Queue

Queue의 기본 데이터 타입으로 환형 리스트뿐만 아니라, 배열을 사용할 수 있다. capacity로 N개의 공간을 할당하고, 실제 데이터의 개수는 n, 가장 앞에 있는 원소의 인덱스를 front_index, 마지막 원소의 인덱스를 rear_index라고 한다면, 모듈러 연산을 활용하여 Queue에 원소를 추가하거나 제거할 때, O(n)의 공간 복잡도를 피할 수 있다.

 

#pragma once
#include <string>

// 예외 클래스
class RuntimeException{
public:
	RuntimeException(const std::string& err) : errorMsg(err){}
	std::string getMessage() const{ return errorMsg; }
private:
	std::string errorMsg;
};

class QueueEmpty : public RuntimeException{
public:
	QueueEmpty(const std::string& err = "Queue Empty") : RuntimeException(err){}
};

class QueueFull : public RuntimeException{
public:
	QueueFull(const std::string& err = "Que Full") : RuntimeException(err){}
};

// Queue 구현부
template <typename T, size_t N>
class Queue{
public:
	Queue() : data(new T[N]), front_index(0), rear_index(0), n(0){}
	~Queue(){ delete[] data; }

	size_t size() const{ return n; }

	bool empty() const{ return n == 0; }

	const T& front() const throw(QueueEmpty){
		if(empty()){
			throw (QueueEmpty());
		}
		return data[front_index];
	}

	void dequeue()  throw(QueueEmpty){
		if(empty()){
			throw (QueueEmpty());
		}
		front_index = (front_index + 1) % N;
		n = n - 1;
	}

	void enqueue(const T& e) throw(QueueFull){
		if(size() == N){
			throw(QueueFull());
		}
		data[rear_index] = e;
		rear_index = (rear_index + 1) % N;
		n = n + 1;
	}
private:
	T* data;
	size_t front_index;
	size_t rear_index;
	size_t n;
};