KR_CS_Stack_Queue

Q5: 스택(Stack)과 큐(Queue)

질문: 스택과 큐의 동작 원리를 LIFO/FIFO 관점에서 설명하고, 시간 복잡도와 실무 활용 사례를 설명하세요.

주요 용어

용어	설명
Stack	LIFO(Last In First Out) — 후입선출 자료구조
Queue	FIFO(First In First Out) — 선입선출 자료구조
Push/Pop	스택의 삽입/삭제 연산
Enqueue/Dequeue	큐의 삽입/삭제 연산
Call Stack	함수 호출 정보를 저장하는 스택 구조
Priority Queue	우선순위 기반 큐 (Heap으로 구현)

스택 (Stack) — LIFO

┌─────────┐
│  TOP    │  ← Push / Pop
├─────────┤
│    5    │  (마지막 삽입, 가장 먼저 제거)
├─────────┤
│    3    │
├─────────┤
│    2    │  (첫 삽입, 가장 나중에 제거)
└─────────┘
 BOTTOM

연산 및 시간 복잡도

연산	설명	시간 복잡도
push(item)	스택 상단에 추가	O(1)
pop()	상단 요소 제거 및 반환	O(1)
peek()	상단 요소 확인 (제거 X)	O(1)
isEmpty()	비어있는지 확인	O(1)

활용 사례

사례	설명
함수 호출 스택 (Call Stack)	재귀 호출 시 각 함수 프레임을 스택으로 관리
DFS (깊이 우선 탐색)	탐색할 노드를 스택에 저장하여 가장 깊은 경로 먼저 탐색
괄호 유효성 검사	여는 괄호를 push, 닫는 괄호 만날 때 pop하여 매칭 확인
Undo/Redo	작업 이력을 스택으로 관리

큐 (Queue) — FIFO

Front                              Rear
  ↓                                  ↓
┌─────┐ → ┌─────┐ → ┌─────┐ → ┌─────┐
│  2  │   │  7  │   │  3  │   │  5  │
└─────┘   └─────┘   └─────┘   └─────┘
Dequeue                          Enqueue

연산 및 시간 복잡도

연산	설명	시간 복잡도
enqueue(item)	큐 뒤쪽에 추가	O(1)
dequeue()	앞쪽 요소 제거 및 반환	O(1)
peek()	앞쪽 요소 확인 (제거 X)	O(1)
isEmpty()	비어있는지 확인	O(1)

활용 사례

사례	설명
BFS (너비 우선 탐색)	탐색할 노드를 큐에 저장하여 레벨 순서로 탐색
작업 스케줄링	OS 프로세스 스케줄러, 프린터 스풀러
메시지 큐	Kafka, RabbitMQ — Producer/Consumer 패턴
이벤트 처리	JavaScript 이벤트 루프의 Task Queue

스택 vs 큐 비교

항목	Stack	Queue
원리	LIFO	FIFO
삽입 위치	Top	Rear
삭제 위치	Top	Front
탐색 알고리즘	DFS	BFS
주요 활용	함수 호출, Undo, 괄호 검사	스케줄링, 메시지 큐, 이벤트 처리

우선순위 큐 (Priority Queue)

일반 큐와 달리 우선순위가 높은 항목이 먼저 처리됨. Heap 자료구조로 구현.

연산	시간 복잡도
enqueue	O(log n)
dequeue	O(log n)
peek	O(1)

활용: Dijkstra 최단 경로, 작업 스케줄링, 이벤트 드리븐 시스템

참고

• ← KR_CS지식.md로 돌아가기