C++로 Circular Queue (원형 큐) 구현하기

큐(Queue)란? 박스처럼 입출력이 한곳에서 진행되는 스택과 다르게 front와 rear이 존재하며 rear로 데이터가 들어가고 front에서 데이터가 나오게 된다.

FIFO (First In First Out, 선입선출)로, 가장 먼저 들어온 데이터가 가장 먼저 나온다.

 

Queue(큐) 사진 (출처 : 나무위키)

일반 큐의 단점은 큐에 빈 메모리가 남아있어도, rear가 끝에 도달한 경우 꽉 찬 경우로 판단 할 수 있다.

이를 개선한 것이 Circular Queue (원형 큐)이다.

 

원형 큐는 초기 공백 상태일 때 front와 rear이 0으로 초기화 되어있으며, 공백 및 포화 상태를 쉽게 구분하기 위해 자리 하나를 비워두는 것이 핵심이다. 또한, 원형 큐는 (index+ 1) % size 로 순환시킬 수 있다.

---

C++로 원형 큐를 구현하기 위해 제작한 함수

1. q.push() : 큐의 rear 부분에 데이터를 넣기 위해 제작한 함수.

 데이터를 push 하기 전, 큐가 가득 차 있는 상태인지 확인해야 한다. 

2. q.pop() : 큐의 front 부분의 데이터를 제거하고 front 위치를 옮기기 위해 제작한 함수.

 큐가 비어있는 경우 더 이상 데이터를 제거하지 않고, 큐가 비어있다는 알림을 출력해줘야 한다.

3. q.print() : 큐의 전체를 출력하는 함수

 큐가 비어있는 경우 큐가 비어있다는 알림을 출력해준다. 그렇지 않으면 큐에 들어있는 모든 데이터를 출력해준다.

---

연습문제 : 길이가 10인 배열로 원형 큐를 구현해보자.

#include <iostream>
using namespace std;

class myQueue {
private:
	int arr[10] = { 0 };
	int front = 0, rear = 0;

public:
	void push() {
		if (((rear + 1) % 10) == front) {
			cout << "Queue is Full" << endl;
		}
		else {
			cout << "데이터를 입력하세요 : ";
			int data;
			cin >> data;
			rear = (rear + 1) % 10;
			arr[rear] = data;
		}
	}
	void pop() {
		if (front == rear) {
			cout << "Queue is Empty" << endl;
			return;
		}
		front = (front + 1) % 10;
	}
	void print() {
		if (front == rear) {
			cout << "Queue is Empty" << endl;
			return;
		}
		for (int i = (front+1)%10; i != (rear + 1)%10; i = (i + 1) % 10) {
			cout << i << " : " << arr[i] << endl;
		}
	}
};
int main() {
	int num;
	myQueue q;
	while (1) {
		cout << "번호를 입력해주세요 1. push / 2. pop / 3. print / 4. 종료" << endl;
		cin >> num;
		switch (num) {
		case 1:
			q.push();
			break;
		case 2:
			q.pop();
			break;
		case 3:
			q.print();
			break;
		case 4:
			return 0;
		default :
			cout << "잘못된 입력입니다." << endl;
		}
	}

	return 0;
}