내일배움캠프 17일차 - 자료구조 & 알고리즘 3주차 : 쌓고 줄 서기(stack, queue)
Stack
LIFO작업을 수행하는 STL컨테이너이다.
LIFO(Last-In, First-Out, 후입선출): 마지막에 넣은 것이 먼저 나온다. 접시 쌓기에 비유하면 된다.
핵심 연산: push(x), pop(), top() → 모두 O(1)
| 연산 | 설명 | 시간 복잡도 |
| push(x) | 맨 위에 x 추가 | O(1) |
| pop() | 맨 위 요소 제거 (반환값 없음) | O(1) |
| top() | 맨 위 요소 반환 (제거하지 않음) | O(1) |
| empty() | 비어있는지 확인 | O(1) |
※ vector와 stack의 공통점
- vector의 push_back(), pop_back() 이 Stack(LIFO) 동작과 비슷하다.
- 즉, vector로도 스택처럼 동작시킬 수 있다.
※ 그렇다면 C++에 별도의 stack이 있는 이유는?
→ 핵심은 의도를 명확히 하기 위해서. stack을 쓰면 LIFO로만 쓸거라는 선언이 된다.
<예시1> push(10) → push(20) → push(30)
 |
| stack은 항상 맨 위에 쌓인다. |
<예시2> pop() → top() = ?
 |
| top() = 20 |
stack은 중간 원소에 접근할 방법이 없다. 오직 맨위(top)만 볼 수 있다.
이것이 스택의 본질이자. 의도를 명확히 하는 설계의 핵심이다.
queue
FIFO작업을 수행하는 STL컨테이너이다.
줄 서기
FIFO(First In, First Out, 선입선출): 먼저 넣은 것이 먼저 나온다. 줄 서기에 비유하면 된다.
스택과의 차이: 스택은 한쪽 끝(top)에서만, 큐는 뒤에서 넣고 앞에서 뺀다.
| 연산 | 설명 | 시간 복잡도 |
| push(x) | 뒤에 x 추가 | O(1) |
| pop() | 맨 앞 요소 제거 (반환값 없음) | O(1) |
| front() | 맨 앞 요소 반환 | O(1) |
| back() | 맨 뒤 요소 반환 | O(1) |
<예시1> push(10) → push(20) → push(30)
 |
| queue는 항상 뒤(back)에 추가된다. |
<예시2> pop() → front() = ?
 |
| front() = 20, 항상 앞(front)부터 빠져나간다. |
※ vector는 앞에서 빼면(erase) → O(n)이었는데?
queue의 pop()은 O(1)이다. 왜일까?
→ queue는 내부적으로 deque를 사용하기 때문이다.
deque는 양쪽 끝에서 삽입/삭제가 O(1)이다
stack vs queue (같은 입력, 다른 출력)
<예시> 같은 순서로 1,2,3을 넣고 하나씩 빼면?
| Stack (LIFO) | Queue (FIFO) | |
| 비유 | 접시 쌓기 | 줄 서기 |
| 넣기 | 위에 쌓기 push(x) | 뒤에 서기 push(x) |
| 빼기 | 위에서 빼기 pop() | 앞에서 빼기 pop() |
| 확인 | top() | front() / back() |
| 대표 용도 | Undo, 괄호 검사, DFS | 순서 처리, 대기열, BFS |
※ 판단 기준: 가장 최근의 것이 중요하면 Stack, 순서대로 처리해야 하면 Queue
내부 구현 - 컨테이너 어댑터
stack과 queue 는 컨테이너 어댑터 라고 불린다.
기존 컨테이너를 감싸서 접근 방식을 제한 한 것.
→ queue의 앞에서 빼기가 O(1)인 이유이기도 하다. (vector는 앞에서 빼면 O(n))
<예제> 괄호 짝 맞추기 (Stack의 대표 패턴)
<예제(도전)> vector로 stack 흉내내기
 |
vector로도 되는데 왜 stack을 쓸까? → 의도 표현 + 실수 방지 |
프로그램은 함수를 스택으로 관리한다.
함수를 호출하면 스택 프레임이 쌓인다.
<예시> main() → funcA() → funcB() 호출 시
 |
| 마지막에 호출된 함수가 먼저 끝난다 = LIFO |
Stack Overflow
재귀 함수가 끝없이 자기 자신을 호출하면?
→ 스택 프레임이 끝없이 쌓이다가 메모리(보통 1~8MB)가 꽉 차면 발생
메모리 구조와의 연관점
Stack 영역: 함수 호출 시 자동으로 잡히는 공간
Heap 영역: vector등 동적할당한 원소가 사는 곳
실전에서의 사용
게임 개발
- Stack 사용: Undo/Redo 시스템 (예: Undo 스택에서 pop, redo 스택에 push)
- Queue 사용: 입력 이벤트 큐 / 네트워크 패킷 큐 / 매칭 대기열
웹/서버
- Stack 사용: 브라우저 뒤로가기 / 앞으로가기
- Queue 사용: 메시지 큐(Message Queue) = 서비스 간 비동기 통신
일반 CS
- Stack 사용: 함수 호출 스택 = 모든 프로그래밍 언어의 핵심
- Queue 사용: OS 프로세스 스케줄링 = Ready Queue
※ 나중에 배울 DFS는 스택 기반, BFS는 큐 기반
오늘의 핵심
- Stack (LIFO): 마지막에 넣은 것이 먼저 나온다.
push(), pop(), top() → 모두 O(1)
- Queue (FIFO): 먼저 넣은 것이 먼저 나온다.
push(), pop(), front() → 모두 O(1)
- 판단기준
가장 최근 것이 중요하면 Stack,
순서대로 처리해야하면 Queue
- 둘 다 내부적으로 deque를 사용하며
기존 컨테이너의 접근 방식을 제한하여 의도를 명확히 하는 설계라 볼 수 있다.
댓글
댓글 쓰기