[Linear Data] Chapter 04. 큐

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/c944c3b8377426e722f4c3cf296d00c6b62db56c

큐(Array, List) 구현 · developeSHG/Data_Structure-Algorithm@c944c3b

 

 

---

 

 

Queue는 선입선출 구조다.

큐를 구현할 때, 데이터의 삽입은 뒤에서 추가되고, 삭제는 맨 앞에서 일어난다.

이럴 때, 데이터 복사로 인해 삽입/삭제 속도가 느린 vector보다 단순 node 끼리 연결된 list가 유용하다.

 

하지만, vector로 구현할 수 있는 방법이 아예 없는 건 아니다.

생각을 바꿔서, 굳이 임의로 데이터를 꺼내기보단, 실질적으로 사용할 데이터 범위를 정해둬서 순환 구조로 관리하면 어떨까란 생각이 든다.

front와 back의 인덱스(위치)를 알고 있기에 데이터를 순환 구조로 만든 후, 데이터를 삽입/삭제 함에 따라 front와 back의 인덱스를 변경해주면 된다.

만약 꽉 찼을 경우, 위에 말한대로 순환 구조라 했으니 다시 back이 맨 앞으로 돌아가면 되고, 또는 다시 크기를 증설해도 된다.

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
using namespace std;

// Queue (FIFO First-In-First-Out 선입선출)

// front << [1][2][3][4] << rear(back)
// 대기열

// 순환구조 큐
// [][][front][][][][][][][][][back][][][][]
// [front][][][][][][][][][back][][][][][][][][][][][][][][][][][][][][]
template<typename T>
class ArrayQueue
{
public:
	ArrayQueue()
	{
		//_container.resize(100);
	}

	void push(const T& value)
	{
		// TODO : 다 찼는지 체크
		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;
	int _size = 0;
};

template<typename T>
class ListQueue
{
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;
};

int main()
{
	ArrayQueue<int> q;

	for (int i = 0; i < 100; i++)
		q.push(i);

	while (q.empty() == false)
	{
		int value = q.front();
		q.pop();
		cout << value << endl;
	}

	int size = q.size();
}