C++ Queue 만들기 (version.3 - Growable Array Queue)

Queue 만들기 version 3

 

Growable Array Queue 이면서 garbage collector 명령어와 destructor를 사용해 보겠다.

 

Growable Array Queue도 Growable Array Stack과 마찬가지로 자료구조가 가득 차게되면 자료구조의 size를 두배 씩 늘려나가며 운용하는 것이다.

Queue 자체는 Circular Queue의 방식과 같고 OverFlow가 발생하기 전에 자료구조 크기를 늘려주는 작업이 추가된 것과 같다.

 

데이터가 들어가지 않은 초기 상태의 큐가 이렇게 있을 때, 데이터를 1부터 증가시키면서 넣어보겠다.

이런 식으로 데이터를 채워나가게 되고 다음으로 4를 enqueue한다고 할 때, (rear+1) % size 의 값이 front와 같아진다면 이후에 더이상 저장할 공간이 없게 되므로 배열 사이즈를 늘려준 후 enqueue 작업을 진행하게 한다.

 

사용하던 큐의 두배 크기의 임시 배열을 만든 후 현재 큐의 front의 다음칸, (front+1)%size를 tmp_front로 지정해준다. (front가 맨 뒤 인덱스를 가리키는 경우 다음칸이 0번째 인덱스가 될 수 있으므로 모듈로 연산 %을 잊지 않는다)

그리고 tmp_front 부터 size-1 번 만큼 루프를 돌면서 임시 배열 tmp에 차례대로 값을 넣어준다.

 

 

이런식으로 채워주고 나머지 빈공간은 0으로 채워주도록 한다.

 

새로운 배열에 rear를 size - 1에 위치하게 해주고, size *= 2 를 하여 새로운 배열의 크기가 8이 됨을 나타내도록 해준다. 그리고 원래 큐가 임시 배열을 참조하도록 한다.

그리고 enqueue를 위해 들어온 값을 큐의 rear위치에 넣어주며 front는 size - 1에 위치하게 한다. 즉, front는 배열의 마지막 인덱스에 위치하게 함으로써 오버플로우 판별을 위한 하나의 공백 칸을 두기 위함이다.

 

 

이런식으로 Growable Array 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->print();
	q->enqueue(20);
	q->print();
	q->enqueue(30);
	q->print();
	int x = q->dequeue();
	q->print();
	printf("%d\n", x);
	q->print();
	q->enqueue(40);
	q->print();
	q->enqueue(50);
	q->print();
	printf("%d\n", q->dequeue());
	q->print();

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

	q->print();
	delete q;
}

위의 메인함수는 큐에 데이터를 넣고 빼고 출력해보는 작업을 한다.

 

#define INIT_SIZE		(4)

class Queue {
	int *s;
	int sz;
	int front;
	int rear;
	bool isFull();
	bool isEmpty();
	void emptyError();
public:
	Queue();
	~Queue();
	void enqueue(int x);
	int dequeue();
	void print();
};

헤더 파일은 위와 같이 정의해주었고 constructor 밑에 destructor, 즉 소멸자를 만들었다. 

생성자와 반대되는 개념으로 큐 객체가 소멸되는 시점에 garbage collector 기능을 해주는 역할을 한다.

클래스 명 앞에 ~(Tilde, 틸드)를 붙임으로써 destructor를 추가할 수 있다.

 

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

Queue::Queue() {
	front = 0;
	rear = 0;
	sz = INIT_SIZE;
	s = new int[sz];

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

Queue::~Queue() {
	delete []s;
}

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

void Queue::enqueue(int x) {
	if (isFull()) {
		int *tmp = new int[sz*2];
		int tmp_front = (front+1)%sz;
		for (int i = 0; i < sz-1; i++) {
			tmp[i] = s[tmp_front];
			tmp_front = (tmp_front+1)%sz;
		}
		for (int i = sz-1; i < sz*2; i++) {
			tmp[i] = 0;
		}
		delete []s;
		rear = sz-1;
		sz *= 2;
		s = tmp;
		s[rear] = x;
		front = sz-1;
	}
	else {
		rear = (rear+1)%sz;
		s[rear] = x;
	}
}

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

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

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

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

주요 내용들은 위에서 설명한 바와 같고, destructor 부분을 보자면

객체 소멸 시점에 사용했던 데이터를 delete 시켜준다. 

하지만 모든 garbage를 collect 해주는 것은 아니고 해당 데이터가 참조하고 있는 또 다른 데이터가 더 있다면 그 데이터들은 지워주지 않는다. 

C++ 프로그래머들이 garbage collect 작업에 신경을 엄청나게 쓰는 이유가 이런 부분들에 있어서 인 듯하다. 

일일히 참조하고 있는 데이터들을 따라가서 다 지워줘야하는 방식인데 프로그램 크기가 방대해지면 이러한 처리들이 되게 찾기도 어렵고 힘들것 같다.