스택, 큐와 덱 | SW 전공 | 모두의 문제집

1. 스택

스택은 한쪽 끝인 top에서만 삽입과 삭제가 일어나는 LIFO(Last In, First Out) 구조이다.

후위식 6 2 3 + *은 스택으로 계산한다. 2+3=5를 먼저 계산하고 6×5=30이 된다.

큐는 rear에서 삽입하고 front에서 삭제하는 FIFO(First In, First Out) 구조이다.

선형 배열 큐는 앞쪽 공간이 비어도 rear가 배열 끝에 도달하면 공간을 활용하지 못하는 가짜 포화(false overflow) 문제가 생길 수 있다. 이를 해결하는 구조가 원형 큐이다.

크기가 N인 배열에서 인덱스는 (index + 1) mod N으로 순환한다. 구현 방식에 따라 한 칸을 비워 두면 다음 조건을 사용한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

공백: front == rear
포화: (rear + 1) mod N == front

구현마다 front가 첫 원소를 가리키는지, 첫 원소 직전 위치를 가리키는지가 다르므로 문제에서 정의를 확인해야 한다.

구조	원칙	삽입 위치	삭제 위치	대표 활용
스택	LIFO	top	top	함수 호출, DFS
큐	FIFO	rear	front	스케줄링, BFS
덱	양방향	양쪽	양쪽	슬라이딩 윈도, 양방향 처리
우선순위 큐	우선순위	구조에 따라	최고·최저 우선순위	작업 선택, 최단경로

스택은 보통 top이 마지막 원소 인덱스를 가리키도록 구현한다. 빈 스택을 top=-1로 두면 push 후 증가 또는 증가 후 저장 중 어떤 규칙인지 일관되어야 한다.

PYTHON코드 영역 안에서 좌우로 이동할 수 있습니다.

stack = []
stack.append(10)       # push
x = stack.pop()        # pop

원형 큐는 구현 정의를 먼저 확인한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

한 칸 비우기 방식
공백: front == rear
포화: (rear + 1) % N == front
저장 가능 원소 수: N - 1
현재 원소 수: (rear - front + N) % N

front가 첫 원소 직전을 가리키는 구현에서는 삭제할 때 먼저 front=(front+1)%N을 수행한 뒤 원소를 읽는다.

크기 6, 한 칸 비우기 방식에서 처음 front=rear=0이라고 하자. 11, 22, 33을 삽입하면 rear=3이고, 두 번 삭제하면 front=2이다. 이어 44, 55, 66을 삽입하면 rear는 0으로 순환한다.

CODE코드 영역 안에서 좌우로 이동할 수 있습니다.

index : 0   1   2   3   4   5
value : 66  -   -  33  44  55
front=2, rear=0
논리적 순서: 33 → 44 → 55 → 66

배열의 물리적 인덱스 순서와 큐의 논리적 순서를 혼동하지 않는다.

후위식 계산은 값을 스택에 넣고 연산자를 만나면 오른쪽 피연산자, 왼쪽 피연산자 순으로 꺼낸다.

PYTHON코드 영역 안에서 좌우로 이동할 수 있습니다.

b = stack.pop()   # 오른쪽
a = stack.pop()   # 왼쪽
stack.append(a - b)

중위식을 후위식으로 바꿀 때는 연산자 우선순위와 괄호를 스택으로 관리한다. 예를 들어 A*(B+C)-D는 ABC+*D-가 된다.

덱은 단순히 양쪽 큐가 아니다. 다음 문제에서 핵심 도구가 된다.

단조 스택은 다음 큰 원소, 히스토그램 최대 직사각형처럼 “아직 답을 찾지 못한 후보”를 순서 있게 유지한다.

우선순위 큐는 삽입 순서가 아니라 우선순위에 따라 삭제한다. 힙 구현에서는 삽입·삭제가 O(log n), 최우선 원소 확인이 O(1)이다. 같은 우선순위 사이의 FIFO는 별도 순번을 함께 저장하지 않으면 보장되지 않을 수 있다.