[자료구조] 큐의 개념, 배열로 큐 구현하기(원형 큐)

큐(Queue)

큐는 먼저 들어간 데이터가 먼저 나가는 FIFO(First in, First Out)의 구조를 가지는 자료구조이다.

큐는 일상생활에서도 많이 볼 수 있다. 예를 들면 매표소, 은행 대기표, 식당 등 줄을 세우고 먼저 온 사람이 먼저 서비스를 받는 형태를 모두 큐라고 볼 수 있다.

 

실제로 큐를 구현하기에 앞서 어떤 연산과 변수들이 필요할지 생각해보자.

핵심이 되는 연산은 넣고(enqueue), 빼는(dequeue) 연산이다. 그리고 데이터가 들어오는 곳과 나가는 곳의  위치를 구분하기 위한 변수 front(앞쪽), rear(뒤쪽)가 필요하다.

 

 

 

배열로 큐 구현하기

우리가 실제로 줄을 서는 것 처럼 큐를 구현해보자.

제일 앞사람이 일을 마치고 빠져나가면, 뒤에 사람들은 한칸씩 앞으로 이동하는 방식이다.

삽입할 때는 별 문제가 없어 보인다. 이제 데이터를 삭제해보자.

F의 위치는 그대로 유지시키면서 삭제를 하므로 삭제 시 뒤에 있는 데이터들을 전부 앞으로 옮겨야 한다. 삭제를 하는 것보다 데이터를 옮기는데 더 많은 연산을 하고 있다.

따라서 데이터를 전부 이동시키는 방식이 아니라, F만 이동하는 방식으로 연산의 낭비를 줄이고자 한다.

 

 

그럼 F의 위치를 이동하는 방식으로 큐를 구현해보자.

이번에는 다른 문제가 발생한다.

이렇게 삽입과 삭제를 반복하다보면 배열이 꽉 차지도 않았는데 삽입이 불가능해지는 문제가 발생한다.

이 문제를 해결하기 위해서는 순환하는 형태로 큐를 구현해야 한다.

 

 

 

 

원형 큐(Circular Queue)

원형 큐는 아래와 같이 순환하는 구조를 가진 큐를 말한다.

원형 큐

이런 형태를 아래와 같이 직관적으로 표현하도록 하겠다. 

그림은 확연히 달라졌지만, 삽입과 삭제 방식은 지금까지와 똑같고, 그저 배열의 끝에 도달했을 때 다시 처음 위치로 순회하는 방식으로만 바뀌었을 뿐이다.

 

 

이 원형 큐에도 한가지 문제가 있다. 추가로 데이터를 삽입해서 배열을 꽉 채워보자.

 

이제 배열의 데이터를 전부 삭제해보자.

삽입과 삭제는 문제가 없다. 하지만 문제는 상태를 구분해야 될 때 발생한다.

꽉 찬 경우와 비어 있는 경우 모두 R 다음에 F가 위치하므로, R과 F의 위치를 이용해서 텅 빈 경우와 꽉 찬 경우를 구분할 수가 없다.

 

 

이 문제에 대한 간단한 해결책은 배열을 꽉채우지 않고 N-1개가 채워졌을 때 꽉찬 것으로 간주하는 것이다.

그리고 한 칸을 비워둔 상태로 시작하기 위해서 삽입, 삭제 시 F와 R을 한 칸 이동시킨 뒤에 연산을 수행한다.

삽입

삭제

이제 F와 R의 위치를 이용해서 꽉 찬 상태와 비어 있는 상태를 구분할 수 있다.

F == R는 비어있는 상태를 의미하고 R + 1 == F는 꽉찬 상태를 의미한다.

이제 문제가 해결되었으니 원형 큐 코드를 작성해보자.

 

 

 

코드(C++)

#include <iostream>
 
using namespace std;
 
const int maxSize = 5;
 
class MyQueue
{
public:
    int IsEmpty();
    int IsFull();
    void Enqueue(int t);
    int Dequeue();
 
private:
    int front = 0, rear = 0;
    int queue[maxSize];
 
};
 
int MyQueue::IsEmpty()
{
    if(front == rear)
        return true;
 
    return false;
}
 
int MyQueue::IsFull()
{
    if ((rear + 1) % maxSize == front)
        return true;
 
    return false;
}
 
void MyQueue::Enqueue(int t)
{
    if (IsFull()) 
    {
        cout << "큐가 꽉찼습니다" << endl;
        return;
    }
 
    rear = (rear + 1) % maxSize;
    queue[rear] = t;
}
 
int MyQueue::Dequeue()
{    
    if (!IsEmpty())
        return queue[++front % maxSize];
 
    return -1;
}
 
int main()
{
    MyQueue q;
 
    q.Enqueue(1);
    q.Enqueue(2);
    q.Enqueue(3);
    q.Enqueue(4);
 
    while (!q.IsEmpty())
        cout << q.Dequeue() << endl;
}