[Stack and Queue] 스택, Stack

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 스택 (Stack)

• 한 쪽 끝에서만 새로운 항목을 저장하거나 삭제하는 자료구조
• 후입선출(Last-In First-Out, LIFO) 원칙 하에 삽입과 삭제 수행

 

- 연산

• 데이터 삽입 : Push
• 데이터 삭제 : Pop
• 데이터 읽기 : Top

 

- 수행 시간

• 파이썬의 리스트로 구현한 스택의 삽입과 삭제 연산은 각각 O(1) 소요
• 파이썬 리스트의 크기를 확대 또는 축소 시키는 경우에 스택의 모든 항목을 새 리스트로 복사해야 하므로 O(n) 소요
• 단순 연결 리스트로 구현한 스택의 삽입과 삭제 연산은 각각 O(1) 소요

 

- 응용

• Recursive program
• 간단한 수식 계산기(Infix, Prefix, Postfix)
• 그래프의 깊이 우선 탐색(DFS)