[C++][구현] 원형 큐(Circular Queue)

원형 큐를 사용하면서, 버퍼 1개를 빈 공간으로 사용하여 Empty와, Full 유무를 확인 하였습니다.

 

Front : 값이 나올 인덱스

Rear : 값이 들어갈 인덱스

 

Full() : 큐가 가득 찬지 확인합니다.

Empty() :: 큐가 비어 있는지 확인합니다.

enqunue() : 값을 큐에 삽입합니다.

dequeue(): 큐의 값을 한개 반환합니다.

qPrint() : 남아있는 값을 출력합니다. 

 

---

Front == Rear 인 큐에 아무것도 없는 상태

 

 

Front == (Rear +1) % capactiy 인 큐가 가득 찬 상태 (Empty와 구분을 위하여 1개의 여분의 버퍼를 남겨둡니다) 

---

 

#include <iostream>
using namespace std;

// Buffer을 한개 더 안 쓰는 Circular Queue
template <typename T> class cQueue {
private:
	size_t front;
	size_t rear;
	size_t capacity;
	T* arr;

public:
	cQueue() {
		front = 0;
		rear = 0;
		capacity = 10; // use size 9
		arr = new T[capacity]; // empty buffer 1, for Empty, Full 
	}

	bool Full() {
		return front == (rear + 1) % capacity;
	}

	bool Empty() {
		return front == rear;
	}

	void enqueue(const T&& data) {
		if (!Full()) {
			arr[rear] = move(data);
			rear = (rear + 1) % capacity;
		}
	}

	T dequeue() {
		if (!Empty()) {
			T p = arr[front];
			front = (front + 1) % capacity;
			return p;
		}
	}

	void qPrint() {
		if (front > rear) {
			for (int i = front; i < capacity; i++) cout << arr[i] << ' ';
			for (int i = 0; i < rear; i++) cout << arr[i] << ' ';
		}
		else for(int i=front; i< rear; i++) cout << arr[i] << ' ';
	}
};