[자료구조] 큐(Queue)의 구조와 구현 - 선형 큐(Linear Queue)와 원형 큐(Circular Queue)

삽입과 삭제가 한 곳(top)에서만 이루어는 후입선출(LIFO)의 입출력 구조를 가졌던 스택(Stack)과 달리,

배열의 양 끝에서 입력과 출력이 이루어지는 큐(Queue)에 대해서 알아보자!

 

 

 

큐(Queue)

 

큐(Queue) 는 리스트의 앞 부분에서는 삭제가, 뒷 부분에서는 삽입이 이루어지는,

먼저 삽입된 자료가 먼저 삭제되는 선입선출(FIFO)의 입출력 구조로 운영된다.

 

다음과 같은 전단(front)과 후단(rear)이 리스트의 양 끝을 가리키게 된다.

 

- 전단(front) : 데이터의 삭제 연산 (가장 먼저 들왔던 데이터가 쌓여있는 쪽) -> dequeue() 연산

- 후단(rear) : 데이터의 삽입 연산 (가장 나중에, 최근에 삽입된 데이터가 쌓여있는 쪽) -> enqueue() 연산

 

 

 

 

큐의 ADT는 다음과 같다.

 

- create(max_size) : 최대 크기가 max_size인 공백 큐 구조체가 생성된다.

- init(q) : 큐의 front, rear 값을 -1로 초기화한다.

- is_empty(q) : size==0 인 경우, front==rear 

- is_full(q) : size==max_size인 경우, rear==max_size-1

- enqueue(q, e) : 큐의 후단(rear)에 요소 삽입

- dequeue(q) : 큐의 전단(front)의 요소 제거 하여 반환

- peek(q) : q의 전단(front)의 요소 반환

 

 

 

---

 

선형 큐 / 원형 큐

 

위에서 설명한 기본적인 큐의 구조와 입출력 형태, ADT 모두 선형 큐를 설명한 것이다. 

원형 큐로 넘어가기 전에 선형 큐의 구조와 코드로 구현한 것을 짧게 살펴보자.

 

 

 

선형 큐 (Linear Queue)

 

 

 

선형 큐는 정해진 리스트 배열 크기 내에서 각 인덱스를 front와 rear이 각각 한 번만 지나칠 수 있다.

따라서, 데이터의 삽입 연산 enqueue() 가 일어나는 후단 rear 부분이 배열의 끝에 도달하면,

더이상 배열을 사용할 수 없게 되는 구조이다.

 

 

 

 

---

 

기본적인 큐의 선언과 연산을 코드로 구현하면 다음과 같다.

 

 

1. 큐 QueueType 구조체 선언

큐에 삽입될 수 있는 요소의 개수는 총 5개이고, 가독성을 위해 TRUE와 FALSE는 각각 1과 0으로 정의하였다.

요소 element로는 int형 정수가 사용된다.

그리고 QueueType 의 구조체를 선언하고 typedef 시켜놓았다.

멤버로는 전단과 후단을 가리킬 front와 rear, 그리고 리스트 element data 배열이 포함된다.

 

#define MAX_QUEUE_SIZE 5
#define TRUE 1
#define FALSE 0

typedef int element;
typedef struct QueueType {
	int front; // front에 데이터 삽입
	int rear; // rear의 데이터 삭제
	element data[MAX_QUEUE_SIZE];
}QueueType;

 

 

 

2. 큐 초기화, 공백/포화 상태 체크

init_queue() - q의 front와 rear의 값을 모두 -1로 초기화한다.

is_empty() - front와 rear의 값이 같다면 큐가 공백임을 확인

is_full() - rear의 값이 큐 리스트의 최대 사이즈인 MAX_QUEUE_SIZE 보다 1 작다면 큐가 포화임을 확인

 

// init_queue
void init_queue(QueueType* q) {
	q->front = -1;
	q->rear = -1;
}

// is_empty
int is_empty(QueueType*q) {
	if (q->front == q->rear) return TRUE;
	else return FALSE;
}

// is_full
int is_full(QueueType *q) {
	if (q->rear == MAX_QUEUE_SIZE - 1) return TRUE;
	else return FALSE;
}

 

 

3. enqueue()

큐의 후단(rear) 부분에 새로운 요소를 삽입한다.

먼저 큐가 포화 상태인지 체크한다. 배열의 끝에 rear이 도달해 있는 상태면 더이상 요소를 삽입하지 못한다.

 

큐의 rear은 요소를 삽입하기 이전의 마지막 요소를 가리키고 있으므로,

새로운 요소를 삽입하는 연산이 이루어질 때에는, rear의 값을 먼저 증가시킨 후에

rear가 가리키는 위치에 새로운 요소를 삽입한다.

 

// enqueue
void enqueue(QueueType* q, element item) {
	if (is_full(q)) {
		printf("queue is full \n");
		return;
	}
	q->data[++(q->rear)] = item;
}

 

 

4. dequeue()

큐의 전단(front) 부분의 요소를 삭제하고 반환한다.

먼저 큐가 공백 상태인지 체크하여 삭제 가능한 상태인지 확인한다.

 

front역시 rear과 마찬가지로, 다음 연산이 이루어지기 이전의 인덱스를 가리키고 있다.

따라서 요소를 반환하기 위해, front의 값을 1 증가시킨 후에 해당 요소를 item 변수에 저장하여 리턴하도록 한다.

 

// dequeue
element dequeue(QueueType*q) {
	if (is_empty(q)) {
		printf("queue is empty \n");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

 

 

5. queue_print()

큐에 들어있는 요소들을 출력한다.

0번째부터 MAX_QUEUE_SIZE까지의 배열 인덱스 중에,

(front+1) 부터 rear 사이의 요소들을 출력하도록 한다.

 

// queue_print
void queue_print(QueueType* q) {
	printf("[");
	for (int i = 0;i < MAX_QUEUE_SIZE;i++)
		if (i > q->front && i <= q->rear)
			printf("%3d", q->data[i]);
	printf("  ]\n");
}

 

 

 

 

main 함수를 포함한 전체 코드는 다음과 같다.

 

#include <stdio.h>

#define MAX_QUEUE_SIZE 5
#define TRUE 0
#define FALSE 1

typedef int element;
typedef struct QueueType {
	int front; // front에 데이터 삽입
	int rear; // rear의 데이터 삭제
	element data[MAX_QUEUE_SIZE];
}QueueType;

// init_queue
void init_queue(QueueType* q) {
	q->front = -1;
	q->rear = -1;
}

// is_empty
int is_empty(QueueType*q) {
	if (q->front == q->rear) return TRUE;
	else return FALSE;
}

// is_full
int is_full(QueueType *q) {
	if (q->rear == MAX_QUEUE_SIZE - 1) return TRUE;
	else return FALSE;
}

// enqueue
void enqueue(QueueType* q, element item) {
	if (is_full(q)) {
		printf("queue is full \n");
		return;
	}
	q->data[++(q->rear)] = item;
}

// dequeue
element dequeue(QueueType*q) {
	if (is_empty(q)) {
		printf("queue is empty \n");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

// queue_print
void queue_print(QueueType* q) {
	printf("[");
	for (int i = 0;i < MAX_QUEUE_SIZE;i++)
		if (i > q->front && i <= q->rear)
			printf("%3d", q->data[i]);
	printf("  ]\n");
}

int main() {
	QueueType q;
	init_queue(&q);

	printf("< enqueue > \n\n");
	for (int i = 0;i < 3;i++) {
		enqueue(&q, i);
		queue_print(&q);
	}

	printf("\n< dequeue >\n\n");
	for (int i = 0;i < 3;i++) {
		printf("dequeue %d \n", dequeue(&q));
		queue_print(&q);
	}
}

 

0부터 3까지 총 3개의 요소를 enqueue() 한 후에,

똑같이 3번 dequeue() 연산을 실행하도록 하였다.

 

실행 결과는 다음과 같다.

 

0부터 2까지 차례대로 리스트의 후단에 차례대로 요소가 삽입되며,

dequeue() 연산을 동일하게 3번 실행하면, 전단 부분부터 요소가 삭제되는 LIFO 구조를 확인할 수 있다.

 

 

 

 

---

 

위의 선형 큐는 후단 부분에 enqueue() 가 이루어져, rear의 값이 (MAX_QUEUE_SIZE - 1) 에 도달하면

포화 상태의 큐가 되어 더이상 요소를 삽입할 수 없게 된다.

하지만, rear이 마지막 인덱스에 도달하더라도 dequeue() 연산이 이루어져 리스트의 앞부분이 비어 있는 경우,

포화 상태가 아님에도 불구하고 더이상 해당 배열의 입출력을 할 수 없게 된다.

 

이러한 선형 큐의 잘못된 포화 상태 인식 문제를 해결하기 위해 원형 큐(Circular Queue) 구조가 사용된다.

선형 큐와 동일하게 1차원 배열을 사용하지만, 배열의 처음과 끝이 연결되어 있는 구조이다

 

 

 

 

 

원형 큐 (Circular Queue)

 

선형 큐와 구조가 동일하지만, 차이점은 다음과 같다.

- front와 rear의 초깃값은 0이다.

- 포화 상태와 공백 상태를 구분하기 위해, 자리 하나를 항상 비워둔다.

- 삽입/삭제 연산에서, 변경되는 front와 rear값이 가리키는 위치가 마지막 인덱스에서 다시 처음 0번 인덱스로 돌아오게 되는 경우를 위해 나머지 연산자(modulus) 를 사용한다.

 

 

 

 

 

 

 

---

선형 큐와 다른 부분만 살펴보자.

 

 

1. init_queue, is_empty, is_full

 

front와 rear값이 선형 큐에서는 -1로 초기화되는 것과 달리, 원형 큐에서는 0으로 초기화된다.

큐가 공백 상태일 때와 포화 상태일 때를 구분하기 위해서이다.

두 상태를 구분하기 위해서, 원형 큐에서는 자리 하나를 항상 비워둔다.

 

공백 상태는 front와 rear의 값이 같을 때이고,

포화 상태는 rear이 front보다 하나 앞에 있을 때이다. 

 

 

포화 상태를 예를 들어보자.

MAX_QUEUE_SIZE == 3인 큐가 있다고 가정하고,

현재 2개의 요소가 삽입되어 rear값이 2, front값이 0이라고 해보자. 

이 때, 리스트의 전단과 후단이 연결되어 있다고 논리적으로 생각해보면, rear이 front의 위치보다 하나 앞에 있다고 할 수 있다.

따라서 ( rear + 1 ) % MAX_QUEUE_SIZE = ( 2 + 1 ) % 3 = ( 3 % 3 )의 값은 0이 되므로,

포화 상태임을 확인할 수 있다. (front가 현재 가리키는 0번 인덱스의 위치의 자리 하나가 비어있는 상태)

 

void init_queue(QueueType *q) {
	q->front = 0;		// linear queue front = -1
	q->rear = 0;		// linear queue rear = -1
}

// is_empty
int is_empty(QueueType*q) { return (q->front == q->rear); }

// is_full
int is_full(QueueType *q) {
	return((q->rear + 1) % MAX_QUEUE_SIZE) == q->front;
}

 

 

2. enqueue와 dequeue

각각 마지막 인덱스를 가리키고 있는 상태에서, 다음 연산을 실행 할 때 0번 인덱스의 위치에서 입출력이 이루어질 수 있도록,

front와 rear 값을 1을 증가 시킨 후에 MAX_QUEUE_SIZE로 나눈 나머지의 값을 저장하여 

front와 rear의 값을 변경하여 연산을 실행하도록 한다.

 

// enqueue
void enqueue(QueueType *q, QueueObject item) {
	if (is_full()) {
		printf("queue is full \n");
		return;
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

// dequeue
QueueObject dequeue(QueueType*q) {
	if (is_empty(q)) {
		printf("queue is empty \n");
		return -1;
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

 

 

 

 

전체 코드는 다음과 같다.

 

#include <stdio.h>

#define MAX_QUEUE_SIZE 3
#define TRUE 1
#define FALSE 0

typedef int QueueObject;
typedef struct QueueType {
	int front;
	int rear;
	QueueObject data[MAX_QUEUE_SIZE];
}QueueType;


void init_queue(QueueType *q) {
	q->front = 0;		// linear queue front = -1
	q->rear = 0;		// linear queue rear = -1
}

// is_empty
int is_empty(QueueType*q) { return (q->front == q->rear); }

// is_full
int is_full(QueueType *q) {
	return((q->rear + 1) % MAX_QUEUE_SIZE) == q->front;
}

// enqueue
void enqueue(QueueType *q, QueueObject item) {
	if (is_full()) {
		printf("queue is full \n");
		return;
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

// dequeue
QueueObject dequeue(QueueType*q) {
	if (is_empty(q)) {
		printf("queue is empty \n");
		return -1;
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

// queue_frint
void queue_print(QueueType*q) {
	for (int i = 0;i < MAX_QUEUE_SIZE;i++)
		printf("%d \t front = %d, rear = %d \n", q->data[i], q->front, q->rear);
	printf("\n");
}

int main() {
	QueueType q;
	init_queue(&q);

	printf("enqueue \n\n");
	for (int i = 0;i < 5;i++) {
		enqueue(&q, i);	
		queue_print(&q);
	}
	
	printf("\ndequeue\n\n");
	for (int i = 0;i < 5;i++) {
		printf("dequeue %d \n", dequeue(&q));
		queue_print(&q);
	}
}

 

 

 

---

이후 공부할 것

 

원형 큐의 원형 연결리스트 (Circular Linked List) 로의 확장

전단과 후단 모두에서 삽입/삭제 연산이 이루어지는 덱(Deque: Double Ended Queue)