[C++ 자/알 Note] 큐 구현

주의사항

- 구현 방식

vector, list, deque 등 다양한 방식으로

내부 container를 사용할 수 있는데

실제 STL에선 deque가 기본이다

 

- 순환구조

순환구조를 배우는 겸 vector로 구현해보자

 

리스트 큐 구현

template<typename T>
class MyListQueue
{
public:
	void push(const T& value)
	{
		_container.push_back(value);
	}

	void pop()
	{
		_container.pop_front();
	}

	T& front()
	{
		return _container.front();
	}

	bool empty() { return _container.empty(); }
	int size() { return _container.size(); }

private:
	list<T> _container;
};

 

동적배열(vector) 큐 구현

template<typename T>
class MyVectorQueue
{
public:
	MyVectorQueue()
	{
		//_container.resize(100);
	}

	void push(const T& value)
	{
		if (_size == _container.size())// 꽉 찬 경우
		{
			// 증설 작업
			int newSize = max(1, _size * 2);
			vector<T> newData;
			newData.resize(newSize);

			// 데이터 복사
			for (int i = 0; i < _size; i++)
			{
				int index = (_front + i) % _container.size();
				newData[i] = _container[index];
			}

			_container.swap(newData);
			_front = 0;
			_back = _size;
		}

		_container[_back] = value;
		_back = (_back + 1) % _container.size();
		_size++;
	}

	void pop()
	{
		_front = (_front + 1) % _container.size();
		_size--;
	}

	T& front()
	{
		return _container[_front];
	}

	bool empty() { return _size == 0; }
	int size() { return _size; }

private:
	vector<T> _container;

	int _front = 0;
	int _back = 0;// rear or back
	int _size = 0;
};