자료구조 - 큐

이번에는 자료구조 큐에 대해 알아보도록 하겠습니다.

 

 큐는 FIFO (First In First Out)의 구조를 가진 자료구조입니다. 먼저 들어온 데이터가 먼저 빠져나오는 방식으로 만들어져 있기 때문에 LIFO (Last In First Out)의 구조를 가진 스택과는 다른 구조를 지녔음을 알 수 있습니다.

 

 마치 식당이나 은행에서 대기표를 받고, 대기 순서를 기다렸다가 먼저 대기표를 뽑은 순서대로 입장하듯, 먼저 들어온 데이터가 먼저 나가는 큐 자료구조 또한 많은 상황에서 사용할 수 있는 유용한 자료구조입니다.

 

 우선 리스트 컨테이너를 이용한 큐를 살펴보도록 하겠습니다.

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

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

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

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

private:
	list<T> _container;
};

 리스트는 중간 삽입/삭제에 용이하기 때문에 맨 앞의 원소값을 제거하는 기능을 제공해야 하는 큐 자료구조를 만드는 데에 있어서 별다른 제약이 없이 만들 수 있습니다. 

 하지만, 리스트가 아닌 동적 배열을 이용해서 큐 자료구조를 만드는 경우에는 상황이 조금 다릅니다. 배열은 중간 삽입/삭제 시에 배열을 재할당하는 비효율적인 동작을 해야 한다는 단점이 있습니다. 하지만 이를, 선형(Line)이 아닌 원형(Circle) 큐 방식으로 만들게 되면 해당 문제를 조금 더 효율적으로 만들 수 있게 됩니다.

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;
		}

		// _back 위치에 value를 넣음
		_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() const { return _size; }

private:
	vector<T> _container;

	int _front = 0;
	int _back = 0;
	int _size = 0;
};

 

 데이터는 기본적으로 선형(Line)으로 저장되기 때문에 이를 원형의 구조로 만들기 위해서는 큐의 마지막 위치에서 한 칸 더 이동을 하게 되는 순간, 다음 칸으로 이동하는 것이 아닌 큐의 첫번째 공간으로 이동하는 방식입니다.

 

예시를 들면, [] [] [] [] [] [] [X]    ->  [X] [] [] [] [] [] [] 이런 느낌이라고 생각하면 좋을 것 같습니다. 

 

 원형의 구조를 가지므로 큐 데이터 공간의 첫번째 인덱스가 반드시 큐의 첫번째 인덱스를 의미하는 것이 아니게 됩니다. (마지막 인덱스 또한 동일) 그렇기 때문에 원형 큐에서 큐의 가장 앞의 인덱스(_front)와 가장 뒤(_back) 인덱스의 의미를 가지는 변수를 만들고 큐에 들어있는 원소들의 개수(_size)를 저장한 변수를 추가적으로 만들어서 큐의 공간을 증설하거나, 기타적으로 큐에서 제공하는 메소드들을 구현하는데에 사용합니다.

 

이것으로 자료구조 큐에대한 소개를 마치도록 하겠습니다. 포바~!