[자료구조] 큐(Queue)와 원형큐(Circular Queue) 개념과 구현

큐(Queue)

스택과 양대산맥인 큐는 스택과 반대의 성격을 지닌 녀석입니다. 스택이 후입선출(Last In First Out)방식이었다면 큐는 선입선출(First In First Out)방식이 되지요. 스택과 큐는 컴퓨터 과학에서 아주 중요한 도구들입니다. 스택의 개념과 사용처는 지난 포스팅에서 했으니, 큐에 대해서만 설명해보도록 하겠습니다.

큐는 개념은 정말 쉽습니다. 첫번째로 들어오는 녀석을 가장 먼저 내보내는 것이 큐입니다. 현실 세계에서도 역시 큐에 개념이 사용됩니다. 버스 기다릴때나 은행 업무를 기다릴때, 가장 먼저 도착한 사람이 버스를 타거나 은행업무를 보게 되지요. 새치기하지마라 진짜

'

위의 그림 처럼 말이죠. 그냥 쭉 줄서있죠? 이런 큐를 선형큐라고 합니다.

그림에서는 보이진 않지만 가장 앞에 있는 원소를 Front, 그리고 가장 뒤에 있는 원소를 Rear라고 합니다.

큐에는 기본적으로 두 가지의 연산이 있습니다. 바로 enqueue와 dequeue입니다.

enqueue 큐에 데이터를 삽입합니다.

dequeue 큐에서 데이터를 꺼내옵니다.

선형큐는 구현하는 게 매우 간단하지만( 단지 배열로 일직선으로 구현) 치명적인 약점이 있는데요.

1) 큐에 데이터가 꽉 찼다면 데이터를 더 추가할 수 없습니다(물론 큐 사이즈를 늘리고 원소를 다시 복사하면 됩니다. 근데 시간이 안습이죠.). 

2)공간의 효율성을 고려해야합니다. 배열로 단순히 구현하면 front가 뒤로 계속 밀려 앞의 공간이 남게 되죠. 그러니까 하나의 원소가 빠져나가면 그 다음부터 모든 녀석들을 앞으로 당겨와야하니까 속도 측면에서 상당히 느립니다. 작은 데이터들이라면 물론 상관없지만, 요즘처럼 사이즈가 크고 많은 데이터를 처리하기에는 무리죠.

사용하기에는 단점이 좀 아프니까 선형큐는 개념 정도만 알고 가겠습니다.

원형큐(Circular Queue)

선형큐의 단점을 보완할 수 있는 큐로는 바로 원형큐가 있습니다. 큐를 직선 형태로 놓는 것 보다 원형으로 생각해서 큐를 구현하는 것이죠. 큐를 원형으로 생각해야되기 때문에 모듈러 연산(나머지 연산)을 해야합니다.

그림으로 설명해보도록 하지요.

우선 큐의 시작점은 어느 점이라도 됩니다. 그냥 단순히 보기 위해서 가장 아래에 있는 점을 시작 점이라고 정의해보겠습니다.

그리고 색이 칠해져있는 부분이 노드가 삽입된 상태입니다.

또한, front가 노드를 가리키고 있지 않고 그 전의 점을 가리키고 있는 이유는 우선 증가 연산 후에 데이터를 꺼내오기 때문입니다.

 

우리는 아래 구조체를 코딩을 통해서 큐를 구현할 겁니다. SIZE는 원형큐의 SIZE를 의미합니다. 그리고 front와 rear가 배열의 마지막 원소로 지정한 것은 배열 인덱스 0부터 시작하려고 하기 때문입니다(선증가 후 원소를 삽입한다는 사실만 지금은 기억하기 바랍니다.). 뭐 front와 rear를 0으로 하건 1로하건 상관없습니다.

struct cirQueue {
	
	int arr[SIZE];
	int front, rear;
	
	cirQueue() {
		front = SIZE-1;
		rear = SIZE-1;
	}
};

cirQueue()는 front와 rear의 초기값을 지정합니다. 이렇게 하고 싶지 않다면  변수를 선언할때 일반적인 구조체를 다루듯이 

cirQueue q;

q.front=q.rear=SIZE-1;

이런식으로 코딩하면 됩니다.

우리는 이제 4가지의 연산을 정의할 건데요. 잘 따라오세요.

1. isEmpty

큐가 비어있냐 아니냐를 질의하는 연산입니다. 처음 큐의 rear와 front는 같은 자리에 위치하게 됩니다. 그러니 rear와 front는 당연히 같은 값이 되지요. 그리고 큐가 삽입되고 꺼내어지고 할 때 역시 큐가 비어있게 된다면 rear와 front는 역시 같은 값이 됩니다. front를 하나 증가하고 난 이후에 데이터를 꺼내오니까요.

코드도 역시 간단하게 구현이 되는 군요.

bool isEmpty() {
		return rear == front;
}

2. isFull

큐에 데이터가 꽉차있는 상태인지 알아보는 연산입니다. rear를 하나 증가시키고 데이터를 넣으려보니까 그 자리에는 front라는 것이 자리잡고 있는 겁니다. 

여기서 중요한 사실은 큐에서 1개는 쓸 수 없다는 사실입니다. rear+1자리에 front가 있는 지 알아보기 위해서지요.

bool isFull() {
		return ((rear + 1) % SIZE) == front;
}

여기서 큐의 SIZE로 나누는 이유는 계속 rear+1이 큐의 SIZE보다 클 수 있다는 겁니다. rear가 SIZE-1의 원소(배열의 마지막 원소)를 가리키고 있고 다음 rear+1은 SIZE가 아니라 0이 되어야합니다. 그래야 원형큐가 되니까요.

아참! 간간히 눈에 보이지 않는 오류가 있는데 수식을 잘 보셔야됩니다. 덧셈보다 모듈러 연산의 우선순위가 더 높기 때문에 (rear +1 % SIZE) == font 를 하게 되면 1%SIZE 부터 계산하게 됩니다. 우리가 원하는 것은 rear를 먼저 1증가시킨 후 SIZE로 나눈 나머지를 구하는 것이니 괄호를 처리해야 합니다. 

( (rear + 1) % SIZE ) == front 로요.

3. enqueue

큐에 원소를 삽입하는 연산입니다. 우선 큐가 꽉차있는 상태인지 아닌지 부터 알아봅니다. 삽입하기 충분한 공간이 있다면 현재 rear에서 1을 증가시킵니다 다음 원소에 추가시키기 위해서요. 그자리에 원소를 삽입하면 됩니다. 

여기서도 역시 나머지 연산이 들어갑니다. 원형큐이기 때문에 SIZE보다 크면 다시 처음부터 원소가 삽입되어야 하기 때문입니다.

void enqueue(int data) {
		if (isFull()) {
			cout << "Q is full" << endl;
			return;
		}
		rear = (rear + 1) % SIZE;
		arr[rear] = data;
}

4. dequeue

큐에 원소를 꺼내어 오는 연산입니다. 맨 처음 들어간 원소는 front+1이 됩니다. 그러니까 우선 큐가 비어있는 지 확인하는 작업이 필요합니다. 비어있는 큐에 원소를 꺼내올 수 없으니까요.

이후 front를 한칸 증가시켜 그 원소를 빼내옵니다. 그러고 나면 front는 빈 원소를 가리키게 되는 것이죠.

역시 모듈러 연산이 쓰이는 군요. 이유는 위와 같습니다.

int dequeue() {
		if (isEmpty()) {
			cout << "Q is empty" <<endl;
			return INF;
		}
		return arr[front = (front + 1) % SIZE];
}

전체 코드

이렇게 큐의 연산을 모두 끝냈습니다. 전체 코드는 아래에 있습니다.

#include <iostream>
#define INF 987654321
#define SIZE 6
using namespace std;

struct cirQueue {
	
	int arr[SIZE];
	int front, rear;
	
	cirQueue() {
		front = SIZE-1;
		rear = SIZE-1;
	}
	
	bool isEmpty() {
		return rear == front;
	}
	
	bool isFull() {
		return ((rear + 1) % SIZE) == front;
	}

	void enqueue(int data) {
		if (isFull()) {
			cout << "Q is full" << endl;
			return;
		}
		rear = (rear + 1) % SIZE;
		arr[rear] = data;
	}

	int dequeue() {
		if (isEmpty()) {
			cout << "Q is empty" << endl;
			return INF;
		}
		return arr[front = (front + 1) % SIZE];
	}
};

int main() {
	
	cirQueue q;
	for (int i = 1; i <= 6; i++)
		q.enqueue(i);
	q.enqueue(10);
	while (!q.isEmpty())
		cout << q.dequeue() << endl;
	cout << q.isEmpty() << endl;
	cout << q.isFull() << endl;
}

결과는?

메인함수에서 코드를 보면 왜 이렇게 결과가 나오는지 이해할 수 있을 겁니다.