2. 큐(Queue) / 원형큐(Circular Queue)

2. 큐(Queue)

- 한쪽 끝(뒤)에서는 자료를 삽입하고, 다른 한쪽 끝(앞)에서 자료를 출력하는 형태의 자료구조

- 가장 먼저 넣은 것이 가장 먼저 나오게 되므로 First In First Out(FIFO)라고 한다.

- front : 출력이 일어나는 곳

- rear : 삽입이 일어나는 곳

[ 배열을 이용한 큐 구현 ]

- 기본적인 형태의 Queue를 선형큐(Linear Queue)라고 한다. 선형큐의 단점은 데이터를 출력한 영역은 재사용 할 수 없다는 것이다.

(선형큐에 데이터를 꽉채우고 모두 꺼내면 front와 rear 모두 마지막 Index를 가리키게 된다. )

- 이러한 문제점를 개선하기 위해 원형큐(Circular Queue)로 구현한다. 아래와 같이 큐의 끝의 다음이 처음이 되도록 구현된 형태이다.

구현 방식의 차이는 index값을 더하는 처리를 할 때, Queue의 최대 size를 넘어가지 않도록 나머지 연산자를 취해주는 것 밖에 없다.

0. 초기 상태

1. push 연산 : 큐에 데이터를 삽입

: rear에 데이터를 삽입한 후, rear를 하나 증가시킨다. 

: 원형큐이므로 rear가 Queue의 최대 size를 넘지 않도록, 최대 size로 나눈 나머지로 나눠준다.

data[rear] = 4;
rear = (rear + 1) % MAX_QUEUE_SIZE;

data[rear] = 3;
rear = (rear + 1) % MAX_QUEUE_SIZE;

2. pop 연산 : 큐에서 데이터를 꺼낸다.

: front에 있는 데이터를 꺼내고, front를 1 증가시킨다.

: 원형큐이므로 front가 Queue의 최대 size를 넘지 않도록, 최대 size로 나눈 나머지로 나눠준다.

int result = data[front];
front = (front + 1) % MAX_QUEUE_SIZE;

return result;

3. Empty 연산 : 큐가 비었는지 확인한다.

: 큐가 비어있는 경우, front와 rear는 같은 곳을 가리키게 된다. (초기 상태를 기억하면 편함)

4. Full 연산 : 큐가 가득찼는지 확인한다.

: 원형 큐이므로, 비어있을 때와 꽉차있을 때를 구분하기 위해 Queue의 마지막은 사용하지 않는다.

아래와 같이 rear + 1을 큐의 최대 size로 나눈 값이 front와 같을 경우 큐가 가득찬 상태임을 나타내기로 약속한다.

예시) 

rear = 4, front = 0, Queue의 최대 size = 5(0~4까지)

(rear + 1) % (Queue의 최대 size) = 0 = front이므로 큐가 가득찬 상태이다.

5. Top 연산 : 큐에서 가장 위에 있는 데이터를 확인한다.

: 현재 front에 있는 값을 리턴한다. pop과는 다르게 front + 1을 하지 않아 front에 있는 데이터는 그대로 유지된다.

6. Size 연산 : 큐에서 현재 저장되어 있는 데이터의 개수를 확인한다.

[ 최종 구현(C++)]

#include <stdio.h>
#define MAX_QUEUE_SIZE 100002

template <typename T>
class Queue
{
public:
	T data[MAX_QUEUE_SIZE];
	int rear;
	int front;

	Queue()
	{
		rear = 0;
		front = 0;
	}

	void push(T item)
	{
		data[rear] = item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = data[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty() {return (this->front == this->rear);}
};