C++ Queue 만들기 (version.1)

Stack에 이어 Queue를 C++ 로 만들어 보겠다.

 

Queue도 주로 Stack과 같이 자료구조의 앞 부분을 장식하는 친구이다. 

 

First In First Out 방식이며, 데이터 추가 및 삭제시 Java에서는 add()와 remove()지만 C++은 enqueue()와 dequeue()이다.

 

메인 함수가 있는 test.cpp 파일을 먼저 만들어 보겠다.

#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->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());

	delete q;
}

 

주석 처리 하지 않은 Dynamic allocation 방식의 큐를 보겠다.

 

큐에 10, 20, 30을 순서대로 넣고 dequeue()를 한번 하여 변수 x에 저장한다. x를 출력 시켜주면 10이 print되어 나올것이다. 그 다음으로 40, 50을 enqueue()후 큐에서 바로 dequeue()한 20을 print하는 순서다.

 

 

큐의 헤더파일을 만들어 보겠다.

 

#define MAX		(100)

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();
};

Queue라는 클래스에 private Data member들 배열 s와 큐의 앞부분을 나타내줄 front, 뒷 부분의 rear를 정의해주고 bool 타입의 메서드 isFull(), isEmpty(), void 타입의 overFlow(), emptyError()를 정의해준다.

public에는 생성자 Queue()와 연산을 위한 메서드 enqueue(int x), dequeue()를 정의한다.

 

 

큐를 구현할 Queue.cpp 파일을 만들겠다.

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

Queue::Queue() {
	front = -1;
	rear = -1;

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

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

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

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

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

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

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

 

초기에 Queue를 생성할 때, front와 rear에는 -1을 넣어 큐가 비어있음을 나타낸다. 그리고 큐를 0으로 초기화해준다.

 

enqueue()는 rear가 MAX-1과 같을 때, 즉, 다 찼을때의 isFull() 체크를 하며 오버플로우 처리를 해주고, isFull()이 아니라면 rear를 하나씩 증가시키면서 배열에 값을 넣어준다.

 

dequeue()도 비슷하게 front가 rear와 같다면 큐가 비어있는게 되기때문에 emptyError()처리를 해주고, 아닌 경우 front를 1씩 증가하며 배열의 값을 리턴시켜준다.

 

여기까지 가장 간단한 Queue 구현(version.1)을 해보았다