왜 스택과 큐를 따로 배우는가

05편에서 자료구조는 여러 데이터를 “어떤 방식으로 조직하느냐”에 대한 답이라고 정리했다. 06편의 배열과 07·08편의 연결리스트는 데이터를 넣고 뺄 때 위치를 자유롭게 지정할 수 있는 구조였다. 반면 스택(stack)과 큐(queue)는 위치를 자유롭게 고르지 못하게 일부러 제한을 건 자료구조다. “넣고 빼는 순서를 딱 하나로 고정”하면, 그 순서를 이용해야 하는 문제(되돌리기, 순서 대로 처리하기, 함수 호출 관리)를 아주 단순하고 빠르게 풀 수 있기 때문이다.

이 제한이 정확히 무엇인지가 스택과 큐를 구분하는 핵심이고, 독학사 시험에서 “다음 상황에 알맞은 자료구조는?”이라는 형태로 자주 나온다.

스택 — 마지막에 넣은 것부터 나온다

스택(stack)은 데이터를 한쪽 끝(top)으로만 넣고 뺄 수 있는 자료구조다. 이 성질을 LIFO(Last-In-First-Out, 후입선출)라고 부른다. 나중에 넣은 원소가 가장 먼저 나온다는 뜻이다.

쉽게 말하면: 스택은 접시를 쌓아 올리는 것과 같다. 접시는 맨 위에 올리고(push), 쓸 때도 맨 위 것부터 집어서(pop) 쓴다. 맨 아래 접시를 먼저 쓰려면 위에 쌓인 접시를 전부 치워야 한다.

스택의 기본 연산

01편에서 스택 ADT의 네 연산(push, pop, peek, isEmpty)을 이미 명세했다. 여기서는 그 연산들이 실제로 자료를 어떻게 바꾸는지 표로 추적한다.

이 추적표가 보여주듯, push로 넣은 순서(10, 20, 30)와 pop으로 나오는 순서(30, 20, 10)는 완전히 반대다. 이것이 LIFO의 실체다.

자주 틀리는 점: “스택은 항상 배열로 구현한다”는 틀린 생각이다. 01편에서 배웠듯 ADT는 구현 방식을 정하지 않는다. 스택은 배열로도, 연결리스트로도 구현할 수 있다. 아래에서 두 방식을 모두 본다.

스택을 배열로 구현하기

배열로 스택을 구현하면, top의 위치를 가리키는 정수 변수 하나만 있으면 된다. 보통 top을 “가장 최근에 넣은 원소의 인덱스”로 두고, 빈 스택일 때 top을 -1로 초기화한다.

• push(x): top을 1 증가시키고 arr[top]에 x를 저장한다. 시간 복잡도 O(1).
• pop(): arr[top]을 반환하고 top을 1 감소시킨다. 시간 복잡도 O(1).
• isEmpty(): top이 -1이면 참. O(1).
• isFull(): top이 배열의 마지막 인덱스(배열 크기 - 1)에 도달했으면 참. O(1).

배열 구현의 장점은 모든 연산이 O(1)이라는 점이지만, 단점은 배열 크기를 미리 정해야 하므로 스택 오버플로(stack overflow, 배열이 꽉 찬 상태에서 push를 시도하는 상황)가 발생할 수 있다는 점이다.

스택을 연결리스트로 구현하기

연결리스트로 구현하면 07편의 단순 연결리스트 노드를 그대로 쓰되, 항상 머리(head) 쪽에서만 삽입·삭제한다. 머리 노드가 곧 top이다.

• push(x): 새 노드를 만들어 머리 앞에 연결한다(07편의 머리 삽입과 동일). O(1).
• pop(): 머리 노드를 떼어내고 그 값을 반환한 뒤, 머리를 다음 노드로 옮긴다. O(1).

연결리스트 구현은 크기 제한이 없어(메모리가 허용하는 한) 오버플로를 걱정할 필요가 없지만, 노드마다 링크(포인터)를 저장할 추가 메모리가 든다. 이 트레이드오프는 06~08편에서 다룬 배열과 연결리스트의 비교와 정확히 같은 구도다.

큐 — 먼저 넣은 것부터 나온다

큐(queue)는 한쪽 끝(rear, 후단)으로 넣고 반대쪽 끝(front, 전단)으로 빼는 자료구조다. 이 성질을 FIFO(First-In-First-Out, 선입선출)라고 부른다.

쉽게 말하면: 큐는 은행 창구 앞에 줄을 선 것과 같다. 줄 뒤(rear)에 서면(enqueue) 줄 앞(front)에서부터 순서대로 처리되어 빠져나간다(dequeue). 새치기가 없다.

큐의 기본 연산

넣은 순서(10, 20, 30)와 나오는 순서(10, 20, 30)가 똑같다. 이것이 FIFO이며, 앞서 본 스택의 LIFO와 정반대다.

큐를 배열로 구현할 때 생기는 문제 — 그리고 원형 큐

큐를 배열로 가장 단순하게 구현하면 front와 rear라는 두 개의 인덱스 변수를 둔다. enqueue는 rear를 늘리며 값을 넣고, dequeue는 front를 늘리며 값을 뺀다. 그런데 이 방식에는 심각한 문제가 있다.

배열 크기가 5(인덱스 0~4)이고, enqueue를 5번 해서 배열이 가득 찼다고 하자. 이제 dequeue를 2번 해서 front가 2로 옮겨 갔다. 배열의 인덱스 0, 1 자리는 이제 비어 있는데도, rear는 이미 4(배열 끝)에 있어서 새로 enqueue할 자리가 없다고 잘못 판단하게 된다. 실제로는 빈 칸(0, 1번)이 있는데도 “가득 찼다”고 오판하는 이 현상을 선형 큐(linear queue)의 잘못된 오버플로라고 부른다.

이 문제를 해결하는 방법이 원형 큐(circular queue)다. 배열의 끝(마지막 인덱스)에 도달하면 다시 처음(인덱스 0)으로 돌아가도록, 인덱스 계산에 나머지 연산(modulo, 기호 %)을 쓴다.

• $n$: 배열의 전체 크기
• $\bmod$: 나머지 연산자. % 기호로 표기하며, “나눈 나머지를 취한다”는 뜻이다.

이 계산 덕분에 인덱스가 4(배열 크기 5의 마지막)에서 다시 늘어나면 (4 + 1) mod 5 = 0이 되어 자동으로 처음 칸으로 돌아간다. 배열을 마치 원(circle)처럼 이어 붙여 쓰는 셈이어서 “원형” 큐라고 부른다.

이 표의 7번째 줄이 원형 큐의 핵심 장면이다. rear가 배열 끝(인덱스 4)에서 다시 인덱스 0으로 돌아가, 앞에서 비워진 칸(원래 A가 있던 자리)을 재사용한다.

자주 틀리는 점: “가득 참”과 “비어 있음”을 어떻게 구분하는지가 시험에서 자주 등장한다. front와 rear가 같은 위치면 “비어 있다”는 뜻일 수도 있지만, 계속 채워서 한 바퀴를 돌면 다시 front == rear가 되어 “가득 찼다”는 뜻이 될 수도 있다. 이 모호함을 없애기 위해 실제 구현에서는 흔히 배열 한 칸을 항상 비워 두거나(가득 찼을 때 (rear + 1) mod n == front), 별도의 원소 개수 카운터를 둔다.

큐를 연결리스트로 구현하기

연결리스트로 큐를 구현하면 원형 큐 같은 나머지 연산 트릭이 필요 없다. front가 가리키는 노드에서 삭제하고, rear가 가리키는 노드 뒤에 삽입하면 된다. 단, rear에서 빠르게 삽입하려면 08편에서 다룬 것처럼 rear를 가리키는 포인터를 따로 유지해야 한다(그렇지 않으면 매번 끝까지 순회해야 해서 O(n)이 된다).

덱 — 양쪽에서 넣고 뺄 수 있는 큐

덱(deque, Double-Ended Queue의 줄임말이며 “덱” 또는 “디큐”로 읽는다)은 양쪽 끝(front와 rear) 모두에서 삽입과 삭제가 가능한 자료구조다. 스택과 큐를 합친 것으로 볼 수도 있다.

• addFront(x) / addRear(x): 앞 또는 뒤에 원소를 넣는다.
• removeFront() / removeRear(): 앞 또는 뒤에서 원소를 뺀다.

덱은 앞쪽만 쓰면 스택처럼, 한쪽으로 넣고 반대쪽으로 빼면 큐처럼 동작한다. 즉 스택과 큐는 덱의 사용 방식을 제한한 특수한 경우로 볼 수 있다.

쉽게 말하면: 덱은 양쪽에 문이 달린 기차 칸이다. 앞문으로도 뒷문으로도 타고 내릴 수 있다. 앞문만 쓰기로 정하면 스택이 되고, 뒷문으로 타서 앞문으로 내리기로 정하면 큐가 된다.

스택·큐·덱 비교

자주 틀리는 점

• LIFO와 FIFO를 반대로 외우는 실수: 스택은 “마지막에 넣은 것이 먼저 나온다”(Last-In-First-Out), 큐는 “먼저 넣은 것이 먼저 나온다”(First-In-First-Out)다. 두 단어의 순서(Last vs First)에 집중해서 외우면 헷갈리지 않는다.
• 큐를 배열로 구현할 때 원형 처리를 빠뜨리는 실수: 단순히 front와 rear를 계속 증가만 시키면, 배열 앞쪽에 빈 칸이 있어도 다 찬 것으로 오판한다. 나머지 연산으로 인덱스를 순환시켜야 한다.
• peek(top 확인)과 pop(top 제거)을 혼동하는 실수: peek은 값을 보기만 하고 스택·큐 상태를 바꾸지 않지만, pop·dequeue는 원소를 실제로 제거해 상태를 바꾼다.
• 덱을 스택·큐와 완전히 다른 자료구조로 오해하는 실수: 덱은 스택과 큐를 포함하는 더 일반적인 구조다. 스택과 큐는 덱의 삽입·삭제 위치를 한쪽으로 제한한 특수한 사용 방식으로 이해하는 것이 정확하다.

핵심 정리

• 스택은 LIFO(후입선출), 큐는 FIFO(선입선출) 성질을 가지며, 둘 다 삽입·삭제 위치가 제한된 자료구조다.
• 스택과 큐 모두 배열과 연결리스트로 구현할 수 있고, 배열 구현은 O(1) 연산이 가능하지만 크기 제한이 있다.
• 큐를 배열로 구현할 때는 front·rear 인덱스를 나머지 연산(mod)으로 순환시키는 원형 큐가 필요하다. 그렇지 않으면 빈 칸이 있는데도 가득 찬 것으로 오판한다.
• 덱은 양쪽 끝에서 삽입·삭제가 가능한 자료구조이며, 스택과 큐는 덱의 사용 방식을 제한한 특수한 경우로 볼 수 있다.

마무리 복습

참고 자료

• 국가평생교육진흥원 과목별 평가영역  — 자료구조 과목의 평가영역과 출제 범위를 확인할 수 있는 공식 자료.
• 국가평생교육진흥원 독학학위제  — 독학학위제 시험 체계 전반을 확인할 수 있는 공식 사이트.