Queue

Queue 기본 개념

흔히 온라인 게임을 할 때 게임이 잡히지 않으면 큐가 잡히지 않는다는 말을 사용하곤 한다. 여기에서 말하는 큐가 오늘 알아볼 Queue이다.

위에서 말했듯이 queue는 대기열의 느낌이나는 자료 구조이다.
queue는 stack과 마찬가지로 동종 아이템들로 구성된 자료 구조이다. Item이 한쪽 끝에 추가되고(enqueue) 반대쪽 끝에서 제거된다.(dequeue)
이렇듯 Queue는 FIFO ("First In First Out") 구조를 갖는다.

Queue 정의

다음은 Queue의 정의이다.

#include <iostream>
using namespace std;

template<class ItemType>
class QueueType {
private:
	ItemType* data; // 동적 할당
	int front;
	int rear;
	int maxQueue;

public:
	QueueType(int maxQueue);
	void enqueue(ItemType value);
	ItemType dequeue();
	void clear();

	bool isFull() const;
	bool isEmpty() const;
};

constructor

queue의 생성자를 보면 동적 할당을 한다.

template <class ItemType>
QueueType<ItemType>::QueueType(int maxQue){
	maxQueue = maxQue + 1;
	front = maxQueue - 1;
	rear = maxQueue - 1;
	data = new ItemType[maxQueue]
}

이상한 점이 있다 front와 rear가 같은데 왜그럴까? 또한 maxQueue에 왜 1을 추가로 더해주는 것일까? 이는 Circular Queue개념과 Reserved Space개념을 익히고 알아보자.

enqueue

rear + 1후 Item 추가

dequeue

먼저 Item을 return하고 나머지를 전부 앞으로 한칸씩 땡기는 방법을 사용할 수 있다. 그러나 이것은 시간 복잡도가 O(N)으로 별로 효율적으로 보이지 않는다.
대신 front를 앞으로 한칸 옮겨주는 것으로 개선할 수 있다.
front + 1후 반환(reserved space)

Circular Queue

Queue에 Item을 추가하려는데 rear == maxQueue - 1일 때 (앞에는 비어있음) Item을 맨 앞에 넣어주고 rear를 맨 앞으로 옮긴다.

enqueue(): rear = 0; if rear == maxQueue - 1

마찬가지로 dequeue를 하려는데 front == maxQueue - 1이면 Item을 return후 front를 앞으로 보내준다.

dequeue(): front = 0; if front == maxQueue - 1

이렇게 진행하다 보면
front == rear + 1일 때 우리는 Queue가 꽉 찼다고 생각할 수 있다.

여기서 문제가 발생한다.
front = rear + 1일 때에 Queue가 비워질 수도 있다는 점이다.

해결책은 Reserved Space를 만드는 것이다.

실제 front는 2이지만 front가 항상 reserved를 가리키도록 하는 것이다.

이렇게 구현하면 Queue가 꽉 찼을 때 조건은 다음과 같이 바뀐다.front == rear + 1 or front == (rear + 1)%maxQueue
(%는 그냥 Circular Queue가 돌다가 index범위를 벗어나는 것을 막고 첫번째로 돌아가도록 하는 것임)

Queue가 비워졌을 때는 rear == front로 조건이 바뀐다.

그리고 아까 생성자에서 rear와 front 모두 maxQueue -1이었는데 그 이유를 알 수 있다. 첫칸 부터 쓰기 위해서이다. enqueue나 dequeue를 할 때 모두 +=1 하고 maxQueue로 나눈 나머지로 값을 설정하는데 maxQueue - 1일 때 그렇게하면 첫번째 칸으로 가지기 때문이다.
그리고 maxQueue + 1인 이유는 Reserved Space를 만들어주기 위함이다.

data type 크기 만큼의 메모리 공간을 한칸 낭비한다는 점은 있다.

나머지 연산자

마지막으로 나머지 연산자들을 코드로 구현 해보자

template<class ItemType>
QueueType<ItemType>::~QueueType() {
	delete[] data; //data가 배열이라 delete[] -> 단일 객체면delete
}

template<class ItemType>
bool QueueType<ItemType>::isFull() const {
	return((rear + 1) % maxQueue == front);
}

template<class ItemType>
bool QueueType<ItemType>::isEmpty() const {
	return(rear == front);
}

template<class ItemType>
void QueueType<ItemType>::enqueue(ItemType newItem) {
	rear = (rear + 1) % maxQueue;
	data[rear] = newItem;
}

template<class ItemType>
ItemType QueueType<ItemType>::dequeue() {
	ItemType ret;
	front = (front + 1) % maxQueue; //reserved space 때문에 + 1
	ret = data[front];
	return ret;
}

소멸자에 delete[]를 사용하여 할당 해제를 구현하였고 나머지 연산은 reserved space를 활용하여 구현하였다.

queue 공부하면서 헷갈렸던거
-> 왜 enqueue시 rear + 1이고 dequeue시 front + 1인가.
enqueue 했을 때 rear + 1(뒤에 추가됨) 해주고 dequeue 했을 때 front + 1(front 빼감) 해주어야 처음에 들어온애가 나갈 때 처음으로 나갈 수 있음
1. 그림으로 생각해보기
2. 새로오는 애는 뒤에 점점 쌓이고 나가는 애는 처음에 있는 애가 나감 (식당 대기줄)
3. 사실 reserved space를 따로 구현하지는 않았음 그냥 MaxQueue + 1로 한칸 늘려주고 front가 reserved space를 계속 가리키고 있다고 생각하면서 isFull()이랑 isEmpty()정의한 것임
4. Queue를 dequeue할 때 실제론 값이 비워지지 않고 front위치만 바뀜 enqueue는 덮어 씌우는 느낌