C++ Queue 만들기 (version.2 - Circular Queue)

C++로 자료구조 만들기

Circular Queue를 만들어 볼 것이다.

 

Circular Queue는 문자 그대로 원형 큐, 즉 큐의 rear 부분이 자료구조의 끝을 가리키는 경우 enqueue를 한다면 rear가 자료구조의 맨 앞을 가리키게 되며 큐가 마치 원 모양으로 도는 것처럼 구현하기 때문에 이렇게 이름 지어졌다.

 

size 4의 큐가 있을 때, 1부터 6까지의 숫자를 큐에다 넣는다 하고 아래와 같이 명령을 넣어보면

> enqueue(1), enqueue(2), enqueue(3), dequeue(), enqueue(4), dequeue(), enqueue(5), dequeue(), enqueue(6)

 

이런식으로 동작할 것이다.

 

Queue의 Overflow 문제를 보완하기 위해 고안된 방법이지만 완전한 방법은 아니다. 큐 안에 데이터가 쌓인다면 이것 역시Overflow가 발생한다.

 

Overflow 에러 방지를 위해 큐의 맨 앞쪽 요소와 맨 마지막에 있는 요소 사이에는 한칸 비워두는 것이 좋다.

 

 

Circular Queue의 메인 함수부터 만들어 보겠다.

#include "Queue.h"
#include <stdio.h>

void main() 
{
	/*Queue q;
	q.enqueue(10);
	q.enqueue(20);
	q.enqueue(30);
	int x = q.dequeue();
	printf("%d\n", x);
	q.enqueue(40);
	q.enqueue(50);
	printf("%d\n", q.dequeue());*/

	Queue *q = new Queue();
	q->print();
	q->enqueue(10);
	q->enqueue(20);
	q->enqueue(30);
	int x = q->dequeue();
	printf("%d\n", x);
	q->enqueue(40);
	q->enqueue(50);
	printf("%d\n", q->dequeue());

	for (int i = 1; i < 20; i++) {
		q->enqueue(i);
		printf("%d\n", q->dequeue());
	}

	q->print();
	delete q;
}

Queue를 만들고 큐의 메서드로 print(), enqueue(), dequeue()를 사용하는 것을 확인할 수 있다.

 

다음은 Queue의 헤더 파일이다

#define MAX		(10)

class Queue {
	int s[MAX];
	int front;
	int rear;
	bool isFull();
	void overFlow();
	bool isEmpty();
	void emptyError();
public:
	Queue();
	void enqueue(int x);
	int dequeue();
	void print();
};

size 10의 배열을 사용하는 큐이다. 구조상으로 version 1의 큐와 다른 것은 없다.

 

그리고 Queue.cpp를 보겠다.

#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>

Queue::Queue() {
	front = 0;
	rear = 0;

	for (int i = 0; i < MAX; i++) s[i] = 0;
}

void Queue::print() {
	printf("%d %d\n", front, rear);
	for (int i = 0; i < MAX; i++) {
		printf("%d ", s[i]);
	}
	printf("\n");
}

void Queue::enqueue(int x) {
	if (isFull()) overFlow();
	rear = (rear+1)%MAX;
	s[rear] = x;
}

bool Queue::isFull() {
	if (rear+1 == front%MAX) return true;
	return false;
}

void Queue::overFlow() {
	printf("Overflow\n");
	exit(-1);
}

int Queue::dequeue() {
	if (isEmpty()) emptyError();
	front = (front+1)%MAX;
	return s[front];
}

bool Queue::isEmpty() {
	if (front == rear) return true;
	return false;
}

void Queue::emptyError() {
	printf("Empty\n");
	exit(-1);
}

Queue의 constructor 부분은 front = rear = 0, 배열 값 0으로 초기화 해주는 것이고, 큐의 현재 값들을 출력해주는 print() 함수를 만들었다.

 

enqueue()는 큐가 가득 찼는지 확인을 해주고 큐에다가 값을 넣는다. isFull()을 보면 rear + 1 이 front % MAX 한것과 같다면 가득찬 것이다. rear에 +1을 한 것과 비교한 이유는 큐의 마지막 끝에 해당하는 칸은 비워두는 것으로 가정하기 때문이다.

값을 넣을 때는 rear 에다 (rear + 1) 에 모듈로 연산(%)을 사이즈만큼 한 값을 정해준다. 배열이 사이즈 범위를 초과한 경우 배열의 앞부분 인덱스에 위치시키기 위함이다. 그리고 배열의 rear 에 해당하는 인덱스에 값을 넣는다.

 

dequeue()는 큐가 비었는지 확인을 먼저 해준다. 초기상태와 같이 front와 rear가 같은 위치를 가리키고 있다면 큐는 비었으므로 값을 빼내는게 불가능하다. 

큐가 비어있지 않은 경우에는 rear 위치 지정과 마찬가지로 front = (front + 1) % MAX를 한 후 배열의 front번째 요소를 리턴한다.