큐
큐(Queue)는 스택처럼 특정한 위치에서 넣고 뺄 수 있는 자료구조입니다. 스택은 입구와 출구가 같아서 나중에 들어간 자료가 먼저 나오는 후입선출 구조였다면, 큐는 입구와 출구가 따로 있어서 먼저들어간 자료가 먼저 나오는 선입선출(FIFO, First Input First Out) 자료구조 입니다.
보통 어딘가 입장할 때 우리는 줄을 섭니다. 그래서 먼저 줄을 선 사람이 먼저 입장하게됩니다. 이 줄이 큐입니다. 혹시 리그 오브 레전드 라는 게임 혹은 다른 게임에서 우리는 게임을 잡기 위해 대기 큐를 잡는다~라고 하죠? 그 큐도 이 큐입니다. 먼저 게임을 잡으려고 한사람부터 게임에 넣어주는 구조이죠.
이제 큐가 무엇인지는 감이 잡히시나요? 그림으로 설명하면 다음과 같은 구조를 갖습니다.
연결 리스트랑 차이점을 잘 모르겠어요~라고 할 수도 있는데, 일반 연결 리스트와의 차이점은 삽입 삭제가 중간에서는 불가능하다 라는 점이 있습니다. 이 차이로 인해 쓰는 용도가 크게 달라지는 점도 유의해야합니다.
큐도 역시 배열과 연결 리스트를 이용해서 구현할 수 있는데, 배열을 이용한 큐부터 구현해보도록하겠습니다.
배열을 이용한 큐 구현
우선 순차 자료구조인 배열을 이용한 큐 구현입니다. 기본적인 선언이나 생성에 대한 설명에 있어서 스택과 비슷하기 때문에, 완전히 중복되는 부분은 제외하고 큐에 관한 부분만 설명하겠습니다.
큐 선언
#define QUEUE_SIZE 5
typedef char element;
typedef struct {
element queue[QUEUE_SIZE];
int front, rear;
}QueueType;
QueueType* createQueue() {
QueueType* Q;
Q = (QueueType*)malloc(sizeof(QueueType));
Q->front = -1;
Q->rear = -1;
return 0;
}큐에 들어갈 자료는 char형이고, 큐의 크기는 5입니다.
front와 rear는 각각 큐의 처음과 끝을 이야기 할건데 front는 일반적으로 배열 인덱스 [0]방향이고 rear는 인덱스 [4]방향입니다. 그래서 삽입은 rear로 삭제는 front위치에서 이루어질 예정입니다.
int isEmpty(QueueType* Q) {
if (Q->front == Q->rear) {
return 1;
}
return 0;
}
int isFull(QueueType* Q) {
if (Q->rear == QUEUE_SIZE - 1) {
return 1;
}
else {
return 0;
}
}이번에는 큐가 비었는지 가득 찼는지 검사하는 두 함수입니다. Empty조건은 front와 rear가 같은 경우 입니다. 즉, 초기화 상태인 -1, -1을 제외하고는 front와 rear가 같을 일이 없기 때문에 front와 rear가 같다면 현재 큐는 비어있는 상태를 의미합니다.
Full조건은 rear가 큐 사이즈와 같은지를 검사합니다. rear가 삽입 부분이기 때문에 rear와 큐 사이즈가 동일하다면 더 이상 삽일할 수가 없기에 가득찬 상태임을 의미합니다.
인큐 Enqueue
스택에서는 삽입을 푸시라고 했었습니다. 이처럼 큐에서는 삽입을 인큐라고 부릅니다. 인큐는 큐에 데이터를 삽입하는 것을 의미합니다.
void enQueue(QueueType* Q, element elem) {
if (isFull(Q)) {
return;
}
else {
Q->rear++;
Q->queue[Q->rear] = elem;
}
}인큐는 rear를 1증가시키고 해당 인덱스에 데이터를 집어넣습니다. 그림으로 표현하면 다음과 같습니다.
디큐 Dequeue
마찬가지로 큐에서의 삭제 연산을 디큐라고합니다. 근데 지금 우리가 하는 배열을 이용한 구현에서 디큐는 한가지 문제점을 띕니다. 우선 코드부터 확인하시죠.
void deQueue(QueueType* Q) {
if (isEmpty(Q)) {
return;
}
else {
Q->front++;
}
}삭제를 보시면 단순히 Q->front를 증가시켜 마치 삭제된 것 처럼 보입니다.
마지막 그림처럼 된다면 어떻게 될까요? 앞에 4칸을 삭제했지만 인덱스의 문제로 가득차있다 라는게 되어서 가득 찼다는 판정이 나옵니다. 이것을 해결하기 위해서는 삭제될 때마다 원소를 한 칸씩 앞으로 옮겨주면 됩니다.
하지만 배열을 이용한 구현에서의 원소 이동은 큐에 대해 과부하를 주기 때문에 그다지 좋은 선택사항은 아닙니다. 그래서 이를 연결 리스트로 구현하거나 자료구조적으로 해결하는데 그것이 바로 원형 큐입니다. 원형 큐에 대한 내용은 따로 다루기로 하겠습니다.
피크
스택에서 피크는 가장 꼭대기의 원소를 확인하는 거였죠. 큐에서의 피크는 front의 직전에 있는 원소를 확인하는 기능입니다. 결국 스택이든 큐든 팝 되면 삭제될, 디큐하면 삭제될 원소를 확인하는 것 입니다.
element peek(QueueType* Q) {
if (isEmpty(Q)) {
exit(1);
}
else {
return Q->queue[Q->front + 1];
}
}front에 1을 더하는 이유는 front 자체는 이전에 삭제된 원소이기 때문에 가장 앞의 원소는 front+1이기 때문입니다.
연결 리스트로 큐 구현
배열로 했을 때 큐의 사이즈와 원소 이동이라는 골치아픈 문제가 생겼었습니다. 이를 해결하는 방법 중 하나인 노드를 이용한 연결 리스트로 큐를 구현해보겠습니다. 연결 리스트를 주구장창 했기 때문에 바로 인큐 부터 들어가겠습니다.
인큐
void enQueue(LinkedQueueType* LQ, element elem) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = elem;
newNode->link = NULL;
if (LQ->front == NULL) { //큐가 비어있는 경우 새 노드가 front이자 rear가 된다
LQ->front = newNode;
LQ->rear = newNode;
}
else {
LQ->rear->link = newNode; //이전 마지막 노드였던 rear의 링크필드는 새 노드를 가리킨다.
LQ->rear = newNode; //그리고 rear는 새로 삽인한 노드가 됩니다.
}
}디큐
element deQueue(LinkedQueueType* LQ) {
//oldNode는 삭제할 노드입니다. 큐는 front부터 삭제되므로,
//oldNode는 front를 가리키도록 합니다.
QueueNode* oldNode = LQ->front;
if (isEmpty(LQ)) {
return 0;
}
else {
//노드가 삭제되면 다음 노드가 front가 되므로 front를 재설정 합니다.
LQ->front = LQ->front->link;
if (LQ->front == NULL) { //이 경우는 삭제한 노드가 큐의 하나 뿐인 노드인 경우입니다.
LQ->rear = NULL; //하나뿐인 노드를 삭제했으므로 당연히 rear도 없습니다.
}
free(oldNode);
}
}피크
피크는 그냥 front의 data를 반환하기만 하면 됩니다.
element peek(LinkedQueueType* LQ) {
element elem;
if (isEmpty(LQ)) {
return 0;
}
else {
elem = LQ->front->data;
return elem;
}
}