Queue

Queue

• FIFO (First In First Out 선입선출)

List로 구현한 Queue

template<typename T>
class ListQueue
{
public:
	void push(const T& value)
	{
		_container.push_back(value);
	}
	void pop()
	{
    	//_container.erase(_container.begin());
		_container.pop_front();
	}

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

	bool empty()
	{
		return _container.empty();
	}
	int size()
	{
		return _container.size();
	}
private:
	//vector<T> _container;
	list<T> _container;
};

• List를 활용하여 Queue를 구현하면 Vector와는 달리 중간 삽입/삭제가 효율적이기 때문에 이점이 있다. (List Queue)

• Vector를 활용하여 Queue를 구현할 경우 순환 방식을 사용하여 구현한다.

순환 배열을 사용한 Queue

template<typename T>

class ArrayQueue
{
public:
	ArrayQueue()
	{
		_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[_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;
	int _size = 0;
};

• vector는 list와는 달리 중간 삽입/삭제가 비효율적이기 때문에 색다른 방식의 구현이 필요하다.

• vector의 임의 접근을 이용하여 front와 back을 임의로 지정하여 index를 순환하며 저장을 하는 방식을 사용한다.

• 만약 size가 초기에 지정한 size보다 커질 경우 메모리를 증설하여 데이터를 옮겨준다.