[열혈자료구조] 7강. 큐(queue)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

큐(queue)는 말 그대로 대기열이다. 놀이기구 줄을 설 때, 나중에 온 사람이 먼저 탑승하면 그건 새치기가 된다. 따라서, 대기열은 먼저 온 사람이 먼저 탑승하고, 나중에 온 사람은 나중에 탑승하는 선입선출(FIFO, First in First Out) 구조이다. LIFO 구조였던 스택과는 대비된다.

 

큐의 ADT

스택에는 push, pop, peek의 기능이 핵심적이었다. 큐는 데이터를 넣는 부분과 빼는 부분의 위치가 다르기 때문에, 아래와 같은 두 개의 연산이 핵심적이다.

• enqueue: 큐에 데이터를 넣음
• dequeue: 큐에서 데이터를 뺌

이를 이용하여, ADT에 아래 5가지를 구현하자.

1. void QueueInit(Queue * pq);
Queue를 초기화한다.

2. int QIsEmpty(Queue * pq);
Queue가 비었으면 1, 비어있지 않으면 0을 반환한다.

3. void Enqueue(Queue * pq, Data data);
큐에 데이터를 저장한다.

4. Data Dequeue(Queue * pq);
큐에서 데이터를 제거한다.

5. Data QPeek(Queue * pq);
큐에서 데이터를 삭제하지 않고, 저장 순서가 가장 앞인 데이터를 확인한다.

 

스택과 마찬가지로, 큐를 배열과 연결 리스트 기반으로 구현해 보자. 스택에서 데이터를 꺼내는(pop) 위치를 앞으로 변경(Dequeue)하기만 하면 될 것 같지만, 실제로는 차이가 조금 있다.

---

배열로 큐 구현하기

배열로 큐를 구현할 때는 스택과 달리 F와 R이라는 두 변수를 설정한다. F는 Front로 큐의 머리, R은 Rear로 큐의 꼬리를 나타낸다. 이렇게 구성하는 이유는 스택은 넣고 빼는 곳이 같기 때문에 한 곳만 참조하면 되지만, 큐는 넣는 곳과 빼는 곳 양쪽을 참조해야 하기 때문이다. 이때, R을 참조하여 enqueue를, F를 참조하여 dequeue를 한다.

Enqueue 과정

 

가장 좋은 연산 방법은 메모리 공간에서 데이터의 이동을 최소화하는 연산이다. Dequeue를 할 때, 위의 Enqueue 과정을 단순히 뒤집어서 R을 한 칸씩 앞으로 당긴다고 생각해 보자.

하지만, 이렇게 될 경우 처음 큐에 1, 2, 3이 들어있었을 경우, dequeue는 F에서 진행되어야 하므로 두 번째 큐에는 2, 3이 들어있어야 하고 세 번째 큐에는 3이 들어있어야 하기 때문에 메모리 공간 상에서 데이터가 계속 움직이게 된다. 이는 매우 비효율적이므로, dequeue 과정에서는 아래와 같이 F를 움직여야 한다.

하지만, 이러한 경우 발생할 수 있는 문제는, 배열로 구현할 때는 최대 길이를 정해놓고 한다는 점이다. 즉, enqueue와 dequeue를 반복하다 보면 큐의 위치가 점점 오른쪽으로 옮겨지는데, 배열의 최대 길이에 해당하는 칸에 도달하면 더 이상 연산이 불가능해 지는 것이다. 이를 해결하기 위해, 배열의 최대 길이에 해당하는 칸에 도달한 queue에서 enqueue가 되면 다시 첫 번째 칸에 저장되는 구조를 생각할 수 있다. 이를 원형 큐(circular queue)라고 한다.

즉 위와 같이 enqueue 과정과 dequeue 과정이 진행되는 것이다. 파란색 화살표는 enqueue 과정, 빨간색 화살표를 dequeue 과정을 나타낸다. 이렇게 하면 배열의 마지막에 도달했을 때 연산을 더 이상 못 하는 것을 막을 수 있다. 하지만, 이 경우에도 문제가 있다. F와 R의 위치만으로 꽉 찬 경우와 텅 빈 경우를 구분할 수 없다는 것이다. 즉 dequeue를 계속 해서 빈 큐를 만드는 경우와, enqueue를 계속 해서 꽉 찬 큐를 만드는 경우 F와 R의 상대적 위치가 같다.

 

이는 생각보다 간단하게 해결할 수 있는데, F가 항상 비어있는 위치를 가리키도록 하여  할당된 저장 공간을 모두 채우지 않는 것을 규칙으로 만들면 된다. 그러면 F와 R이 같은 위치를 가리키는 경우가 빈 큐를 나타내게 되고, R이 F보다 한 칸 뒤에 있는 경우가 꽉 찬 경우가 된다. 즉 원형 큐를 구현할 때, enqueue와 dequeue는 아래와 같이 두 가지로 정리할 수 있다.

1. Enqueue: R을 한 칸 시계방향으로 옮기고, 옮긴 위치에 데이터 저장
2. Dequeue: F를 한 칸 시계방향으로 옮기고, 옮긴 위치의 데이터 삭제

원형 큐의 헤더 파일(CircularQueue.h)은 아래와 같다.

#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__

#define TRUE	1
#define FALSE	0

#define QUE_LEN	100
typedef int Data;

typedef struct _cQueue
{
	int front;
	int rear;
	Data queArr[QUE_LEN];
} CQueue;

typedef CQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

 

각 함수를 구현하기 전에, NextPosIdx 라는 함수를 정의하여 다음 인덱스를 쉽게 가져올 수 있도록 한다.

int NextPosIdx(int pos){
    if(pos == QUE_LEN-1) return 0;
    else return pos + 1;
}

 

큐가 원형으로 되어 있으므로, queArr의 마지막 칸에서 NextPosIdx를 호출하면 다시 처음으로 돌아온다.

void QueueInit(Queue * pq){
    pq->front = 0;
    pq->rear = 0;
}

int QIsEmpty(Queue * pq){
    if(pq->front == pq->rear) return TRUE;
    else return FALSE;
}

 

QueueInit과 QIsEmpty는 이제까지의 구현화 같은 방식으로, 위와 같이 간단하게 나타낼 수 있다.

void Enqueue(Queue * pq, Data data){

    if(NextPosIdx(pq->rear)==pq->front){
        print("queue is full");
        exit(-1);
    }
    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;

}

 

다음은 Enqueue이다. Queue가 꽉 찼는지는 위에서 설명한 대로, F가 R보다 1칸 앞에 있는지 확인하면 된다. 또한, 데이터를 삽입할 때는 R을 한 칸 앞으로 밀고 그 자리에 넣는다.

Data Dequeue(Queue * pq, Data data){
    if(QIsEmpty(pq)){
        print("queue is empty");
        exit(-1);
    }
    pq->front = NextPosIdx(pq->front);
    return pq->queArr[pq->front];
}

Data QPeek(Queue * pq, Data data){
    if(QIsEmpty(pq)){
        print("queue is empty");
        exit(-1);
    }
    return pq->queArr[NextPosIdx(pq->front)];
}

 

Dequeue와 QPeek는 F의 위치를 옮기는지 옮기지 않는지의 차이만 있다. Dequeue에서는 F를 한 칸 앞으로 옮기고, 해당 위치의 데이터를 반환한다.

 

연결 리스트로 큐 구현하기

연결 리스트로 큐를 구현하기 위해서는, 스택과 마찬가지로 노드를 정의하고 이를 이용하여 큐를 정의한다. 연결 리스트로 큐를 구현하면, 길이에 제한이 없기 때문에 원형으로 큐를 구현해야 할 필요성이 사라진다. 따라서, 직선형으로 구현할 것이며 F와 R은 항상 큐의 처음과 끝을 참조한다. 단, 비어 있을 때는 둘 다 NULL을 참조한다.

 

리스트 큐의 헤더 파일은 배열 큐와 동일하지만 노드의 정의가 포함되어 있고, F와 R이 노드로 정의되어 있다. 리스트 큐는 아래와 같이 초기화한다.

void QueueInit(Queue * pq){
    pq->front = NULL;
    pq->rear = NULL;
}

 

큐의 F가 NULL을 가리키고 있는지만 확인해도, 큐가 비어있는지 아닌지를 확인할 수 있다. 따라서 QIsEmpty는 아래와 같이 구현한다.

int QIsEmpty(Queue * pq){
    if(pq->front == NULL) return TRUE;
    else return FALSE;
}

 

Enqueue, Dequeue 구현

 

Enqueue는 R에 노드를 추가하면 된다. 큐가 원래 비어 있었을 경우 새로운 노드를 F와 R에 모두 연결하고, 차 있었을 경우 아래 그림처럼 R을 한 칸 밀고 노드를 끼워넣으면 된다.

차 있는 큐의 enqueue

void Enqueue(Queue * pq, Data data){
    Node * newNode = (Node *) malloc (sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if(QIsEmpty(pq)){
        pq->front = newNode;
        pq->rear = newNode;
    }
    else{
        pq->rear = newNode;
        pq->front->next = newNode;
    }
    
}

 

Dequeue는 F가 가리키고 있는 노드를 삭제하고, 가리키고 있던 노드의 다음 노드를 가리키고록 하면 된다. 문제는 큐에 데이터가 1개 남아있을 때인데, 이때 그 다음 데이터는 NULL이 되므로 F는 문제가 없지만 R은 임의의 값을 가리키게 된다. 하지만 이는 문제가 되지 않는다. QIsEmpty를 정의할 때도 F값만 참조하기 때문에 R 값에는 어떤 것이 들어가도 상관 없다.

 

Data Dequeue(Queue * pq)
{
	Node * delNode;
	Data retData;

	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	delNode = pq->front;
	retData = delNode->data;
	pq->front = pq->front->next;

	free(delNode);
	return retData;
}

Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	return pq->front->data;
}

 

---

큐는 OS, 네트워크에서 아주 중요한 자료구조로, 큐잉 이론(Queuing Theory)라는 학문이 따로 있을 정도이다. 특히, 현상을 시뮬레이션을 하는 영역에서 큐잉 이론이 중요하다.

 

덱(Deque)이란?

덱은 큐와 관련된 자료구조의 일종으로, R에서 데이터를 빼고 F에 데이터를 넣는 큐와 달리 양쪽에서 넣고 빼는 걸 모두 할 수 있다. 이를 Double-Ended Queue, 줄여서 Deque라고 부른다. Enqueue와 Dequeue의 두 가지 연산이 중요했던 큐와 달리, 덱은 아래 4개가 중요하다.

• DQAddFirst: 앞에 데이터 추가
• DQAddLast: 뒤에 데이터 추가
• DQRemoveFirst: 앞에 데이터 삭제
• DQRemoveLast: 뒤에 데이터 삭제

특히, 꼬리에 위치한 노드를 삭제하느 DQRemoveLast를 구현하기 쉽도록 하기 위해서는 단방향 연결 리스트보다 양방향 연결 리스트가 효율적이다. https://cascade.tistory.com/75

[열혈자료구조] 5강. 연결 리스트(Linked List) 3 - (2)

 

덱의 구현을 모두 다루는 것은 큰 의미가 없을 것 같아, 정의에 대한 간단한 소개만 하고, 자세한 구현이 궁금하다면 윤성우의 열혈자료구조 교재나 홈페이지( https://blog.naver.com/oedu/223011150597)를 참고하는 것이 좋을 것 같다.