큐는 뭐야?

스택과 마찬가지로 큐를 1 문장으로 요약하면 "선입선출의 특성을 가진 자료구조"라고 할 수 있다. 선입선출은 사실 실생활에서도 굉장히 많이 사용된다. 예를 들어 은행에 갔을 때 번호표를 뽑는 것, 맛집에 갔을 때 순서표를 뽑고 기대리는 것, 편의점 물류 정리 등이 있다. 

다음은 컴퓨터 공학에서 큐의 활용 예시이다.

• 키보드, 마우스 등 입력 장치 관리
• 모니터, 프린터 등 출력 장치 관리
• 운영체제 작업 스케줄링

선입선출의 특성을 가지기 위해서는 원소를 저장하기 위한 배열 data와 맨 앞 원소를 가리킬 front, 맨 뒤 원소를 가리킬 rear 변수가 필요하다. 특성에 맞게 구조체로 표현하면 다음과 같다.

typedef int element;
typedef struct {
    int front, rear;
    element data[QUEUE_SIZE];
} QueueType;

스택과 비슷하게 큐 또한 push와 pop 기능을 제공한지만 명칭은 각각 enqueue, dequeue로 바꿔 부른다. 그 외에도 큐를 구현하기 필요한 함수들에 대해 알아보겠다. 다음은 큐의 추상 자료형이다.

item: , size: , q:

create(size)     :
init(q)          :
is_empty(q)      :
is_full(q)       :
enqueue(q, item) :
dequeue(q)       :
peek(q)          :

큐 또한 대부분의 프로그래밍 언어에서 기능을 제공하기 때문에 언어마다 구현한 방법과 함수명은 다를 수 있지만 기능은 동일하게 작동한다.

 

다음은 (a)~(f)까지 간단하게 큐가 동작하는 것을 그림으로 표현한 것이다.

큐 동작 예시

동작 예시에서 front와 rear가 어떻게 변하고 반환 값은 어떻게 되는지 알아보겠다.

1. 공백 큐에 0을 저장한다. front = -1, rear = 0
2. 큐에 1을 저장한다. front = -1, rear = 1
3. 큐에 가장 오래 머물렀던 0을 제거하여 반환한다. front = 0, rear = 1, return = 0
4. 큐에 2를 저장한다. front = 0, rear = 2
5. 큐에 3을 저장한다. front = 0, rear = 3
6. 큐에 가장 오래 머물렀던 1을 제거하여 반환한다. front = 1, rear = 3, return = 1

위의 예시에서 눈치를 챘을 수도 있지만 enqueue는 rear의 값을 dequeue는 front의 값을 수정한다. 수정할 때에는 인덱스의 값이 증가하기는 하지만 감소하지는 않는다. 그렇다면 큐의 배열의 앞부분은 한번 사용하면 영원히 사용하지 못하게 되는 걸까?

 

궁금증을 해결하기 위해 나온 개념이 원형 큐이다. 원형 큐는 큐와 동작은 같지만 인덱스가 0으로 되돌아오기 때문에 붙여졌다. 다음은 원형 큐에서 front와 rear를 계산하는 법이다.

front = (front + 1) % QUEUE_SIZE
rear = (rear + 1) % QUEUE_SIZE

큐의 크기가 10이고, front가 현재 9라고 했을 때 위 식에 값을 대입하면 front는 0으로 초기화된다. 따라서 enqueue, dequeue 과정에서 값이 계산 증가한다고 하더라도 큐의 공간이 비어있다면 원점으로 되돌아와서 원소를 채워주게 된다.

 

큐의 구조체, 추상 자료형, 동작 예시와 원형 큐의 개념과 인덱스 계산법에 대해 살펴보았다. 큐는 스택과 함께 기본 자료구조로 많이 불리지만 운영체제, 네트워크 등 선입선출이라는 개념은 실생활에서 활용되는 것만큼 컴퓨터 공학에서도 많이 활용되고 있어 공부를 함에 있어 어떻게 사용되는지 생각해보면 좋을 것 같다.