이 글은 이소연 교수님의 자료구조 강의를 듣고 정리한 내용입니다.
큐(Queue)이란?
1️⃣ Queue의 정의
우리가 매표소에서 표를 사기 위해 줄을 설 때를 생각해보자. 먼저 도착한 사람이 먼저 티켓을 구매하고, 새로 도착한 사람은 줄의 가장 끝에 서서 차례를 기다리게 된다. 다른 예시로는 우리가 여러 문서를 인쇄할 때, 요청한 순서대로 출력되는 것을 알 수 있다. 이렇게 가장 먼저 입력되는 것이 먼저 출력되는 구조를 Queue라고 말할 수 있다.
사전적인 의미로 설명하자면, Queue는 데이터를 한쪽 끝(front)에서는 삽입(enqueue) / 다른 한쪽 끝에서는 삭제(dequeue)할 수 있는 선형 자료구조이고, 이는 가장 먼저 들어간 데이터가 가장 먼저 나오는 선입선출(First In, First Out, FIFO) 구조를 따른다.
아래의 그림은 front/rear의 주소를 계속 증가시키면서 데이터를 입력받고 출력하는 Linear Queue에 대한 구조로, 가장 간단한 Queue의 구조이다.
2️⃣ Queue의 추상 데이터 타입
Queue의 구성 요소와 필요한 연산들을 추상 데이터 타입을 통해 다음과 같이 정리할 수 있다.
- 객체 : n개의 원소들의 선형 리스트
- 연산
create(): Queue의 생성is_empty(): Queue가 비어있는지 확인is_full(): Queue가 가득 찼는지 확인 (정적 구현 시)enqueue(item): Queue의 rear에 데이터를 추가dequeue(): Queue의 rear에서 데이터를 제거하고 반환peek(): 삭제하지 않고 rear의 데이터를 반환
3️⃣ Queue의 변형
앞서 Linear Queue는 간단한 구조를 통해 효율적으로 선입선출 방식을 구현할 수 있지만 단점이 있다. 뒤에서 설명하겠지만 정적으로 Queue를 구현하면 고정된 크기를 가지게 되는데, 이때 front/rear는 계속해서 증가하여 마지막 주소에 도달하게 되면 앞부분이 비어있더라도 사용하지 못한다는 한계가 있다.
이런 한계를 개선하고 다양한 문제에서 활용할 수 있도록 기존 Queue를 변형한 여러가지 구조가 존재한다.
- 원형 큐(Circular Queue)
- 배열의 끝과 처음을 연결한 원형 구조
- 배열에서 앞의 비어있는 공간도 사용할 수 있어 공간을 효율적으로 사용할 수 있다.
배열 최대 크기 - 1개까지 데이터를 저장할 수 있다.
(front == rear 인 경우 empty를 의미하기 때문에 이를 방지하기 위함)
아래 그림에서 Queue의 3번째 상태(Full Queue)를 보면, 0번 주소에는 데이터가 없는 것을 볼 수 있다. 이때 0번 주소에 데이터를 삽입하게 되면, front/rear 모두 0번 주소를 가리키게 되며 Queue의 1번째 상태(Empty Queue)와 동일한 주소값을 가지게 된다. 따라서 Circular Queue에서는 Empty/Full 상태를 구분하기 위해
주어진 크기 - 1개까지만 데이터를 저장한다.
- 데크(Deque, Double-ended queue )
- Queue의 양 끝(front/rear)에서 각각 삽입/삭제 연산 수행이 가능한 방식
- 동적 방식 구현이 필요
아래 그림과 같이 front / rear 모든 위치에서 삽입과 삭제 연산을 수행하는 것을 알 수있다.
- 우선순위 큐(Priority Queue)
- 정해진 기준에 따라 요소에 우선순위를 할당하고,
삽입되는 순서가 아닌 우선순위에 따라 삭제할 요소를 결정하는 방식 - 선형 자료구조(List)가 아닌 비선형 자료구조(Tree)를 활용하여 구현한다.
- 정해진 기준에 따라 요소에 우선순위를 할당하고,
Queue 구현
그럼 이제 C언어를 통해 실제 Queue를 구현하는 방법에 대해서 알아보자.
Queue도 마찬가지로 배열을 이용하는 정적 구현과 연결리스트를 이용하는 동적 구현, 2가지 방법이 있다. 추가로 Queue의 변형 구조인 Circular Queue와 Deqeue에 대해서도 함께 알아보자.
1️⃣ Queue 정적 구현
#include <stdio.h>
#define MAX_QUEUE_SIZE 100
typedef struct {
int data[MAX_QUEUE_SIZE];
int front, rear;
} Queue;
void init(Queue* q) {
q->front = q->rear = -1;
}
int is_empty(Queue* q) {
return q->front == q->rear;
}
int is_full(Queue* q) {
return q->rear == MAX_QUEUE_SIZE - 1;
}
void enqueue(Queue* q, int item) {
if (is_full(q)) {
printf("Queue is full!\n");
return;
}
q->data[++(q->rear)] = item;
}
int dequeue(Queue* q) {
if (is_empty(q)) {
printf("Queue is empty!\n");
return -1;
}
return q->data[++(q->front)];
}
int peek(Queue* q) {
if (is_empty(q)) {
printf("Queue is empty!\n");
return -1;
}
return q->data[q->front + 1];
}2️⃣ Circular Queue 동적 구현
#include <stdio.h>
#define MAX_QUEUE_SIZE 100
typedef struct {
int data[MAX_QUEUE_SIZE];
int front, rear;
} CircularQueue;
void init(CircularQueue* q) {
q->front = q->rear = 0;
}
int is_empty(CircularQueue* q) {
return q->front == q->rear;
}
int is_full(CircularQueue* q) {
return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}
void enqueue(CircularQueue* q, int item) {
if (is_full(q)) {
printf("Circular Queue is full!\n");
return;
}
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
int dequeue(CircularQueue* q) {
if (is_empty(q)) {
printf("Circular Queue is empty!\n");
return -1;
}
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
int peek(CircularQueue* q) {
if (is_empty(q)) {
printf("Circular Queue is empty!\n");
return -1;
}
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}3️⃣ Queue 동적 구현
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct {
Node* front;
Node* rear;
} Queue;
void init(Queue* q) {
q->front = q->rear = NULL;
}
int is_empty(Queue* q) {
return q->front == NULL;
}
void enqueue(Queue* q, int item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = item;
new_node->next = NULL;
if (is_empty(q)) {
q->front = q->rear = new_node;
} else {
q->rear->next = new_node;
q->rear = new_node;
}
}
int dequeue(Queue* q) {
if (is_empty(q)) {
printf("Queue is empty!\n");
return -1;
}
Node* temp = q->front;
int item = temp->data;
q->front = temp->next;
if (q->front == NULL) q->rear = NULL;
free(temp);
return item;
}
int peek(Queue* q) {
if (is_empty(q)) {
printf("Queue is empty!\n");
return -1;
}
return q->front->data;
}4️⃣ Deque 동적 구현
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
typedef struct {
Node* front;
Node* rear;
} Deque;
void init(Deque* dq) {
dq->front = dq->rear = NULL;
}
int is_empty(Deque* dq) {
return dq->front == NULL;
}
void add_front(Deque* dq, int item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = item;
new_node->prev = NULL;
new_node->next = dq->front;
if (is_empty(dq)) {
dq->rear = new_node;
} else {
dq->front->prev = new_node;
}
dq->front = new_node;
}
void add_rear(Deque* dq, int item) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = item;
new_node->next = NULL;
new_node->prev = dq->rear;
if (is_empty(dq)) {
dq->front = new_node;
} else {
dq->rear->next = new_node;
}
dq->rear = new_node;
}
int delete_front(Deque* dq) {
if (is_empty(dq)) {
printf("Deque is empty!\n");
return -1;
}
Node* temp = dq->front;
int item = temp->data;
dq->front = temp->next;
if (dq->front) dq->front->prev = NULL;
else dq->rear = NULL;
free(temp);
return item;
}
int delete_rear(Deque* dq) {
if (is_empty(dq)) {
printf("Deque is empty!\n");
return -1;
}
Node* temp = dq->rear;
int item = temp->data;
dq->rear = temp->prev;
if (dq->rear) dq->rear->next = NULL;
else dq->front = NULL;
free(temp);
return item;
}