자료구조) Queue 큐 - 선형큐인줄 알았지만 슬픈 원형 큐

사용언어) C++

 

Queue란 FIFO(First Info First Out)의 형태를 가지고 있는 자료구조이다.

front와 rear포인트를 활용하여 입력과 출력을 구현한다.

ㅁ

 front -> ✔ ✔ ✔ ✔ rear -> ㅁ ㅁ ㅁ

• 1차원 배열을 이용하여 만들었다.
• 물론 vector나 다른 방식을 이용하면 다른 방식으로도 만들 수 있지만 일단 기초를 다지기 위해서 1차원 배열로 만들었다.
• 선형큐인줄 알고 만들었지만, 알고보니 선형큐의 보안버전인 원형큐였다는 슬픈 사실이...

#include <iostream>

using namespace std;
template<typename T, int n>
class Queue {
private:
	T* datas;
	int front, rear;

public:
	Queue() {
		datas = new T[n];
		front = -1;
		rear = -1;
	}
	bool empty() {
		if (front == rear)
			return true;
		return false;
	}
	void enqueue(T data) {	// Input
		if ((front == -1 && rear == (n-1)) || (rear + 1 == front)) {
			cout << "꽉 찼습니다" << endl;
		}
		else {
			datas[++rear] = data;
			if (rear == n)
				rear = -1;
		}
	}
	T dequeue() {	// Pop
		if (!empty()) {
			T s = datas[++front];
			if (front == n)
				front = -1;
			return s;
		}
		return -1;
	}
};