STL - queue

큐는 선입선출을 원칙으로 하는 자료구조다.

때문에 보통 순서대로 처리해야하는 로직에서 사용한다.

예를들어 HTTP 요청을 하고 응답을 받기까지 꽤나 시간이 걸리는데,

그 응답을 즉각즉각 화면에 표시해야한다면 큐를 사용해볼 수 있다. 

즉, 데이터를 화면에 보여주기 전에 미리 여러개의 데이터를 요청하고, 응답을 받는대로 큐에 넣는다.

화면에 데이터를 표시해야할 때가되면 큐에서 데이터를 꺼내서 표시한다.

이렇게하면 응답이 온 순서대로, 지연시간없이 화면에 데이터를 표시할 수 있다.

 

 

보통은 이런 원형큐를 쓴다.

 

또다른 예는 자바스크립트 런타임의 이벤트루프에서 찾아볼 수 있다.

 

 

자바스크립트 런타임의 이벤트루프

 

https://dev.to/lydiahallie/javascript-visualized-event-loop-3dif

자바스크립트는 싱글스레드 환경에서 돌지만, 비동기식으로 동작한다.

그게 가능한 이유는 이벤트루프를 돌면서 함수를 실행할 시점을 체크하고, 적절한 시점에 함수를 실행하기 때문이다.

즉, setTimeOut이라는 함수를 쓰면 webAPI에서 루프를 돌면서 시간을 재고, (예를들어) 3초가 지나면 setTimeOut의 인자로 넣었던 함수를 작업큐에 넣는다. 콜스택이 비면, 작업큐에 들어간 작업들은 순차적으로 실행된다.

큐가 있기에 콜스택이 빌때까지 기다렸다가, 작업해야할 것들을 순차적으로 처리할 수 있다.

 

하나만 더 예시를 들어보자.

 

게임프로그래밍에서의 오브젝트 풀

만약 FPS게임을 만든다고 가정해보자. 아마도 수많은 총알을 런타임에 생성해야 할 것이다.

이 작업은 매우 무겁다. 때문에 대부분의 FPS 게임에서는 총알을 재사용한다. (혹은 아예 만들지 않거나)

이를 위해 오브젝트 풀이라는 테크닉을 사용한다.

아주 간단하게 설명해보자면 이렇게 된다.

 

 

 

 

1. 처음 총알을 100개 정도 만들어놓고 비활성화해둔다. 이 100개의 총알은 큐안에 들어가있다.

2. 총을 쏠때 큐에서 총알을 꺼내어 사용한다. 발사한 총알은 물체에 부딪쳐 파괴되는데, 진짜로 파괴하는게 아니라 비활성화한다.

3. 비활성화된 총알은 큐의 맨뒤로 다시 삽입된다. 

 

이러면 화면에는 최대 100개의 총알이 보일 수 있지만 끊임없이 재사용하기 때문에 매번 생성과 파괴를 하지않고 무한대로 사용가능하다.

 

 

참고를 위해 필자가 직접 구현한 큐를 올린다.

 

### 정적배열로 구현한 원형큐


#include "stdafx.h"

#define MAX_QUEUE_SIZE 8

/*

모든 원소가 차있을때도, 비어있을때도 프론트와 리어는 같다. 이 상태를 구분하려면 front와 rear는 
같은 곳을 가리키면 안된다.
따라서 하나의 배열방을 비워둬야 한다.

*/



//정적배열로 구현한 큐
template<typename T>
class MyQueue
{
private:
	T m_arr[MAX_QUEUE_SIZE];
	int m_iFront;
	int m_iRear;
	
public:
	MyQueue() :m_iFront(0), m_iRear(0){};
	~MyQueue() {};

public:
	bool isEmpty() { return (m_iFront == m_iRear); }
	void Clear() { while (!isEmpty()) Dequeue(); }
	bool isFull() { return ((m_iRear + 1) % MAX_QUEUE_SIZE) == m_iFront; }
	
	void Enqueue(T _t) 
	{ 
		if (isFull()) return;
		m_iRear = (m_iRear + 1) % MAX_QUEUE_SIZE;
		m_arr[m_iRear] = _t; 
	}
	
	//동적할당한 것은 사용자보고 지우라 합시다.
	T Dequeue()
	{
		if (isEmpty()) return NULL;
		m_iFront = (m_iFront + 1) % MAX_QUEUE_SIZE;
		T tmp = m_arr[m_iFront];
		m_arr[m_iFront] = NULL; 
		return tmp; 
	}
	
	T peek() {  int index = (m_iFront + 1) % MAX_QUEUE_SIZE;  return m_arr[index]; }
	
	//rear - front가 음수인 경우에는 MAX_QUEUE_SIZE 만큼 더해서 rear - front의 반대를 취하고, 
	//rear - front가 양수인 경우에는 rear - front + MAX_QUEUE_SIZE 가 MAX_QUEUE_SIZE보다 
  //커지니까 % MAX_QUEUE_SIZE를 했다.
	int Size() { return (m_iRear - m_iFront + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE; }

	void Dump() { for (int i = m_iFront +1 ; i <= m_iRear; ++i) { cout << m_arr[i] << endl; } }
};

void main()
{
	MyQueue<int> q;
	q.Enqueue(1);
	q.Enqueue(2);
	q.Enqueue(3);
	q.Enqueue(4);
	q.Enqueue(5);
	q.Enqueue(6);
	q.Enqueue(7);
	q.Enqueue(8);
	q.Enqueue(9);
	q.Enqueue(10);
	q.Enqueue(11);
	q.Enqueue(12);
	q.Enqueue(13);

	q.Dump();
	cout << "==========================================" << endl;
	q.Clear();
	q.Dump();

}
```

Mar 2, 2020 

### 동적배열로 구현한 원형큐

```cpp
#include "stdafx.h"

/*

모든 원소가 차있을때도, 비어있을때도 프론트와 리어는 같다. 대신 이 상태를 구분하는 것은 size다.
이는 동적배열의 특성이 아니라 그냥 size변수의 유무의 차이다.

연결리스트로 구현한 큐와 비교

장점
1. new 연산의 빈도가 적다
연결리스토 구현하면 enqueue마다 new 연산을 한다. 동적배열로 구현한 큐는 큐가 꽉찼을때만 
new 연산을 한다.

단점
2. reserve를 쓰지 않는 이상 메모리 낭비가 있을 수 있다.
이건 벡터의 특성과 같다. 연결리스트로 하면 필요한 만큼의 메모리만 생성하지만, 동적배열은 
capacity/2 만큼의 배열방을 더 가진 배열을 생성하기 때문에
메모리가 낭비될 가능성이 있다.

*/
//동적배열로 구현한 큐

template<typename T>
class MyQueue
{
private:
	T* m_arr;
	int m_iFront;
	int m_iRear;
	int m_iSize;
	int m_iCapacity;

public:
	MyQueue() :m_iFront(0), m_iRear(0), m_iCapacity(0), m_iSize(0), m_arr(nullptr) { };
	~MyQueue() { delete[] m_arr; };

public:
	bool isEmpty() { return m_iSize <= 0; }
	void Clear() { while (!isEmpty()) Dequeue(); }

	void Enqueue(T _t)
	{
		Expand_if_Full();
		//한 칸을 비워둘 필요가 없기 때문에 일단 리어에 넣은다음에 리어를 증가시키게 된다.
		m_arr[m_iRear] = _t;
		m_iRear = (m_iRear + 1) % m_iCapacity;
		++m_iSize;
	}

	//동적할당한 것은 사용자보고 지우라 합시다.
	T Dequeue()
	{
		if (isEmpty()) return NULL;
		T tmp = m_arr[m_iFront];
		//마찬가지로 일단 프론트에 있는걸 지우고 프론트를 증가시킨다.
		m_arr[m_iFront] = NULL;
		m_iFront = (m_iFront + 1) % m_iCapacity;
		--m_iSize;
		return tmp;
	}

	T peek() { return m_arr[m_iFront]; }

	int Size() { return m_iSize; }
	int Capacity() { return m_iCapacity; }

	//그냥 front에서 size만큼 출력해주면 된다.
	void Dump() 
	{ 
		int index = m_iFront;
		for (int i = 0; i < m_iSize; ++i) 
		{
			cout << m_arr[index] << endl; 
			++index;
		}
	
	}

private:
	bool isFull() { return m_iSize >= m_iCapacity; }

	void Expand_if_Full()
	{
		if(isFull())
		{
			int newArrSize;

			//꽉 차 있으면 m_iCapacity/2 만큼 증가시킨 동적배열을 만든다. 
			//m_iCapacity/2가 1보다 작으면 1만큼 증가한 동적배열을 만든다.
			if ((m_iCapacity >> 2) <= 1)
				newArrSize = m_iCapacity + 1;
			else
				newArrSize = m_iCapacity + (m_iCapacity >> 2);

			T* newArr = new T[newArrSize];
			memset(newArr, 0, sizeof(T) * newArrSize);
			memcpy(newArr, m_arr, sizeof(T) * m_iCapacity);
			delete m_arr;
			m_arr = newArr;
			m_iRear = m_iCapacity; //리어를 확장하기 전의 capacity로 한다. 중요.
			m_iCapacity = newArrSize;
		}
	}
};

void main()
{
	MyQueue<int> q;
	q.Enqueue(1);
	q.Enqueue(2);
	q.Enqueue(3);
	q.Enqueue(4);

	q.Dequeue();
	q.Dequeue();

	cout << "================Dump======================" << endl;
	q.Dump();
	cout << "사이즈: " << q.Size() << endl;
	cout << "캐퍼시티: " << q.Capacity() << endl;
	cout << "비어있는가?: " << q.isEmpty() << endl;

	cout << "===============Peek======================" << endl;
	cout << q.peek() << endl;

	cout << "================Clear======================" << endl;
	
	q.Clear();
	q.Dump();

}