스택 (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

시간 복잡도

필수 질문

추천 연습 문제