[자료구조] 스택 (Stack)

스택은 후입선출(LIFO, Last-In-First-Out)의 구조를 가지는 자료구조이다.

그림과 같이 한 쪽에서만 데이터를 넣고 뺄 수 있다. 정해진 Stack의 사이즈보다 많은 데이터를 쌓으려고할 때 StackOverFlow가 일어난다. Stack은 추상적인 자료 구조로서 배열과 연결 리스트로 구현할 수 있다.
Stack은 중첩 혹은 재귀 함수를 구현하는데 있어서 중요한 방법이며, DFS를 구현하는데 사용된다.

시간 복잡도

동작	Big-O
Top/Peek	O(1)
Push	O(1)
Pop	O(1)
isEmpty	O(1)
Search	O(n)

필수 질문

• LeetCode
  - Valid Parentheses
  - Implement Queue using Stacks

추천 연습 문제

• LeetCode
  - Implement Stack using Queues
  - Min Stack
  - Asteroid Collision
  - Evaluate Reverse Polish Notation
  - Basic Calculator
  - Basic Calculator II
  - Daily Temperatures
  - Trapping Rain Water
  - Largest Rectangle in Histogram