-
큐
먼저 들어간 데이터가 먼저 나옴, FIFO(First In First Out), 선입선출(先入先出)
-
큐의 주요 기능: 삽입과 제거
큐의 가장 앞 요소를 전단(Front), 마지막 요소를 후단(Rear)라고 부름
큐는 삽입(Enqueue)은 후단, 제거(Dequeue)는 전단에서 수행
-
끝은 새로운 시작이다: 순환 큐
순환 큐를 소개합니다.
위의 그림과 같은 방법으로 큐를 만든다면 제거(Dequeue)가 될 때마다 나머지 요소를 앞으로 이동해야하는 비용이 필요하다
그래서 전단을 가리키는 변수를 도입하여 배열의 요소를 변경하는 대신 변경된 전단의 위치만 관리할 수 있다. 요소들의 이동에 대한 부하는 해결할 수 있지만 요소를 제거하고나서 전단의 앞의 요소를 사용하지 못하여 용량이 줄어드는 문제가 생긴다
그래서 시작(Front)와 끝(Rear)를 연결하여 사용하지 못하는 공간에 대한 문제를 풀 수 있다.
이렇게 시작과 끝을 연결하여 순환하도록 고안된 큐를 순환 큐(Circular Queue)라고 부른다
비어 있거나 또는 가득 차 있거나
순환 큐는 비어 있는 상태와 가득 차 있는 상태를 구분할 수가 없다.
일반적으로 큐 배열을 생성할 때 실제 용량보다 1만큼 더 크게 만들어 전단과 후단 사이를 비워 비어있거나 가득 차 있는 상태를 나타낸다. 이렇게 하면 비어있을 때는 전단과 후단이 같은 곳을 가리키고(Front == Rear), 가득 차있을 때는 후단이 전단보다 1작은 값(Rear-1 == Front)이 되게 된다.
순환 큐 구현하기
-
데이터 구조체(NODE)
type int ElemnetType;
typedef struct tagNode
{
ElementType data;
} NODE;
-
순환 큐 구조체
typedef strcut tagCircularQueue
{
int capacity; // 용량
int front; // 전단 인덱스
int rear; // 후단 인덱스
NODE* node; // 노드 배열
}CircularQueue;
-
순환 큐의 생성
void CQ_createQueue(CircularQueue** queue, int capacity)
{
// 큐를 생성
(*queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
// 입력된 capacity+1만큼 노드 할당
(*queue)->node = (NODE*)malloc(sizeof(NODE) * (capacity+1));
(*queue)->capacity = capacity; // 큐가 수용할 실제 용량 저장
(*queue)->front = 0;
(*queue)->rear = 0;
}
-
순환 큐의 소멸
void CQ_destroyQueue(CircularQueue* queue)
{
free(queue->node);
free(queue);
}
-
삽입(Enqueue) 연산
void CQ_enqueue(CircularQueue* queue, ElementType data)
{
int position = 0;
if( queue->rear == queue->capacity+1 )
{
queue->rear = 0;
position = 0;
}
else
{
position = queue->rear++;
}
queue->node[position].data = data;
}
-
제거(Dequeue) 연산
ElementType CQ_dequeue(circularQueue* queue)
{
int position = queue->front;
if( queue->front == queue->capacity )
queue->front = 0;
else
queue->front++;
return queue->node[position].data;
}
-
공백 상태 확인
int CQ_isEmpty(CircularQueue* queue)
{
return (queue->front == queue->rear);
}
-
포화 상태 확인
int CQ_isFull(CircularQueue* queue)
{
if( queue->front < queue->rear )
return (queue->rear - queue->front) == queue->capacity;
else
return (queue->rear+1) == queue->front;
}
순환 큐 예제 프로그램
- 예제 CircularQueue.h
-
|
#ifndef CIRCULARQUEUE_H__ #define CIRCULARQUEUE_H__
#include <stdio.h> #include <stdlib.h>
typedef int ElementType;
typedef struct tagNode { ElementType data; }NODE;
typedef struct tagCircularQueue { int capacity; int front; int rear;
NODE* node; }CircularQueue;
void CQ_createQueue(CircularQueue** queue, int capacity); void CQ_destroyQueue(CircularQueue* queue); void CQ_enqueue(CircularQueue* queue, ElementType data); ElementType CQ_dequeue(CircularQueue* queue); int CQ_getSize(CircularQueue* queue); int CQ_isEmpty(CircularQueue* queue); int CQ_isFull(CircularQueue* queue);
#endif |
- 예제 CircularQueue.c
|
#include "CircularQueue.h"
void CQ_createQueue(CircularQueue** queue, int capacity) { // 큐 생성 (*queue) = (CircularQueue*)malloc(sizeof(CircularQueue)); // capacity+1 만큼 노드 생성 (*queue)->node = (NODE*)malloc(sizeof(NODE)*(capacity+1));
(*queue)->capacity = capacity; (*queue)->rear = 0; (*queue)->front = 0; } void CQ_destroyQueue(CircularQueue* queue) { free(queue->node); free(queue); } void CQ_enqueue(CircularQueue* queue, ElementType data) { int position = 0;
if( queue->rear == queue->capacity+1 ) { queue->rear = 0; position = 0; } else { position = queue->rear++; } queue->node[position].data = data; } ElementType CQ_dequeue(CircularQueue* queue) { int position = queue->front;
if( queue->front == queue->capacity ) { queue->front = 0; } else { queue->front++; } return queue->node[position].data; } int CQ_getSize(CircularQueue* queue) { if( queue->front <= queue->rear ) { return queue->rear - queue->front; } else { return queue->rear + (queue->capacity+queue->front)+1; } } int CQ_isEmpty(CircularQueue* queue) { return (queue->front == queue->rear); } int CQ_isFull(CircularQueue* queue) { if( queue->front < queue->rear ) { return (queue->rear - queue->front) == queue->capacity; } else { return (queue->rear + 1) == queue->front; } } |
- 예제 main.c
|
#include "CircularQueue.h"
void main() { int i = 100; CircularQueue* queue;
CQ_createQueue(&queue, 10);
CQ_enqueue(queue,1); CQ_enqueue(queue,2); CQ_enqueue(queue,3); CQ_enqueue(queue,4); CQ_enqueue(queue,5);
printf("Dequeue : %d, front : %d, rear : %d\n", CQ_dequeue(queue), queue->front, queue->rear); printf("Dequeue : %d, front : %d, rear : %d\n", CQ_dequeue(queue), queue->front, queue->rear); printf("Dequeue : %d, front : %d, rear : %d\n", CQ_dequeue(queue), queue->front, queue->rear);
while( CQ_isFull(queue) == 0 ) { CQ_enqueue(queue, i++); }
printf("capacity : %d, size : %d\n\n", queue->capacity, CQ_getSize(queue));
while(CQ_isEmpty(queue) == 0) { printf("Dequeue : %d, front : %d, rear : %d\n", CQ_dequeue(queue), queue->front, queue->rear); }
CQ_destroyQueue(queue); } |
-
링크드 큐
순환 큐 vs 링크드 큐
링크드 큐의 각 노드는 앞 노드에 대한 포인터를 이용해 구성되어 있기 때문에, 삽입은 새 노드의 포인터에 후단을 연결하고 제거는 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두어 들이는 것으로 구현이 될 수 있다
링크드 큐는 큐가 가득 차 있는 상태인지 확인할 필요가 없다
링크드 큐 구현하기
-
링크드 큐 노드
typedef struct tagNode
{
char* data;
struct tagNode* next;
}NODE;
-
링크드 큐 구조체
typedef struct tagLinkedQueue
{
NODE* front;
NODE* rear;
int count;
}LinkedQueue;
-
링크드 큐 생성
void LQ_createQueue(LinkedQueue** queue)
{
(*queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));
(*queue)->front = NULL;
(*queue)->rear = NULL;
(*queue)->count = 0;
}
-
링크드 큐 소멸
void LQ_destroyQueue(LinkedQueue* queue)
{
while( !LQ_isEmpty(queue) )
{
NODE* pop = LQ_dequeue(&queue);
LQ_destroyNode(pop);
}
// 해제
free(queue);
}
-
삽입(Enqueue) 연산
void LQ_endqueue(LinkedQueue* queue, NODE* newNode)
{
if( queue->front == NULL )
{
queue->front = newNode;
queue->rear = newNode;
queue->count++;
}
else
{
queue->rear->next = newNode;
queue->rear = newNode;
queue->count++;
}
}
-
제거(dequeue) 연산
NODE* LQ_dequeue(LinkedQueue* queue)
{
// LQ_dequeue() 함수가 반환할 최상위 노드
NODE* front = queue->front;
if( queue->front->next == NULL )
{
queue->front = NULL;
queue->rear = NULL;
}
else
{
queue->front = queue->front->next;
}
queue->count--;
return front;
}
링크드 큐 예제 프로그램
- 예제 LinkedQueue.h
-
|
#ifndef _LINKEDQUEUE_H__ #define _LINKEDQUEUE_H__
#include <stdio.h> #include <stdlib.h> #include <string.h>
typedef struct tagNode { char* data; struct tagNode* next; }NODE;
typedef struct tagLinkedQueue { NODE* front; NODE* rear; int count; }LinkedQueue;
void LQ_createQueue(LinkedQueue** queue); void LQ_destroyQueue(LinkedQueue* queue);
NODE* LQ_createNode(char* data); void LQ_destroyNode(NODE* node);
void LQ_enqueue(LinkedQueue* queue, NODE* newNode); NODE* LQ_dequeue(LinkedQueue* queue);
int LQ_isEmpty(LinkedQueue* queue);
#endif |
- 예제 LinkedQueue.c
|
#include "LinkedQueue.h"
void LQ_createQueue(LinkedQueue** queue) { (*queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue)); (*queue)->front = NULL; (*queue)->rear = NULL; (*queue)->count = 0; } void LQ_destroyQueue(LinkedQueue* queue) { while( !LQ_isEmpty(queue) ) { NODE* pop = LQ_dequeue(queue); LQ_destroyNode(pop); } free(queue); }
NODE* LQ_createNode(char* data) { NODE* newNode = (NODE*)malloc(sizeof(NODE)); newNode->data = (char*)malloc(strlen(data)+1);
// 데이터 저장 strcpy(newNode->data, data); newNode->next = NULL;
return newNode; } void LQ_destroyNode(NODE* node) { free(node->data); free(node); }
void LQ_enqueue(LinkedQueue* queue, NODE* newNode) { if( queue->front == NULL ) { queue->front = newNode; queue->rear = newNode; } else { queue->rear->next = newNode; queue->rear = newNode; } queue->count++; } NODE* LQ_dequeue(LinkedQueue* queue) { // LQ_dequeue() 함수가 반환할 최상위 노드 NODE* front = queue->front;
if( queue->front->next == NULL ) { queue->front = NULL; queue->rear = NULL; } else { queue->front = queue->front->next; } queue->count--;
return front; }
int LQ_isEmpty(LinkedQueue* queue) { return (queue->front == NULL); } |
- 예제 main.c
|
#include "LinkedQueue.h"
void main() { NODE* pop; LinkedQueue* queue;
LQ_createQueue(&queue);
LQ_enqueue(queue, LQ_createNode("abc")); LQ_enqueue(queue, LQ_createNode("def")); LQ_enqueue(queue, LQ_createNode("efg")); LQ_enqueue(queue, LQ_createNode("hij"));
printf("queue size : %d\n", queue->count);
while( LQ_isEmpty(queue) == 0 ) { pop = LQ_dequeue(queue); printf("Dequeue: %s\n", pop->data); LQ_destroyNode(pop); } LQ_destroyQueue(queue); } |