[C++] Queue

간단한 bfs문제를 풀기위해 큐 구조를 직접 구현하였다.
덱 구조를 만들 수도 있었지만, 일단 큐를 구현하는게 먼저로 보여서 우선 큐로 만들었다.

구현 방법은 pop를 할때 맨 앞의 데이터를 return해주고, 시작 지점을 1부터 읽도록 만들어 주었다.

또한 push할때 capacity와 비교하여 나머지 연산을 통해 0부터 다시 넣어주는 방법을 통해 순환하도록 만들고 size가 capacity에 가득차면 resize과정에서 다시 0부터 데이터를 입력하여 보완하였다.

template<typename T>
struct queue {
	size_t start;
	size_t _size;
	size_t capacity;
	T* data;

	int size() { return static_cast<int>(_size); }
	queue(size_t init_size=2) : start(0), _size(0), capacity(init_size) {
		data = new T[init_size];
	}

	~queue() {
		delete[] data;
	}


	void resize(size_t new_size) {
		T* new_data = new T[new_size];
		for(size_t i = 0; i<_size; i++){
			new_data[i] = data[(start + i) % capacity];
		}
		start = 0;
		delete[] data;
		data = new_data;
		capacity = new_size;
	}

	void push(T value) {
		if (capacity == _size) resize(_size * 2);
		data[(start + _size++)%capacity] = value;
	}

	T pop() {
		if (_size == 0) {
			std::cerr << "index error : queue empty"; std::exit(EXIT_FAILURE);
		}
		_size--;
		
		T returnvalue = data[start];
		start = (start + 1) % capacity;
		return returnvalue;
	}
	
	void clear() {
		start = 0;
		_size = 0;
	}

	T& operator[](size_t index) {
		if (index > _size) {
			std::cerr << "index error : queue size over";
			std::exit(EXIT_FAILURE);
		}
		return data[(start + index) % capacity];
	}

};