스택과 큐

스택(stack)과 큐(queue)는 값을 넣고 빼는 자리를 줄의 끝으로 정해 둔 선형 구조입니다. 스택은 한쪽 끝에서만 넣고 빼서 나중에 넣은 값이 먼저 나오고, 큐는 뒤로 넣고 앞에서 빼서 먼저 넣은 값이 먼저 나옵니다. 배열은 아무 칸이나 꺼낼 수 있어 무엇을 먼저 꺼낼지 따로 챙겨야 하지만, 스택과 큐는 꺼내는 차례가 구조에 들어 있어 되돌아가기나 줄 서기 같은 일을 차례가 꼬이지 않게 처리합니다. 아래 그림은 같은 값 1·2·3이 스택과 큐에서 다른 차례로 나오고, 원형 큐의 rear가 끝 칸에서 첫 칸으로 돌아가 앞쪽 빈칸을 쓰는 모습을 보입니다.

1스택 — 나중에 넣은 값이 먼저 나온다

스택은 한쪽 끝에서만 넣고 뺍니다. 넣기를 push, 빼기를 pop이라 하고, 맨 위 값의 자리를 top이 가리킵니다. 나중에 넣은 값이 먼저 나오므로 후입선출(LIFO, Last In First Out)이라 부릅니다. 칸이 다 찼는데 넣으면 오버플로(overflow), 빈 스택에서 빼면 언더플로(underflow)입니다.

넣는 차례가 정해져 있어도, 사이사이 언제 빼느냐에 따라 나오는 차례가 달라집니다. 1·2·3을 이 차례로 넣으며 아무 때나 뺄 수 있으면 나올 수 있는 차례는 다섯 가지이고, 3·1·2 하나만 나올 수 없습니다.

규칙은 이렇습니다. 어떤 값이 나온 뒤, 그보다 먼저 넣고 아직 남은 값들은 넣은 차례의 거꾸로만 나옵니다.

2큐와 데크 — 먼저 넣은 값이 먼저 나온다

큐는 뒤(rear)로 넣고 앞(front)에서 뺍니다. 먼저 넣은 값이 먼저 나오므로 선입선출(FIFO, First In First Out)이라 부릅니다. 데크(deque)는 앞과 뒤 양쪽에서 모두 넣고 뺄 수 있는 큐입니다. 빈 데크의 앞에 1, 뒤에 2, 앞에 3을 넣으면 앞에서부터 3 1 2로 놓이고, 뒤에서 빼면 2가, 앞에서 빼면 3이 나옵니다.

꺼내는 차례가 다르니 맞는 일도 다릅니다.

후위 표기는 이진 트리 순회와 수식 표기에서, 두 탐색은 그래프와 탐색에서 봅니다.

3원형 큐 — 끝 칸 다음은 첫 칸

배열로 큐를 만들면 뺄 때마다 front가 뒤로 옮겨 가서 앞쪽에 빈칸이 생깁니다. 그런데 rear가 끝 칸에 닿으면 앞쪽 빈칸이 있어도 더 넣지 못합니다. 원형 큐(circular queue)는 끝 칸 다음을 첫 칸으로 이어, 칸 번호를 칸 수 N으로 나눈 나머지로 셉니다.

이 레슨의 원형 큐는 front가 맨 앞 값의 바로 앞 칸을, rear가 맨 뒤 값의 칸을 가리키고, 처음에는 둘 다 0입니다.

• 넣기: rear = (rear + 1) % N⁠으로 옮긴 뒤 그 칸에 넣습니다.
• 빼기: front = (front + 1) % N⁠으로 옮긴 뒤 그 칸의 값을 꺼냅니다.
• 비었음: front == rear
• 가득 참: (rear + 1) % N == front

칸 N개를 모두 채우면 rear가 front와 같아져 비었을 때와 구별되지 않습니다. 그래서 칸 하나를 늘 비워 두고, 값이 N − 1개가 되면 가득 찬 것으로 봅니다.

예제

C로 만든 원형 큐

칸 넷짜리 원형 큐에 1·2·3을 넣고, 둘을 뺀 뒤, 4를 넣고 하나를 더 뺍니다. get은 꺼낸 값을 찍습니다.

#include <stdio.h>
int q[4], front, rear;
void put(int x) {
    rear = (rear + 1) % 4;
    q[rear] = x;
}
void get(void) {
    front = (front + 1) % 4;
    printf("%d\n", q[front]);
}
int main(void) {
    put(1); put(2); put(3);
    get(); get(); put(4); get();
    printf("rear=%d\n", rear);
}

무엇이 찍힐까요? 답을 정한 뒤 펼쳐 보세요.

1
2
3
rear=0

시험 포인트

• 필기: 스택은 한쪽 끝에서만 넣고 빼는 후입선출(LIFO), 큐는 뒤로 넣고 앞에서 빼는 선입선출(FIFO)이고, 데크는 양 끝에서 넣고 뺍니다. 넣는 차례를 주고 '나올 수 없는 차례'를 고르는 문제가 자주 나옵니다. 스택의 쓰임(함수 호출·후위 표기 계산·깊이 우선 탐색)과 큐의 쓰임(너비 우선 탐색·인쇄 대기열)을 뒤바꾼 보기가 함정입니다. 원형 큐는 칸 하나를 비워 두어 N칸에 N − 1개를 넣고, 가득 참을 (rear + 1) % N == front⁠로 가립니다.
• 실기: 원형 큐 코드의 출력을 그대로 씁니다. rear·front를 % N으로 옮길 때 끝 칸 다음이 0번 칸인 것을 놓치지 않습니다. 이름은 스택(Stack)·큐(Queue)·데크(Deque)·원형 큐(Circular Queue)로 씁니다.

확인 문제

1. 스택에 A·B·C·D를 이 차례로 넣고, 넣는 사이사이 아무 때나 뺄 수 있습니다. 나올 수 없는 차례를 고르세요.

• ① B A D C
• ② C B D A
• ③ C A B D
• ④ A D C B

2. 다음 (가)~(라)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 택배 상자를 트럭 안쪽부터 실었다가, 내릴 때는 문 쪽 상자부터 내립니다.
• (나) 놀이기구 앞에 온 사람은 줄 끝에 서고, 줄 맨 앞사람부터 탑니다.
• (다) 카드 묶음의 맨 위와 맨 아래 어느 쪽으로도 카드를 넣고 뺍니다.
• (라) 칸 다섯짜리 배열에 줄을 세우고, 4번 칸 다음에는 0번 칸으로 넘어가 앞에서 비운 칸을 다시 씁니다.

3. 예제 코드의 12번 줄에서 put(3);을 지웠습니다. 출력을 그대로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

#include <stdio.h>
int q[4], front, rear;
void put(int x) {
    rear = (rear + 1) % 4;
    q[rear] = x;
}
void get(void) {
    front = (front + 1) % 4;
    printf("%d\n", q[front]);
}
int main(void) {
    put(1); put(2);
    get(); get(); put(4); get();
    printf("rear=%d\n", rear);
}

1
2
4
rear=3