큐: 기본 개념과 구현

들어가며

최초 작성일(yy/mm/dd): 24/01/10 최초 작성

학습 목표

1. 큐의 기본적인 개념과 연산, 쓰임을 이해한다.
2. 자바의 제네릭을 이용해 큐 자료구조를 구현해본다.

학습 상황

• 큐를 이해하고 어떤 상황에서 쓰일지 고민해볼 필요가 있었다.
• 삼성 SW 역량테스트 B형에 대비해, 구현 과정에서도 java.util 내 자료구조 ArrayList 등을 이용하지 않는다.

큐: 기본 개념

큐(Queue)란 무엇인가?

Fig 1. 큐의 기본 구조
출처: geeksforgeeks.com

큐의 개념

큐는 한 쪽 끝에서는 삽입(enqueue)이 이루어지고, 다른 한 쪽 끝에서는 삭제(dequeue)가 이루어지는 자료구조를 의미합니다. 양쪽 끝에 모두 접근할 수 있지만, 실행할 수 있는 연산은 다릅니다.

따라서 FIFO(First In, First out), 즉 먼저 들어간 요소가 먼저 나오게 됩니다. 이는 티켓 줄서는 것과 비슷합니다.

가장 앞에 있는(=순서가 가장 빠른) 요소를 가리키는 포인트는 front(head), 가장 뒤에 있는(=순서가 가장 느린) 요소를 가리키는 포인터는 rear(tail)로 부를 수 있습니다.

큐의 종류

1. 원형 큐

   Fig 2. 원형 큐의 기본 구조와 동작
   출처: geeksforgeeks.com

   큐의 마지막 위치가 다시 처음 위치에 연결되어 원처럼 이어지는 큐입니다. ‘링 버퍼’(Ring Buffer)라고도 불립니다. 메모리 관리, traffic system, CPU 스케쥴링에서 쓰입니다. 원형 큐는 다른 글에서 자세하게 살펴보겠습니다.
   

2. 입력 제한 큐

   Fig 3. 입력 제한 큐의 기본 구조
   출처: geeksforgeeks.com

   입력 제한 큐에서, 한 쪽 끝은 삽입과 삭제 모두 가능하지만, 한 쪽 끝(head)은 삭제만 가능합니다. 이는 (1) FIFO 순서로 정렬되지만 (2) 최근에 삽입된 자료를 삭제할 필요가 있는 경우에 쓰입니다.
   

3. 출력 제한 큐

   Fig 4. 출력 제한 큐의 기본 구조
   출처: geeksforgeeks.com

   출력 제한 큐에서는 양 쪽 끝 모두 삽입은 가능하지만, 삭제는 한 쪽(head)에서만 가능합니다. 우선순위에 따라 가장 앞(head)의 input을 먼저 실행해야 하는 경우에, 출력 제한 큐는 유용합니다.
   

4. 더블-엔디드-큐 (데크)

   Fig 5. 데크의 기본 구조
   출처: geeksforgeeks.com

   데크는 양 쪽 끝 모두에서 삽입과 삭제가 이루어지는 자료구조입니다. 따라서 지난 번 스택 자료구조에서 살펴보았듯, Deque를 이용해 스택 역시 구현할 수 있습니다. 게다가 데크 자료구조는 O(1)에 시계방향 및 반시계방향으로 input을 회전시킬 수도 있습니다.
   

5. 우선순위 큐

   우선순위 큐는 각 input마다 우선순위가 적용되는 큐입니다. 정렬 순서에 따라, 오름차순 혹은 내림차순으로 적용될 수 있습니다. 자세한 내용은 힙 자료구조를 학습한 이후에 따로 정리할 예정입니다.

큐의 기본 연산

💡 아래의 내용과 관련해, 기본적으로 FIFO를 따르는 Queue의 기본 연산입니다.

enqueue(E)

새로운 요소를 큐의 rear(tail)에 추가합니다. capacity 제한이 있다면, 큐가 가득 차 있는지 이전에 검사해야 합니다.

dequeue()

큐의 front(head)에 있는 요소를 제거합니다. 큐가 비어 있는지 이전에 검사해야 합니다.

배열로 큐를 구현하는 경우에, 제거되지 않은 기존 요소들의 인덱스가 앞당겨져야 하므로 O(N)의 시간복잡도를 가집니다.

isEmpty()

큐가 현재 비어있는지 검사하고, boolean 값을 반환합니다.

peek()

큐의 front(head)에 저장된 요소를 반환합니다.

size()

현재 큐에 들어있는 요소 개수를 반환합니다.

큐 구현: 자바

배열을 이용한 큐

 /* 코드는 수정될 수 있으며,
    참고한 코드는 참고자료 항목에 작성해두었습니다.
    코드는 수정될 수 있습니다.

		최초 작성일(yy/mm/dd): 2024/01/10    
    최종 수정일(yy/mm/dd): 2024/01/10 */

class ArrayQueue<T> {

    private int rear;
    private int front; // In fact, 0 or -1 is always assigned in array- implementation
    public T[] elements;

    public ArrayQueue(int initialCapacity) {
        elements = (T[]) new Object[initialCapacity];
        rear = -1;
        front = 0;
    }

    public boolean isEmpty() {
        return (front > rear);
    }

    public boolean isFull() {
        return (rear == elements.length - 1);
    }

    public void enqueue(T theElement) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        } else {
            rear++;
            elements[rear] = theElement;
        }   
    }

    public void dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        } else {
            T temp;
            for (int index = 0; index < rear; index++) { // array impl: O(N)
                temp = elements[index + 1];
                elements[index] = temp;
            }
            elements[rear] = null;
            rear--;
        }
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        } else {
            return elements[front];
        }
    }

    public void printElements() { // custom method for printing the queue
        for (int i = front; i <= rear; i++) {
            System.out.println(elements[i]);
        }
    }
    
}

연결리스트를 이용한 큐

 /* 코드는 수정될 수 있으며,
    참고한 코드는 참고자료 항목에 작성해두었습니다.
    코드는 수정될 수 있습니다.

		최초 작성일(yy/mm/dd): 2024/01/10    
    최종 수정일(yy/mm/dd): 2024/01/10 */

class LinkedQueue<T> {

    private int size;
    private Node<T> front;
    private Node<T> rear;
    private static int DEFAULT_CAPACITY = 100;
    private int capacity;
    
    private static class Node<T> {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    public LinkedQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
        this.capacity = DEFAULT_CAPACITY;
    }

    public LinkedQueue(int initialCapacity) {
        this.front = null;
        this.rear = null;
        this.size = 0;
        this.capacity = initialCapacity;
    }

    public boolean isEmpty() {
        return (size == 0);
    }

    public boolean isFull() {
        return (size == capacity);
    }

    public void enqueue(T theElement) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        } else if (isEmpty()) {
            front = rear = new Node(theElement);
        } else {
            rear.next = new Node(theElement);
            rear = rear.next;
        }
        size++;
    }

    public void dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        } else {
            front = front.next;
            size--;
        }
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        } else {
            return front.data;
        }
    }

    public void printElements() { // custom method for printing the queue
        Node tmp = front;
        while (tmp != null) {
            System.out.println(tmp.data);
            tmp = tmp.next;
        }
    }
    
}

참고 자료

• https://www.geeksforgeeks.org/queue-data-structure/
• https://www.geeksforgeeks.org/different-types-of-queues-and-its-applications/
• https://www.geeksforgeeks.org/how-to-implement-queue-in-java-using-array-and-generics/
• https://www.geeksforgeeks.org/different-types-of-queues-and-its-applications/