[자료구조] 큐(queue)와 원형큐(Circular Queue)

큐

큐는 데이터를 일시적으로 쌓아 두는 기본 자료구조이다. 아래 그림과 같이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO : First In First Out) 구조로 되어있다. 

큐에 데이터를 넣는 과정을 인큐(en-queue)라 하고, 데이터를 꺼내는 작업을 디큐(de-queue)라 한다.  또 데이터가 나오는 쪽을 프런트(front, 맨 앞)이라고 하고, 데이터를 넣는 쪽을 리어(rear, 맨 뒤)라고 한다.

 

원형 큐/순환 큐(Circular Queue)

자바에선 기본적으로 큐에 대한 인터페이스를 제공한다. 큐 인터페이스를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다. 

 

보통 우선순위큐를 제외하면 다음과 같이 사용했을 것이다. 

Queue<Integer> q = new LinkedList<>();

보통 코딩테스트를 풀 때는 위와 같은 큐를 사용하거나 경우에 따라 PriorityQueue(우선순위 큐)를 사용하지만 큐의 원리를 이해하기 위해 배열을 사용하여 구현하고자 한다. 

 

배열로 큐를 구현할 때는 몇 가지 문제점이 있다.

1. 고정된 크기: 배열은 크기가 고정되어 있어, 큐가 배열의 마지막 위치에 도달하면 더 이상 데이터를 추가할 수 없다.  이는 큐가 가득 찼을 때 배열의 크기를 재조정하거나 새로운 배열을 할당해야 함을 의미한다.
2. 비효율적인 디큐 연산: 데이터를 디큐할 때, 배열의 맨 앞 인덱스의 데이터를 제거하고 나머지 데이터를 한 자리씩 앞으로 이동시켜야 한다.  이는 매 디큐 연산마다 O(n)의 시간 복잡도를 가지며 매우 비효율적이다.

이 문제를 해결하기 위한 방법 중 하나는 원형 큐/순환 큐(Circular Queue)를 사용하는 것이다. 순환 큐는 배열의 처음과 끝이 연결된 것처럼 동작하여 배열의 크기를 보다 효율적으로 사용할 수 있게 한다.  프런트와 리어 포인터를 사용하여 배열 내에서 큐의 시작과 끝을 관리하며, 배열의 끝에 도달하면 포인터를 배열의 처음으로 이동시킨다.

 

구현 (java)

초기 생성자

public class CircleQueue {
    private int[] que;     // 큐의 배열
    private int capacity;  // 큐의 용량
    private int front;     // 맨 앞의 요소 커서
    private int rear;      // 맨 뒤에 요소 커서
    private int num;       // 현재 데이터의 개수
    
    // 생성자
    public CircleQueue(int maxLen) {
        this.front = this.num = this.rear = 0;
        this.capacity = maxLen;
        que = new int[maxLen];
    }

본 큐를 생성하기 위한 생성자 코드이다. 생성 시 num, front, rear는 0으로 초기화하며, 매개변수 maxLen를 통해 큐의 용량(capacity)을 입력받는다. 

 

인큐(enqueue)

// 큐에 데이터를 인큐
public int enqueue(int data) {
    if (this.num >= this.capacity) {
        throw new RuntimeException("큐가 가득 찼습니다.");
    }
    que[this.rear++] = data;
    this.num++;
    if (this.rear == this.capacity) {
        this.rear = 0;
    }
    return data;
}

큐에 데이터를 삽입하는 인큐에 대한 코드이다. 인큐는 큐가 가득 차면 안되므로 예외를 추가하였다. (num >= capacity)

rear 포인트가 가르키는 인덱스에 데이터를 추가하고 rear 포인트를 한 칸 증가시킨다. 여기서 고려할 상황은 rear 포인트가 용량이랑 같게 되면 범위를 초과하는 것이므로 그때는 다시 배열의 첫 인덱스인 0으로 포인트 이동시켜야 한다. (배열은 0 ~ n-1까지가 범위이기 때문)

 

데이터가 [3, 4, 5, 6, 7, 1]  차례대로 큐에 들어간 그림이다. 여기서 8을 인큐한다고 하면 아래 그림과 같이 진행된다.

인큐의 예시

 

디큐(dequeue)

// 큐에 데이터를 디큐
public int deque() {
    if (num <= 0) {
        throw new RuntimeException("큐가 비어 있습니다.");
    }

    int data = que[front++];
    num--;
    if (front == capacity) {
        front = 0;
    }
    return data;
}

큐에서 데이터를 디큐하고 그 값을 반환하는 코드이다. 디큐를 데이터를 꺼내는 작업이기 때문에 큐가 비어있는 것에 대한 예외가 필요하다. ( num <= 0 ) 

디큐도 마찬가지로 front 포인트를 반환데이터로 활용하며, 이후 front 포인트를 한 칸 증가시켜 준다. 디큐도 인큐와 마찬가지로 순환큐의 특성 때문에 포인트가 용량범위를 넘어가면 다시 0으로 이동시켜 준다.

디큐의 예시

 

그 외

// 큐에서 데이터를 피크(프런트 요소)
public int peek() {
    if (num <= 0) {
        throw new RuntimeException("큐가 비어 있습니다.");
    }
    return que[front];
}

// 큐를 비움
public void clear() {
    num = front = rear = 0;
}

// 큐에서 특정 데이터가 인덱스를 반환(없을 시 -1 반환)
public int indexOf(int x) {
    for (int i = 0; i < num; i++) {
        int idx = (i + front) % capacity;
        if (que[idx] == x) {
            return idx;
        }
    }
    return -1;
}

public int getCapacity() {
    return capacity;
}

public int size() {
    return num;
}

public boolean isEmpty() {
    return num <= 0;
}

public boolean isFull() {
    return num >= capacity;
}

피크 메서드는 맨 앞의 데이터를 들여다보는 메서드이며, que [front] 값만 확인한다. clear 메서드는 모든 데이터를 삭제하는 메서드이며, 인큐와 디큐가 num. rear, front 값을 바탕으로 수행되므로 실제 배열을 초기화하지 않고도 처리가 가능하다. 

 

검색 메서드 indexOf는 큐에 특정 데이터가 있는지 확인하는 메서드로 반환 시 해당 데이터의 인덱스를 반환한다. 단 찾고자 하는 데이터가 없을 경우 -1을 반환한다. 스캔 시 물리적인 첫 요소(0)가 아닌 front의 요소부터 스캔되므로 (i + front) % capacity로 계산하게 된다.  

 

그 외에도 최대 용량을 확인하는 메서드(getCapacity), 데이터 개수를 확인하는 메서드(size), 큐가 비었는지, 가득 찼는지 확인하는 메서드가 구현되어 있다. 

 

구현 코드 전체 

package fc.queue;

/**
 * 배열로 구현한 원형큐
 */
public class CircleQueue {
    private int[] que;     // 큐의 배열
    private int capacity;  // 큐의 용량
    private int front;     // 맨 앞의 요소 커서
    private int rear;      // 맨 뒤에 요소 커서
    private int num;       // 현재 데이터의 개수

    public CircleQueue(int maxLen) {
        this.front = this.num = this.rear = 0;
        this.capacity = maxLen;
        que = new int[maxLen];
    }

    // 큐에 데이터를 인큐
    public int enqueue(int data) {
        if (this.num >= this.capacity) {
            throw new RuntimeException("큐가 가득 찼습니다.");
        }
        que[this.rear++] = data;
        this.num++;
        if (this.rear == this.capacity) {
            this.rear = 0;
        }
        return data;
    }

    // 큐에 데이터를 디큐
    public int deque() {
        if (num <= 0) {
            throw new RuntimeException("큐가 비어 있습니다.");
        }

        int data = que[front++];
        num--;
        if (front == capacity) {
            front = 0;
        }
        return data;
    }

    // 큐에서 데이터를 피크(프런트 요소)
    public int peek() {
        if (num <= 0) {
            throw new RuntimeException("큐가 비어 있습니다.");
        }
        return que[front];
    }

    // 큐를 비움
    public void clear() {
        num = front = rear = 0;
    }

    // 큐에서 특정 데이터가 인덱스를 반환(없을 시 -1 반환)
    public int indexOf(int x) {
        for (int i = 0; i < num; i++) {
            int idx = (i + front) % capacity;
            if (que[idx] == x) {
                return idx;
            }
        }
        return -1;
    }

    public int getCapacity() {
        return capacity;
    }

    public int size() {
        return num;
    }

    public boolean isEmpty() {
        return num <= 0;
    }

    public boolean isFull() {
        return num >= capacity;
    }
}

 

자바에서 큐를 선언하는 방식

package fc.queue;

import java.util.LinkedList;
import java.util.Queue;

public class queue_1 {
    public static void main(String[] args) {
        Queue queue = new LinkedList();

        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);

        System.out.println(queue);
        System.out.println(queue.poll());
        System.out.println(queue);
        System.out.println(queue.peek());
        System.out.println(queue);

        System.out.println(queue.contains(3));
        System.out.println(queue.size());
        System.out.println(queue.isEmpty());
    }
}

Java에서 Queue 인터페이스는 다양한 큐 구현체를 지원하며, 대표적으로 LinkedList는 이 인터페이스를 구현하는 클래스 중 하나이다. Queue 인터페이스와 LinkedList 클래스에서 자주 사용하는 주요 메서드는 다음과 같다:

1. add(E e):
   • 큐의 끝에 지정된 요소를 추가한다. 큐가 제한을 초과할 때 예외를 발생시킨다.
2. offer(E e):
   • 큐의 끝에 지정된 요소를 추가한다. 큐가 제한을 초과할 경우 예외를 발생시키지 않고 false를 반환한다.
3. remove():
   • 큐의 머리(head)에 있는 요소를 제거하고 반환한다. 큐가 비어 있을 때는 예외를 발생시킨다.
4. poll():
   • 큐의 머리(head)에 있는 요소를 제거하고 반환한다. 큐가 비어 있을 때는 null을 반환한다.
5. element():
   • 큐의 머리(head)에 있는 요소를 반환한다. 큐가 비어 있을 때는 예외를 발생시킨다.
6. peek():
   • 큐의 머리(head)에 있는 요소를 반환한다. 큐가 비어 있을 때는 null을 반환한다.

이 메서드들은 큐의 표준 동작을 제공한다. add와 offer는 요소를 추가하는 메서드이며, remove와 poll은 요소를 제거하고 반환하는 메서드이다. element와 peek은 요소를 반환하지만 큐에서 제거하지 않는 메서드이다.

• add와 remove는 예외를 발생시키며, offer와 poll은 예외를 발생시키지 않고 대신 특정 조건에서 null 또는 false를 반환한다.
• element와 peek도 마찬가지로 element는 큐가 비어 있을 때 예외를 발생시키지만, peek은 null을 반환한다.