Queue는 자료구조 중의 하나로, 먼저 입력되는 정보가 먼저 나오는 형태의 구조를 지닙니다.
이를 First in First Out 이라 하고, 앞 글자를 따서 FIFO 라 부릅니다.
자료구조로서의 정의가 있기 전에, queue 라는 단어는 "줄 지어 서있는" 것을 의미하는데요
위 사진 처럼 인기 있는 레스토랑에서 식사를 하려고 줄을 서면, 먼저 온 사람이 먼저 식당에 들어가게 됩니다.
자료구조로서의 큐는 그런 특성을 본따서 지은 이름이 아닐까 생각되네요.
큐가 지원하는 메소드는 다음과 같습니다.
-
Enqueue : Queue의 front(맨 앞)에 값을 넣는 것을 의미합니다.
-
Dequeue : Queue의 Back(맨 뒤)에서 값을 빼는 것을 의미합니다.
큐도 스택과 같이 Array와 LL으로 구현할 수 있는데요,
Array의 경우엔 동적으로 메모리의 크기가 커질 수 없기 때문에
처음 선언할 때 최대 size를 지정해주어야 합니다.
-
ArrayQueue
-
처음 Queue를 선언할 때 최대 Size를 주게끔 선언
-
Circular Queue 형식으로 구성, index가 maxSize를 초과할 시 나머지 연산으로 index가 초기화됨.
-
-
LLQueue (Linked List Queue)
-
node를 생성하여 Linked List 형태로 구현, node는 본인 다음에 들어온 node를 가르킴.
-
구현 예시는 Array Queue랑 LLQueue를 모두 소개하겠습니다.
Array Queue
Queue Data Structure
typedef struct Queue_t{
int * data;
int front;
int rear;
int size;
int maxSize;
} Queue;Array Queue는 Queue Struc는 다음과 같이 정의하였습니다.
실제 데이터가 존재하는 배열은 *data로 가리키고 있으며,
포인터를 저장하므로 그 최대 크기를 따로 maxSize로 저장해야 합니다.
현재 맨 앞에있는 요소가 무엇인가를 나타내는 것이 front
현재 맨 뒤에있는 요소가 무엇인가를 나타내는 것이 rear
현재 크기에 해당하는 값이 size입니다.
Create Array Queue
Queue * CreateQueue(int maxSize){
Queue * newQueue = (Queue *)malloc(sizeof(Queue));
if(newQueue==NULL){
printf("Error raised while allocating memory in CreateQueue - newQueue");
return NULL;
}
int * data = (int *)malloc(sizeof(int) * maxSize);
if(data == NULL){
printf("Error raised while allocating memory in CreateQueue - data");
return NULL;
}
newQueue->data = data;
newQueue->front = 0;
newQueue->rear = 0;
newQueue->size = 0;
newQueue->maxSize = maxSize;
return newQueue;
}큐를 초기화 하는 함수입니다. 입력으로는 배열의 최대 크기를 전달해줍니다.
맨 처음 Queue Struct 에 대한 메모리를 할당해주고,
maxSize 크기에 해당하는 배열에 대한 메모리를 할당해준 후
Queue에 해당 배열을 가리키는 포인터를 Queue->data에 지정해줍니다.
그리고 나머지 값들은 초기값을 지정합니다.
Enqueue
void Enqueue(Queue * queue, int value){
if(queue->size == queue->maxSize){
printf("Queue is full! so you cannot push");
return;
}
queue->data[queue->rear++] = value;
queue->rear %= queue->maxSize;
queue->size++;
}큐에 넣는 작업입니다. 넣으려는 큐의 포인터와 값이 필요합니다.
큐가 꽉 찼는데 넣는 건 맨 앞에있는 값에 덮어씌우는 꼴이 되므로 못하게 막습니다.
현재 맨 끝을 가리키는 인덱스에 값을 할당하고, 모듈러 연산을 통해 인덱스가 넘치는 것을 방지합니다.
그 후 현재 큐의 크기를 1 늘려줍니다.
Dequeue
int Dequeue(Queue * queue){
if(queue->size == 0){
printf("Queue is Empty, so you cannot Pop from it\n");
return -44444; // instead raise Error
}
int ret = queue->data[queue->front++];
queue->front %= queue->maxSize;
queue->size--;
return ret;
}큐에서 빼는 작업입니다. 빼려는 큐를 입력해야 합니다.
만약 큐에 아무것도 없다면 못빼게 해야겠죠.
큐에서 뺐다면, 해당 값을 리턴할 수 있게 먼저 참조한 후,
queue->front 값을 1 추가하고 모듈러 연산을 수행하여 다음 인덱스로 이동시킵니다.
그 후 큐의 사이즈를 1 줄입니다.
TraverseQueue
void TraverseQueue(Queue *queue){
printf("Size of this Queue : %d\n", queue->size);
printf("Queue->front : %d, Queue->rear : %d\n", queue->front, queue->rear);
if(queue->rear >= queue->front){
for(int i = queue->front; i <queue->rear; i++){
printf("%d ", queue->data[i]);
}
}
else{
for(int i = queue->front; i < queue->maxSize; i++){
printf("%d ", queue->data[i]);
}
for(int i = 0; i < queue->rear; i++){
printf("%d ", queue->data[i]);
}
}
printf("\n");
}이건 큐에 있는 요소를 한번 훑는 것인데요
front가 rear 보다 인덱스가 작으면 그냥 쭉 훓으면 되는데
rear가 작으면 front에서 끝까지 갔다가 다시 처음으로 돌아와서 rear 까지 스캔해야 합니다.
배열로 구현된 큐는 Circular Queue 임을 항상 잊지 마세요!
Linked List Queue
Node, Queue
typedef struct node_t{
int data;
struct node_t * next;
} node;
typedef struct Queue_t{
node *front;
node *rear;
int size;
} Queue;링크드 리스트의 개별 요소가 되는 node를 정의하고, 큐를 정의합니다.
링크드 리스트를 사용하면 고정 크기가 아닌 임의의 크기의 큐를 정의하여 사용할 수 있습니다.
Create Queue
Queue * CreateQueue(){
Queue *newQueue = (Queue *)malloc(sizeof(Queue));
if(newQueue == NULL){
printf("Problem Occured when allocating memory in CreateQueue - newQueue");
return NULL;
}
newQueue->front = NULL;
newQueue->rear = NULL;
newQueue->size = 0;
}큐를 생성하는 것도 단순히 큐에 대한 구조체 메모리만 할당해주고, 나머지 값은 초기화해줍니다.
Create Node
node * CreateNode(int data){
node * newNode = (node *)malloc(sizeof(node));
if(newNode == NULL){
printf("Problem Occured when allocating memory in CreateNode - newNode");
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}큐에 값을 입력하려면 노드를 생성해서 연결해주어야 하므로, 노드를 생성하는 함수도 만들어 줍니다.
Enqueue
void Enqueue(Queue * queue, int data){
node * newnode = CreateNode(data);
if(newnode == NULL) return;
if(queue->rear == NULL){
queue->front = newnode;
queue->rear = newnode;
}
else{
queue->rear->next = newnode;
queue->rear = newnode;
}
queue->size++;
}큐에 값을 넣어줍니다. node를 생성한 후, 맨 뒤에 넣어줍니다.
만약 아무 값이 없는 경우엔 front 혹은 rear가 null 일 것이므로, 이를 체크해서 지정해줍니다.
node간 가리키는 방향은, 이전 노드가 새로 들어온 노드를 가르킨다고 생각하시면 됩니다.
Dequeue
int Dequeue(Queue * queue){
if(queue->size == 0){
printf("There is No Item to dequeue in queue\n");
return -44444;
}
int ret = queue->front->data;
node* shouldfree = queue->front;
if(queue->size == 1){
queue->front = NULL;
queue->rear = NULL;
}
else queue->front = queue->front->next;
free(shouldfree);
queue->size--;
return ret;
}큐에서 값을 하나 빼줍니다.
아무것도 없을 때 빼면 안될 것입니다.
만약 큐의 크기가 1이였으면, 하나 밖에 없으니까 빼면 아무것도 없게 되어야 합니다.
고로 front 와 rear가 가르키는 포인터를 모두 NULL 로 바꾸어 주어야 합니다.
그 외의 경우엔 현재 front 노드를, 맨 앞에 있는 녀석이 가르키고 있던 노드로 바꾸어줍니다.
동적으로 할당된 메모리도 free 해주어야 memory leakage를 방지할 수 있습니다.
Traverse Queue
void TraverseQueue(Queue *queue){
node * point = queue->front;
printf("size of queue : %d\n", queue->size);
while(point != NULL){
printf("%d ", point->data);
point = point->next;
}
printf("\n");
}큐를 앞에서부터 뒤까지 쭉 훑는 것입니다.
NULL이 나올 때 까지 포인터를 이동해주면서 값을 찾아갑니다.
CPP STL - Queue
STL에 이미 큐가 구현되어있기 때문에,
C++을 사용하신다면 굳이 구현하지 마시고 꼭 stl을 사용합시다.
en.cppreference.com/w/cpp/container/stack
std::stack - cppreference.com
template< class T, class Container = std::deque > class stack; The std::stack class is a container adapter that gives the programmer the functionality of a stack - specifically, a LIFO (last-in, first-out) data structure. The class template act
en.cppreference.com
여기까지 큐에 대해서 알아보고 구현해보았습니다.
다음 자료구조는 BST로 만나뵙겠습니다.
'자료구조 & 알고리즘 > 자료구조' 카테고리의 다른 글
| [6] Heap (0) | 2020.10.28 |
|---|---|
| [5] 이진 탐색 트리 (2) | 2020.10.28 |
| [3] 스택 (2) | 2020.10.20 |
| [2] Segment Tree (Lazy Propagation) (0) | 2020.09.28 |
| [1] Segment Tree (2) | 2020.09.13 |
댓글