선형 큐 (구조체로 구현)
선형 큐 기본 설명
우선은 큐가 동작하는 모습을 이해하기 위한 코드의 설명을 하고 마지막에 스택을 구현했을 때처럼 직접 입력하는 코드는 따로 보이겠다.
밑의 그림을 보면 큐의 초기 상태는 front와 rear가 둘 다 -1에 있을 때다.
큐는 스택과 달리 먼저 들어온 것이 먼저 나가는 형태다. (FIFO, first in first out)
선형 큐의 동작 원리의 이해를 돕기 위해 몇 가지 동작을 해보겠다.
기본 코드는 다음과 같이 설정한다.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
typedef struct Queue{
int front;
int rear;
int data[MAX];
} Queue;
[-1] [0] [1] [2] [3] [4]
| front, rear | (NULL) | (NULL) | (NULL) | (NULL) | (NULL) |
enqueue 함수는 큐에 데이터를 삽입한다.
enqueue 함수
// 선형 큐에 데이터 삽입
void enqueue(Queue *q, int item)
{
if (full(q)) {
printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
return;
}
q->data[ ++(q->rear) ] = item;
}동작 예: enqueue(q, 5), enqueue(q,10)
[-1] [0] [1] [2] [3] [4]
| front | 5 | rear/10 | (NULL) | (NULL) | (NULL) |
dequeue 함수는 큐에서 데이터를 제거한다(front를 1 이동시킨다).
dequeue 함수
// 선형 큐에서 데이터 제거
int dequeue(Queue *q)
{
if (empty(q)) {
printf("큐가 공백상태입니다. 데이터 제거를 취소합니다.\n");
return -1;
}
int item = q->data[ ++(q->front) ];
return item;
}동작 예: dequeue(q)
[-1] [0] [1] [2] [3] [4]
| (NULL) | front | rear/10 | (NULL) | (NULL) | (NULL) |
선형 큐의 문제점까지 미리 얘기하자면, enqueue와 dequeue의 동작을 반복하다 보면 큐가 아래 같은 형태가 된다.
q->data[4]에 들어갈 숫자는 25라 하자.
[-1] [0] [1] [2] [3] [4]
| (NULL) | (NULL) | (NULL) | (NULL) | front | rear/25 |
선형 큐의 단점이 보인다. 분명 큐에는 비어있는 공간이 존재하지만 선형 큐는 이 형태를 큐가 꽉 찼다고 생각해서 공간의 낭비가 발생한다. 이러한 단점을 보완한 큐의 형태가 바로 원형 큐(circular Queue)다. 원형 큐에 대해서는 따로 작성하겠다.
이어서 선형 큐의 상태를 보여줄 print_queue 함수와 full, empty 함수도 작성한다.
print_queue, full, empty 함수
void print_queue(Queue *q)
{
for (int i = 0; i<MAX; i++) {
if (i <= q->front || i> q->rear)
printf(" | ");
else
printf("%d | ", q->data[i]);
}
printf("\n");
}
int full(Queue *q)
{
if (q->rear == MAX - 1 )
return 1;
else
return 0;
}
int empty(Queue *q)
{
if ( q->front == q->rear ) //front==rear이면 빈 상태
return 1;
else
return 0;
}
메인 함수까지 작성을 해서 큐의 동작 상태를 확인해보자.
int main(void)
{
int item = 0;
Queue* q = (Queue *)malloc(sizeof(Queue));
init_queue(q);
dequeue(q);
printf("\n");
enqueue(q, 10); print_queue(q);
enqueue(q, 20); print_queue(q);
enqueue(q, 30); print_queue(q);
enqueue(q, 40); print_queue(q);
enqueue(q, 50); print_queue(q);
printf("\n");
enqueue(q, 60);
printf("\n");
item = dequeue(q); print_queue(q);
item = dequeue(q); print_queue(q);
item = dequeue(q); print_queue(q);
item = dequeue(q); print_queue(q);
item = dequeue(q); print_queue(q);
printf("\n");
item = dequeue(q);
return 0;
}선형 큐의 동작 상태 코드 실행 결과
큐가 공백상태입니다. 데이터 제거를 취소합니다.
10 | | | | |
10 | 20 | | | |
10 | 20 | 30 | | |
10 | 20 | 30 | 40 | |
10 | 20 | 30 | 40 | 50 |
큐가 포화상태입니다. 데이터 삽입을 취소합니다.
| 20 | 30 | 40 | 50 |
| | 30 | 40 | 50 |
| | | 40 | 50 |
| | | | 50 |
| | | | |
큐가 공백상태입니다. 데이터 제거를 취소합니다.
선형 큐 직접 입력 코드 구현
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
typedef struct { // 선형 큐 타입
int front;
int rear;
int data[MAX];
} Queue;
// 선형 큐 초기화
void InitQueue(Queue *queue)
{
queue->rear = -1;
queue->front = -1;
}
int full(Queue *queue)
{
return (queue->rear == MAX-1);
}
int empty(Queue *queue)
{
return (queue->front == queue->rear); //front==rear이면 빈 상태
}
// 선형 큐에 데이터 삽입
void enqueue(Queue *queue, int item)
{
if (full(queue)) {
printf("큐가 포화상태입니다. 데이터 삽입을 취소합니다.\n");
return;
}
queue->data[++(queue->rear)] = item;
}
// 선형 큐에서 데이터 제거
int dequeue(Queue *queue)
{
if (empty(queue)) {
return -1;
}
int num = queue->data[++(queue->front)];
return num;
}
int main(void)
{
Queue *queue = (Queue*)malloc(sizeof(Queue));
InitQueue(queue);
char Get_Com[10];
int N,pushnum;
scanf("%d",&N);
for(int i=0;i<N;i++)
{
scanf("%s",Get_Com);
if(strcmp(Get_Com,"enqueue")==0)
{
scanf("%d",&pushnum);
enqueue(queue,pushnum);
}
else if(strcmp(Get_Com,"dequeue")==0)
printf("%d\n",dequeue(queue));
else if(strcmp(Get_Com,"full")==0)
printf("%d\n",full(queue));
else if(strcmp(Get_Com,"empty")==0)
printf("%d\n",empty(queue));
}
return 0;
}느낀 점
선형 큐는 단점이 확실하기 때문에, 원형 큐를 쓰는게 일반적이다. 그래도 알고는 있어야한다고 생각해서 구현을 해봤고, 혹시 문제에서 선형 큐를 요구할 수도..? 그냥 혹시 모르니 일단 알고는 있어야 하니까 구현해봤다.