Chapter 07. 큐(Queue)
큐(Queue) 는 앞서 설명한 스택과 반대로 먼저 들어간 데이터가 먼저 나오는 선입선출(FIFO) 방식의 구조이다.
큐의 ADT 정의
- void QueueInit(Queue * pq);
- 큐의 초기화를 진행한다.
- 큐 생성 후 제일 먼저 호출되어야 하는 함수이다.
- int QIsEmpty(Queue * pq);
- 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.
- void Enqueue(Queue * pq, Data data);
- 큐에 데이터를 저장한다.
- 매개변수 data로 전달된 값을 저장한다.
- void Dequeue(Queue * pq);
- 저장순서가 가장 앞선 데이터를 삭제한다.
- 삭제된 데이터는 반환된다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
- Data QPeek(Queue * pq);
- 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
큐의 배열 기반 구현
F를 큐의 머리, R을 큐의 꼬리를 가리키는 변수를 만들고, enqueue 연산을 할 때 R이 그 다음 칸을 가리키게 하고 새 데이터를 저장하며, dequeue 연산을 할 때 F를 참조하여 F 가 가리키는 데이터를 삭제하면 된다고 생각할 수 있는데
위의 그림을 참조해보면 dequeue 연산을 할 때 용량이 1씩 줄어드는 문제와, 연산이 완료되면 F와 R을 하나씩 옮기는데 비용이 굉장히 많이 든다는 문제를 겪는다.
따라서 다른 방법으로 구현해야하는데 이때 원형 큐가 나오게 된다.
위의 그림과 같이 원형큐로 만들면 위의 2가지 문제점을 모두 해결할 수 있다.
#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"
// 큐를 초기화하는 함수, front가 머리, rear 가 꼬리를 뜻하고 0으로 초기화해준다.
void QueueInit(Queue * pq)
{
pq->front = 0;
pq->rear = 0;
}
// 큐가 비어있는지 확인하는 함수, front와 rear 의 위치가 같으면 비어있음
int QIsEmpty(Queue * pq)
{
if(pq->front == pq->rear)
return TRUE;
else
return FALSE;
}
// 큐의 다음 위치에 해당하는 인덱스 값 반환
int NextPosIdx(int pos)
{
if(pos == QUE_LEN-1) // pos가 큐의 길이 -1 이면 0으로 돌아감, 즉 회전을 시켜준다.
return 0;
else
return pos+1;
}
// Enqueue 기능을 해주는 함수(큐에 데이터를 넣어줌)
void Enqueue(Queue * pq, Data data)
{
if(NextPosIdx(pq->rear) == pq->front)
{
printf("Queue Memory Error!");
exit(-1);
}
pq->rear = NextPosIdx(pq->rear); // rear을 한 칸 이동
pq->queArr[pq->rear] = data; // rear 이 가리키는 곳에 데이터 저장
}
// Dequeue 기능을 해주는 함수(큐에서 데이터를 뺌)
Data Dequeue(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
pq->front = NextPosIdx(pq->front); // front를 한 칸 이동
return pq->queArr[pq->front]; // front가 가리키는 데이터 반환
}
// QPeek 기능을 해주는 함수(front 위치에 있는 값을 반환함)
Data QPeek(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->queArr[NextPosIdx(pq->front)];
}위의 코드는 원형큐를 배열을 이용하여 구현한 코드이다.
큐의 연결 리스트 기반 구현
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"
// 큐를 초기화하는 함수로 front 와 rear을 NULL값으로 초기화함
void QueueInit(Queue * pq)
{
pq->front = NULL;
pq->rear = NULL;
}
// 큐가 비어있는지 확인하는 함수
int QIsEmpty(Queue * pq)
{
if(pq->front == NULL)
return TRUE;
else
return FALSE;
}
// Enqueue 기능을 구현한 함수
void Enqueue(Queue * pq, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->next = NULL;
newNode->data = data;
if(QIsEmpty(pq)) // 첫 번쨰 노드의 추가라면,
{
pq->front = newNode; // front가 새 노드를 가리키게 하고,
pq->rear = newNode; // rear도 새 노드를 가리키게 한다.
}
else // 두 번쨰 이후의 노드 추가하면
{
pq->rear->next = newNode; // 마지막 노드가 새 노드를 가리키게 하고,
pq->rear = newNode; // rear가 새 노드를 가리키게 한다.
}
}
// Dequeue 기능을 구현한 함수
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; // 삭제할 노드의 다음 노드를 front가 가리킴
free(delNode);
return retData;
}
// QPeek 기능을 구현한 함수, front가 가리키고 있는 data를 반환함
Data QPeek(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->front->data;
}Enqueue 함수의 경우 첫 번째 노드의 추가와 두 번째 이후의 노드 추가 2가지로 나뉘게 되는데 이는 첫번째 노드를 추가할 때 front와 rear 모두 새 노드를 가리키게 해야되고 그 이후에 노드를 추가할 때에는 마지막 노드가 새 노드를 가리키게 하고, rear 가 새 노드를 가리키게 하는 방식에서 차이가 생기기 때문이다.
Dequeue 함수의 경우 두 가지로 나눌 필요가 없다
- F가 다음 노드를 가리키게 한다.
- F가 이전에 가리키던 노드를 소멸시킨다.
위의 과정만 지키면 되기 때문이다.
덱(Deque)의 이해와 구현
“덱”은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺼 수 있는 자료구조이다.
덱의 ADT 정의
- void DequeInit(Deque * pdeq);
- 덱의 초기화를 진행한다.
- 덱 생성 후 제일 먼저 호출되어야 하는 함수이다.
- int DQIsEmpty(Deque * pdeq);
- 덱이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.
- void DQAddFirst(Deque * pdeq, Data data);
- 덱의 머리에 데이터를 저장한다. data로 전달된 값을 저장한다.
- void DQAddLast(Deque * pdeq, Data data);
- 덱의 꼬리에 데이터를 저장한다. data로 전달된 값을 저장한다.
- Data DQRemoveFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 반환 및 소멸한다.
- Data DQRemoveLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 반환 및 소멸한다.
- Data DQGetFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 소멸하지 않고 반환한다.
- Data DQGetLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환한다.
deque는 구현할 때 deque의 특성 상 양방향 연결 리스트를 기반으로 구현해야한다.
초보개발자입니당