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

queue란 자료구조에 대해 알아보겠습니다.

 

 

큐(Queue)는 스택과 마찬가지로 컴퓨터 과학에서 핵심적인 개념입니다. 어떤 표를 사기 위해 줄서는 걸 생각해보면 이해하기 쉽습니다. 줄 서는 것과 같이 먼저 들어간 항목이 먼저 나오는 (First In First Out) 원칙을 따르는 자료구조입니다.

 

큐란?

• 데이터의 삽입과 삭제가 서로 다른 위치에서 일어나는 자료구조
• FIFO: First-In-First-Out

 

큐의 응용

• 은행 대기, 식당 대기, 항공기 이착륙
• 다양한 분야의 시뮬레이션 등

 

큐 구현 방법

1. 단순 배열
2. 원형 배열
3. 연결리스트

이 글에선 원형 배열 큐만 다룹니다.

 

배열 큐의 자료구조 설계

 

• 삽입(enqueue) , 삭제(dequeue)
• isFull(가득 찼는지 검사)
• isEmpty(비었는지 검사)
• 자료의 삽입과 삭제 인덱스 변수: rear(삽입) , front(삭제)

rear 와 front의 초기값을 0으로 둡니다.
이어서 삽입 연산시 rear자리에 삽입 후 rear+1을 해줍니다.
삭제 연산에서는 front 인덱스 자리에 삭제후 front -1을 해줍니다.

 

단순 배열의 한계

선형 큐의 가장 큰 한계점은 큐의 공간 재활용 문제입니다. 선형 큐는 배열을 기반으로 구현되며, 먼저 들어온 요소가 먼저 나가는 FIFO 원칙에 따라 동작합니다. 즉, 큐의 앞쪽에 있는 요소가 삭제되고 나면, 그 자리는 비워져 있게 되며, 이후에는 그 자리를 재활용할 수 없습니다.

이를 '큐의 공간 낭비' 혹은 '큐의 비효율적인 메모리 사용'이라고 할 수 있습니다.

 

이는 큐의 앞 부분에서 요소를 삭제한 후, 빈 공간을 재사용하지 못하고, 대신 큐의 끝부분에 계속해서 요소를 추가하는 방식으로 작동하기 때문입니다.

 

원형 큐 (Circular Queue)

원형 큐(Circular Queue)는 선형 큐의 단점을 해결하기 위해 고안된 자료구조입니다.

 

선형 큐는 앞쪽에서 데이터가 빠져나갈 경우, 해당 공간을 재활용하지 못하고 뒤쪽으로 계속 데이터를 추가하는 방식을 사용하게 됩니다.

 

그러나 원형 큐는 큐의 끝 부분에 도달하면 다시 앞쪽으로 돌아가 데이터를 저장함으로써 이러한 공간의 낭비를 방지합니다.

끝 인덱스와 첫 인덱스가 이어지기에 원형으로 도식화 한 것입니다. 실제론 배열 자료구조를 씁니다.

 

원형 큐의 구현

원형 큐에서는 배열의 첫 번째 요소와 마지막 요소가 연결되어 있는 것처럼 동작합니다.

 

이를 표현하기 위해 "modulo" 연산자(%)를 사용합니다.

 

예를 들어, front나 rear 포인터의 값이 배열의 크기를 초과하면 배열의 처음으로 돌아오도록 해주는 것입니다.

즉, (front + 1) % size 또는 (rear + 1) % size 와 같은 연산을 통해 front와 rear의 위치를 업데이트합니다.

 

이를 통해 front나 rear의 값이 size와 같아지면 다시 0인덱스로 돌아오는 원형 구조를 가질 수 있습니다.

 

원형 큐의 상태 체크

또한, 원형 큐에서는 비어있는 상태와 가득 찬 상태를 구분하기 위한 특별한 방법이 필요합니다.

 

일반적으로 원형 큐에서 비어있는 상태는 front == rear로 판단하고, 가득 찬 상태는 (rear + 1) % size == front로 판단합니다.

isEmpty 연산

isEmpty 연산은 front와 rear가 같은 위치를 가리키고 있으면 큐가 비어있다고 판단합니다.

 

즉, if (front == rear) return true; 같은 로직을 사용합니다.

 

isFull 연산

isFull 연산은 rear의 다음 위치가 front를 가리키고 있으면 큐가 가득 찼다고 판단합니다.

이는 원형 큐에서 한 칸을 항상 비워두는 구현 방식을 따르기 때문입니다. 따라서 if ((rear + 1) % size == front) return true; 같은 로직을 사용합니다.

항상 원형 큐의 최대 크기는 size보다 1개 작다는 걸 주의 해야합니다.

 

 

 

원형 배열 큐 구현

public class Queue<E> {
    private int rear;
    private int front;
    private E[] queue;
    private int size;
    public Queue(int size){
        rear = 0;
        front = 0;
        this.size = size;
        queue = (E[])new Object[size];
    }
    public Queue(){
        this(10);
    }
    public boolean isFull(){
        return (rear+1)%size == front;
    }
    public boolean isEmpty(){
        return rear == front;
    }
    public void enq(E data){
        if(this.isFull()){
            return;
        }
        else{
            queue[rear] = data;
            rear = (rear+1)%size;
        }
    }
    public E deq(){
        if (this.isEmpty()){
            return null;
        }
        else{
            E temp = queue[front];
            front = (front + 1) % this.size;
            return temp;
        }
    }
}

 

<이미지 참고>

- 줄 이미지

-[출처] Queue(큐)의 구조와 c언어로 구현 [자료구조]|작성자 Sooftware

-원형 큐 이미지