stack이란 무엇이며, 어디에 사용되나요?

Question

IT Interview Practice · Accepted Answer

**stack(스택)**은 **LIFO**(Last-In, First-Out, 후입선출) 컬렉션입니다. 마지막에 push된 원소가 가장 먼저 pop됩니다. 오직 **top(맨 위)**만 다룰 수 있습니다.

## 연산

```text
push(3)   push(7)   pop()->7   peek()->3
 [ 3 ]     [ 7 ]      [ 3 ]      [ 3 ]
           [ 3 ]                 top
            top
```

## 예시

```python
stack = []
stack.append('a')   # push
stack.append('b')   # push
top = stack[-1]     # peek -> 'b'
stack.pop()         # pop  -> 'b'
```

dynamic array나 linked list로 뒷받침될 때 모든 연산은 **O(1)**입니다.

| 연산 | 시간 |
|---|---|
| push | O(1) |
| pop | O(1) |
| peek | O(1) |

## 일반적인 용도

- **함수 호출 스택(call stack)** — 활성 호출과 지역 변수를 추적함.
- **실행 취소/다시 실행(undo/redo)** — 각 동작을 push하고, 취소하려면 pop함.
- **수식 평가 / 파싱** — 괄호 짝 맞추기, 중위 표기를 후위 표기로 변환.
- **백트래킹 & DFS** — 어디로 되돌아갈지 기억함.

## 왜 중요한가

stack은 "가장 최근의 것을 먼저 처리한다"를 모델링하며, 이는 재귀부터 브라우저 뒤로 가기 버튼까지 어디에나 등장합니다.

LIFO 패턴을 인식하면 즉시 stack을 떠올리게 되고, 엉킨 문제가 깔끔한 몇 줄의 push/pop으로 정리되는 경우가 많습니다.

연산

예시

관련 질문

일반적인 용도

왜 중요한가