Stack은 Queue와 아주 대조되는 자료구조이다.
스택(Stack)은 후입선출(LIFO) 순서로 데이터를 저장하는 자료구조이다.
데이터를 추가하는 push 와 데이터를 추출하는 pop 모두 O(1) 의 낮은 비용으로 연산이 가능하며, 프로그램의 함수 호출, 웹 브라우저 방문기록, 깊이우선탐색(DFS) 등에 주로 사용된다.
Stack의 특징
1. 후입선출(LIFO)
스택에 새로운 요소가 추가되면 기존 요소 위에 배치된다. 마찬가지로 스택에서 요소가 제거되면 최상위 요소가 먼저 제거된다.
이렇게 stack의 연산은 최상위 요소에서만 진행되며 이 요소에 대한 포인터를 top이라고 한다.
2. push & pop
데이터를 추가하는 것을 push라고 하며, 반대로 데이터를 추출하는 것을 pop이라고 한다.
큐와 마찬가지로 비어있는 스택에서 pop을 하면 underflow라고 하며, 가득차 있는 스택에 push를 하면 overflow라고 한다.
Stack의 구현 방식
Array-based
배열의 마지막에 데이터를 추가하는 것으로 push 연산을 구현하고, 마지막 데이터를 추출하는 것으로 pop 연산을 구현한다. 따라서 push는 Amortized O(1), pop은 O(1) 의 비용이 소요된다.
List-based
Linked List의 head 노드에 데이터를 추가하는 것으로 push은 구현하고, head 노드의 데이터를 추출하는 것으로 pop을 구현한다. 따라서 push와 pop 모두 O(1)의 비용이 소요된다.
요약
| Operation | Worst Case |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
장점
- 빠른 연산: 크기에 상관 없이 모든 연산에서 O(1) 의 비용이 소요된다.
단점
- 딱히 없음
Reference
🖥️