3.5 스택
스택(stack)은 후입 선출(LIFO, Last-In-First-Out) 전략을 따르는 특별한 자료 구조로, 마지막에 추가한 원소가 먼저 제거됩니다.
▲ 그림 3-3 스택
스택은 다음과 같이 다양한 용도로 쓰입니다.
1. 재귀(recursion) 호출
2. 후위 표현식(postfix expression)의 계산
3. 스택으로 구현하는 백트래킹(backtracking)
4. 트리와 그래프의 깊이 우선 탐색(DFS, Depth-First Search)
5. 10진수를 2진수로 변환하기
스택의 API는 다음과 같습니다.
• Push(k) 스택의 맨 위에 값 k를 추가합니다.
• Pop() 스택의 맨 위에 있는 원소의 값을 반환하고 이 원소를 제거합니다.
• Top() 스택의 맨 위에 있는 원소의 값을 반환합니다.
• Size() 스택의 원소 개수를 반환합니다.
• IsEmpty() 스택이 비었는지를 결정합니다. 스택이 비었으면 1을 반환합니다.
스택의 모든 연산의 시간 복잡도는 O(1)입니다.