[자료구조] 큐(Queue) 자료구조 알아보기 & Java 예제 코드

자료구조 중 큐(Queue)에 대해 정리해보자.

---

 

큐(Queue)란?

큐(Queue)는 일반적으로 선입선출(First-In-First-Out, FIFO) 원칙에 따라 동작하는 자료구조다.

큐는 데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나는 구조를 가지고 있다.

큐의 한쪽 끝을 ‘리어(rear)’라고 하고, 다른 한쪽 끝을 ‘프론트(front)’라고 한다.

데이터는 프론트에서 삭제되고, 리어에서 삽입된다.

 

큐의 기본 연산은 다음과 같다.

 

1. enqueue(item) : 큐의 리어(rear)에 항목(item)을 삽입한다.
2. dequeque() : 큐의 프런트(front)에서 항목을 삭제하고 반환한다.
3. isEmpty() : 큐가 비어 있는지 여부를 확인한다.
4. size() : 큐의 현재 크기를 반환한다.
5. peek() : 큐의 프론트(front)에 위치한 항목을 반환한다. 삭제하지 않고 참조만 한다.

출처 : https://ko.wikipedia.org/wiki/%ED%81%90_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

 

 

큐(Queue)의 장점 및 단점

장점

1. 선입선출(FIFO) 원칙 : 큐는 항목을 삽입한 순서대로 삭제되기 때문에 선입선출 원칙을 따른다. 이는 특정 작업을 처리하는 순서를 보장하는 데 유용하다.
2. 크기 조절 가능 : 큐는 일반적으로 동적으로 크기를 조절할 수 있어, 필요에 따라 크기를 늘리거나 줄일 수 있다.
3. 대기열 관리 : 큐는 대기열을 관리하는 데에 매우 유용하다. 예를 들어, 작업을 처리하기 위해 들어오는 요청을 큐에 저장하고 처리 우선순위에 따라 처리할 수 있습니다.

 

단점

1. 중간 항목 접근 어려움 : 큐는 데이터의 삽입과 삭제가 각각 한쪽 끝에서만 일어나기 때문에 중간에 위치한 특정 항목에 접근하기가 어렵다. 큐에서 특정 항목을 삭제하기 위해서는 그 앞에 위치한 모든 항목들을 먼저 삭제해야 한다.
2. 크기 제한 : 큐는 일반적으로 동적으로 크기를 조절할 수 있지만, 특정 구현에서는 크기가 제한되어 있을 수 있습니다. 큐가 가득 찬 상태에서 더 많은 항목을 삽입하려고 하면 오버플로우(Overflow)가 발생할 수 있다.
3. 선형 탐색 시간 : 특정 항목을 찾기 위해서는 큐를 선형적으로 탐색해야 한다. 따라서, 큐에서 특정 항목을 찾는데 걸리는 시간은 큐의 크기에 비례한다.
4.  

큐는 데이터의 순서를 보장하고, 대기열 관리와 작업 분배 등 다양한 상황에서 유용하게 활용될 수 있다.

 

 

 

Queue 예시 코드(Java)

Java에서 Queue는 LinkedList를 활용해 생성해야 한다. (배열(Array)을 이용해 Queue를 구현할 수 있긴 하다.)

따라서 아래와 같이 Queue와 LinkedList가 모두 import되어 있어야 한다.

Queue<Element> queue = new LinkedList<>()와 같이 선언해주면 된다.

 

간단히 살펴보면 다음과 같다.

 

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

public class QueueExample {
    public static void main(String[] args) {
        // 큐 생성
        Queue<Integer> queue = new LinkedList<>();

        // enqueue: 큐에 항목 삽입
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        // dequeue: 큐에서 항목 삭제 및 반환
        int item = queue.poll();
        System.out.println("Dequeued item: " + item);

        // peek: 큐의 프론트(front) 항목 참조
        int frontItem = queue.peek();
        System.out.println("Front item: " + frontItem);

        // isEmpty: 큐가 비어 있는지 확인
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is queue empty? " + isEmpty);

        // size: 큐의 크기 확인
        int size = queue.size();
        System.out.println("Queue size: " + size);
    }
}

 

 

다음은 좀 더 Queue의 기본 연산을 좀 더 자세하게 살펴본 코드다.

 

import java.util.LinkedList;

public class Queue<T> {
    private LinkedList<T> queue;  // LinkedList를 사용해 큐를 구현

    public Queue() {
        queue = new LinkedList<>();
    }

    public void enqueue(T item) {
        queue.addLast(item);  // 큐의 리어(rear)에 항목 추가
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty.");
        }
        return queue.removeFirst();  // 큐의 프론트(front)에서 항목을 제거하고 반환
    }

    public boolean isEmpty() {
        return queue.isEmpty();  // 큐가 비어 있는지 여부 반환
    }

    public int size() {
        return queue.size();  // 큐의 현재 크기 반환
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty.");
        }
        return queue.getFirst();  // 큐의 프론트(front)에 위치한 항목 반환
    }
}

 

앞서 본 것처럼 이렇게 구현된 Queue 클래스를 사용하면 다음과 같이 큐를 생성하고 연산을 수행할 수 있다.

 

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new Queue<>();  // 큐 생성

        queue.enqueue(10);  // 항목 삽입
        queue.enqueue(20);
        queue.enqueue(30);

        System.out.println("Dequeued item: " + queue.dequeue());  // Dequeued item: 10

        System.out.println("Front item: " + queue.peek());  // Front item: 20

        System.out.println("Is queue empty? " + queue.isEmpty());  // Is queue empty? false

        System.out.println("Queue size: " + queue.size());  // Queue size: 2
    }
}