[자료구조] - 원형큐의 구조와 구현

1. 선형큐의 문제점

앞서 포스팅한 큐 설명 글에서 선형큐에 대한 문제점을 잠깐 언급하였다. 선형큐를 1차원 배열을 이용하여 구현할 경우, front와 rear의 값이 계속 증가만 하므로 언젠가는 배열의 끝에 도달하게 되어 비효율적이다. 이러한 문제는 큐를 구현하는 배열을 선형 말고 원형으로 두면 쉽게 해결할 수 있다. 원형큐의 구조와 구현 방법을 지금부터 알아보자. 

 

---

2. 원형큐의 구조

원형큐도 선형큐와 마찬가지로 1차원 배열로 구현하는데, front와 rear가 증가만 하는 선형큐와 달리, 원형큐는 front와 rear의 값이 배열의 끝 값인 MAX-1 에 도달하면 그 다음값은 다시 0이 된다. 

 

원형큐에서 front와 rear의 초기값은 둘 다 0이다. front가 큐의 첫번째 요소의 하나 앞을, rear이 큐의 마지막 요소를 가리키는 것은 동일하다. (front == rear) 이면 큐가 비어있음을 뜻한다. 단 주의할 점은, 원형큐에서는 한 자리는 항상 비워둔다. 한 자리를 비워두지 않으면 꽉 차있을 때에도 (front == rear) 이고, 그러면 비어있는 상태와 꽉 차있는 상태를 구별할 수 없게 된다. 

---

3. 원형큐 구현

그렇다면 front와 rear이 배열의 끝에 도달한 후 다시 0으로 돌아가도록 하려면 어떻게 해야 할까?

=> 나머지 연산자 % 를 이용하면 된다. 증가된 front, rear 값을 MAX로 나눠주면, front와 rear이 1씩 증가하다가 MAX가 될 때, 나머지가 0이므로 MAX-1 다음부터는 다시 0으로 돌아가게 된다. 

//삽입할 때 rear
rear ← (rear+1) % MAX;

//삭제할 때 front
front ← (front+1) % MAX;

 

전체 코드로 원형큐를 구현해보자.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAX 6
typedef int element;

typedef struct {
	int front;
	int rear;
	element data[MAX];
} QueueType;


//큐 초기화
void init_queue(QueueType* q) {
	q->rear = 0;
	q->front = 0;
}

//큐가 비어있는지 검사
int is_Empty(QueueType* q) {
	if (q->front == q->rear) return 1;
	else return 0;
}

//큐가 꽉 차있는지 검사
int is_full(QueueType* q) {
	if ((q->rear+1) % MAX == q->front) return 1;
	else return 0;
}

//큐의 맨 끝에 삽입
void enqueue(QueueType* q, int item) {
	if (is_full(q) == 1) {
		cout << "Overflow";
		exit(1);  //리턴값 없이 함수를 강제 종료
	}
	q->rear = (q->rear + 1) % MAX;
	q->data[q->rear] = item;
}

//큐의 맨 앞의 요소 제거 후 반환
element dequeue(QueueType* q) {
	if (is_Empty(q)) {
		cout << "Empty";
		exit(1);  //리턴값 없이 함수를 강제 종료
	}
	else {
		q->front = (q->front + 1) % MAX;  //맨 앞의 요소는 front+1 의 인덱스에 있다.
		return q->data[q->front];
	}
}

//큐의 맨 앞 요소 출력
element peek(QueueType* q) {
	if (is_Empty(q) == 1) {
		cout << "Empty!";
		exit(1);	//리턴값 없이 함수를 강제 종료
	}
	else
		return q->data[(q->front + 1) % MAX];
}

//main함수
int main() {
	QueueType q;

	init_queue(&q);
	enqueue(&q, 1);
	enqueue(&q, 2);
	enqueue(&q, 3);
	enqueue(&q, 4);

	cout << dequeue(&q) << "\n";
	cout << peek(&q) << "\n";
	cout << dequeue(&q) << "\n";
}