스택
마지막 업데이트
스택은 열린 끝이 정확히 하나뿐인 컬렉션입니다. 값을 넣을 때는 맨 위에 쌓고(푸시), 뺄 때는 그 맨 위를 다시 걷어냅니다(팝). 그래서 마지막에 들어간 값이 항상 가장 먼저 나옵니다. 이것이 후입선출(LIFO)의 의미이며, 규칙은 이게 전부입니다. 위에 얹힌 것을 먼저 치우지 않고 중간에 손을 넣을 방법은 없습니다. 위의 재생을 누르면 푸시할 때마다 기둥이 자라고 팝할 때마다 같은 끝에서 줄어드는 모습을 볼 수 있습니다.
이 제약이 바로 핵심입니다. 두 연산 모두 맨 위만 건드리므로 스택이 아무리 높아져도 각각 O(1)이고, 이 예측 가능성 덕분에 스택은 컴퓨팅의 아주 많은 부분을 떠받칩니다. 재귀를 굴리는 호출 스택, 편집기의 실행 취소 기록, 파서의 괄호 짝 맞추기, 그리고 재귀적인 깊이 우선 탐색을 루프로 바꾸는 명시적 스택이 그렇습니다. 제거하는 끝을 바꾸면 대신 큐가 됩니다.
시간 및 공간 복잡도
배열 기반 또는 연결 리스트 기반의 표준 스택 기준:
| 연산 | 복잡도 | 비고 |
|---|---|---|
| 푸시(push) | O(1) | 동적 배열에서는 상각 O(1)이며, 가끔 크기를 조정한다. |
| 팝(pop) | O(1) | 항상 맨 위 원소이므로 이동이 필요 없다. |
| 피크(맨 위 조회) | O(1) | 제거하지 않고 맨 위를 읽는다. |
| 탐색 | O(n) | 스택의 용도가 아니다. 아래까지 팝해 내려가야 한다. |
| 공간 | O(n) | 저장된 값 하나당 슬롯 하나. |
단계별 진행
| 단계 | 무슨 일이 일어나는가 |
|---|---|
| 1 | 스택은 비어 있는 상태로 시작하고, 맨 위는 아무것도 가리키지 않는다. |
| 2 | 푸시는 맨 위 자리에 값을 쓰고 맨 위를 한 칸 올린다. |
| 3 | 이후의 푸시는 직전 값 바로 위에 놓인다. |
| 4 | 팝은 맨 위의 값을 읽은 다음 맨 위를 한 칸 내린다. |
| 5 | 돌아오는 값은 항상 가장 최근에 푸시한 값이다. |
| 6 | 빈 스택을 팝하는 것은 오류이며 스택 언더플로라고 부른다. 그래서 실제 코드는 먼저 is_empty()를 확인한다. |
풀이 예제
3, 7, 5를 푸시한 뒤 스택을 모두 비우는 과정:
| 연산 | 스택 (아래에서 위로) | 반환값 |
|---|---|---|
push(3) | [3] | 없음 |
push(7) | [3, 7] | 없음 |
push(5) | [3, 7, 5] | 없음 |
pop() | [3, 7] | 5, 가장 새로운 값 |
pop() | [3] | 7 |
pop() | [] | 3, 가장 오래된 값이 마지막 |
스택을 사용해야 할 때
Stack 코드
Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Stack 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.
Python로 구현한 Stack 코드
Python
1stack = []2
3# Push three values onto the top4for value in [3, 7, 5]:5 stack.append(value)6 print(f"push {value} -> {stack}")7
8# Pop them back off: last in, first out9while stack:10 value = stack.pop()11 print(f"pop {value} -> {stack}")12
13print("empty:", len(stack) == 0)JavaScript로 구현한 Stack 코드
JavaScript
1const stack = [];2
3// Push three values onto the top4for (const value of [3, 7, 5]) {5 stack.push(value);6 console.log(`push ${value} ->`, stack);7}8
9// Pop them back off: last in, first out10while (stack.length > 0) {11 const value = stack.pop();12 console.log(`pop ${value} ->`, stack);13}14
15console.log('empty:', stack.length === 0);Java로 구현한 Stack 코드
Java
1import java.util.ArrayDeque;2import java.util.Deque;3
4public class Main {5 public static void main(String[] args) {6 Deque<Integer> stack = new ArrayDeque<>();7
8 // Push three values onto the top9 for (int value : new int[] {3, 7, 5}) {10 stack.push(value);11 System.out.println("push " + value + " -> " + stack);12 }13
14 // Pop them back off: last in, first out15 while (!stack.isEmpty()) {16 int value = stack.pop();17 System.out.println("pop " + value + " -> " + stack);18 }19
20 System.out.println("empty: " + stack.isEmpty());21 }22}C++로 구현한 Stack 코드
C++
1#include <iostream>2#include <stack>3
4int main() {5 std::stack<int> stack;6
7 // Push three values onto the top8 for (int value : {3, 7, 5}) {9 stack.push(value);10 std::cout << "push " << value << " -> size " << stack.size() << "\n";11 }12
13 // Pop them back off: last in, first out14 while (!stack.empty()) {15 int value = stack.top();16 stack.pop();17 std::cout << "pop " << value << " -> size " << stack.size() << "\n";18 }19
20 std::cout << "empty: " << std::boolalpha << stack.empty() << "\n";21 return 0;22}C로 구현한 Stack 코드
C
1#include <stdio.h>2
3#define CAP 164
5int stack[CAP];6int top = 0; /* index of the next free slot */7
8int main(void) {9 int values[3] = {3, 7, 5};10
11 /* Push three values onto the top */12 for (int i = 0; i < 3; i++) {13 stack[top++] = values[i];14 printf("push %d -> size %d\n", values[i], top);15 }16
17 /* Pop them back off: last in, first out */18 while (top > 0) {19 int value = stack[--top];20 printf("pop %d -> size %d\n", value, top);21 }22
23 printf("empty: %d\n", top == 0);24 return 0;25}스택 자주 묻는 질문
LIFO는 무슨 뜻인가요?
후입선출입니다. 가장 최근에 푸시한 값이 가장 먼저 팝됩니다. 접시 더미가 흔한 비유로, 방금 내려놓은 접시를 집지 맨 아래 접시를 집지는 않습니다. 큐는 반대 규율인 FIFO입니다.
스택과 큐의 차이는 무엇인가요?
어느 쪽 끝에서 빼느냐뿐입니다. 둘 다 한쪽 끝에
O(1)로 추가합니다. 스택은 바로 그 끝에서 빼고(LIFO), 큐는 반대쪽 끝에서 뺍니다(FIFO). 위의 복잡도 표를 포함해 나머지는 모두 동일합니다.스택의 주요 연산은 무엇인가요?
push는 값을 맨 위에 얹고, pop은 맨 위 값을 빼서 반환하며, peek(top이라고도 함)은 제거하지 않고 맨 위를 읽고, is_empty는 남은 것이 있는지 알려줍니다. 네 가지 모두 O(1)입니다.스택 오버플로란 무엇인가요?
남은 공간이 없는 스택에 푸시하는 것입니다. 유명한 사례가 호출 스택입니다. 함수 호출마다 프레임이 쌓이므로, 기저 사례에 도달하지 못하는 재귀는 런타임의 스택 한계에 닿을 때까지 계속 쌓다가 프로그램을 중단시킵니다. 그 반대 오류인, 빈 스택을 팝하는 것은 스택 언더플로입니다.
스택은 어떻게 구현하나요?
흔한 구현은 두 가지입니다. 동적 배열은 끝에서 추가와 제거를 수행해 상각
O(1)이고 캐시 친화적입니다. Python의 list와 Java의 ArrayDeque가 이 방식입니다. 연결 리스트는 머리에서 추가와 제거를 수행해 최악의 경우에도 O(1)이고 크기 조정이 없지만, 원소마다 포인터 비용이 듭니다. C++의 std::stack은 어댑터로, 기본값으로는 분할된 배열인 std::deque 위에서 동작하며 다른 컨테이너를 지정할 수도 있습니다.관련 자료
더 많은 시각화
