Queue

Queue 는 Stack과 단짝으로 나오는 친구 중 하나이다.

기본적으로 선입선출이라는 특징을 갖고 있다.

주로 구현에서는 대기열 처리를 들 수 있다. 은근히 많이 쓰인다. 서버에서도 Session을 날릴 때, 일 처리 순으로 Queue사용하고, 생각해보니 굉장히 중요한 녀석이다. 솔직히 Stack은 잘 사용 안했던거 같은데 말이다.

 

이러한 기능을 수행한다. 보통 value를 받을 때, pop에서 return되는 값을 많이 받지만 단순 접근에서는 front를 이용 할 수 있다. front 는 이번에 처음본 듯.

 

queue를 간단히 구현해보면

 

#include <iostream>
#include <vector>
#include <stack>
#include <list>
#include <queue>
using namespace std;
 
template<typename T>
class Queue // ListQueue
{
public:
	void push(const T& value)
	{
		_container.push_back(value);
	}
	void pop()
	{
		//만약 vector로 구현 시 시작 지점에서 하나를 지우고 n번 앞으로 데이터를 복사해준다. 비효율 적이다.
		//_container.erase(_container.begin());
		_container.pop_front();
		// 그리하여 list를 통해 구현하는게 효율적이다.
	}
	T& front()
	{
		return _container.front();
	}
	bool empty() { return _container.empty(); }
	int size() { return _container.size(); }
private:
	list<T> _container;
};



int main()
{
	queue<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();
}

이다. 여기서 강의는 deque를 언급하는데, C#을 사용하던 나에게 낯선 용어이다. 고로 한번 훑어보고 가자.

 

여기 링크를 참고하여 공부하면 금방 이해가능하다.

https://notepad96.tistory.com/entry/STL-Deque-%EC%83%9D%EC%84%B1-%EC%82%BD%EC%9E%85-%EC%82%AD%EC%A0%9C-%EB%93%B1-%EC%82%AC%EC%9A%A9%EB%B2%95

[STL] Deque 생성, 삽입, 삭제 등 사용법

 

Vecter의 경우 동적배열을 통해 배열의 크기가 초과시, 새로운 배열을 만들어 데이터를 이동시켜준다. 하지만 배열을 만들때, 배열의 0번째부터 복사가 이루어진다.

 

하지만 deque의 경우 배열 크기가 부족한 경우 동일한 크기의 배열을 다른 메모리에 연속적으로 할당하고, 이를 이어붙여 사용한다. 

 

만약 ㅁㅁㅁㅁ 4 크기의 배열이 가득 찼다면, 

vecter의 경우 4의 0.5 곱한 크기 만큼인 ㅁㅁㅁㅁㅁㅁ를 만들어 데이터를 이동시킨다면,

deque의 경우 4 크기의 배열에 ㅁㅁㅁ / ㅁㅁㅁㅁ / ㅁㅁㅁ 를 만들어 연속된 배열을 연결시켜준다. 그리하여 배열의 front 쪽에도 데이터를 삽입할 수 있으며, back 쪽에도 데이터를 삽입 할 수 있게 된다. 언급되어 있는 블로그에는 자세한 코드를 들여다 보지 못하므로, 배열이 몇 크기만큼 생성되는지 , 연속된 배열의 링크는 포인터로 작동하는지는 알 수 없지만 확실히 vector의 단점을 보완해줄 수 있는 Container라고 생각이 든다.

 

queue를 f12를 통해 보면 

처음 담아주는 Container이 deque라는 것을 알 수 있다. 

 

하지만 vector을 통해 구현해보면서 공부해보자.

 

template<typename T>
class ArrayQueue
{
public:
	ArrayQueue()
	{
		_containe.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(); // capacity
		_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라는 점인데, _front와 _back을 이용하여, 배열을 순환하는 구조로 만들어 준다. 

_size는 실직적으로 넣어진 데이터의 크기값을 의미하며,  _container.size()는 vector의 capacity(용량)라고 생각하면 된다. 만약 _size가 _container.size()의 크기보다 커질 경우 vector의 capacity를 늘려야 하므로 void push() 함수에서 먼저 check해주고, push가 이루어 지는 것을 알 수 있다.