Page 143 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

04-2 큐

이번에 살펴볼 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조입니다. 하
지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO; First In First Out)인 점이 스택
과 다릅니다.

큐란?

큐(queue)는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다. 그림
4-7에서 볼 수 있듯이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조를 이루고 있
습니다. 생활에서 볼 수 있는 큐의 예는 은행 창구에서 차례를 기다리는 대기열이나 마트에서
계산을 기다리는 대기열을 들 수 있습니다.

만약 이렇게 기다리는 대기열이 ‘스택’이라면 가장 먼저 줄을 선 사람이 가장 늦게까지 기다리게 됩니다.

큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라

고 합니다. 또 데이터를 꺼내는 쪽을 프런트(front)라 하고, 데이터를 넣는 쪽을 리어(rear)라고
합니다.
54를 디큐

54 54 54 65 65 맨 앞(front)
65 65 83 83
83 79

맨 뒤(rear)

54를 인큐 65를 인큐 83을 인큐 79를 인큐
[그림 4-7] 인큐와 디큐

배열로 큐 만들기

스택과 마찬가지로 큐는 배열을 사용하여 구현할 수 있습니다. 그림 4-8을 보면서 배열로 구
현한 큐에 대한 작업을 살펴보겠습니다. 그림의 a 는 배열의 프런트(front)부터 4개(19, 22,

04•스택과 큐 143