[Java] Queue (큐)

Queue?

위 그림의 왼쪽처럼 식당에 입장하기 위해 줄을 서는 것을 생각해보면 가장 먼저 줄을 선 사람이 가장 먼저 입장한다.

 

Queue도 이와 같은 방식으로 동작한다.

 

이처럼 먼저 들어간 것이 먼저 나오는 것을 선입선출(First In First Out, FIFO)라고 한다.

Queue의 주요 연산 Enqueue와 Dequeue

• Enqueue(): 값을 집어넣는 것을 의미
• Dequeue(): 값을 꺼내는 것을 의미

Java에서 Queue의 Enqueue와 Dequeue 메소드

• Enqueue: add, offer
• Dequeue: remove, poll

Queue의 시간복잡도

• Enqueue(): O(1)
• Dequeue(): O(1)
• 탐색: O(n)

Queue에서 값을 탐색하여 얻는 것은 부적절하다. 실제로 Java에서 Queue의 메소드 중 index나 특정 값을 탐색하는 메소드는 존재하지 않는다. 따라서 값을 탐색해야할 경우에는 리스트 또는 배열을 사용하는 것이 좋다.

구현

public class MyQueue<T> {
    private Object[] array;
    private int size; //요소의 개수
    private int front; //가장 앞 쪽에 있는 요소의 위치
    private int rear; //가장 뒤 쪽에 있는 요소의 위치
    private int capacity; //큐의 전체 용량

    public MyQueue(int capacity) {
        this.capacity = capacity;
        this.array = new Object[capacity];
        this.size = 0;
        this.front = 0;
        this.rear = -1;
    }
	
    public boolean isEmpty() {
        return size == 0;
    }

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

    public int size() {
        return size;
    }

    public void enqueue(T item) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue.");
            return;
        }
        rear = (rear + 1) % capacity; //capacity=5, rear=4일 때 다음 rear는 0
        array[rear] = item;
        size++;
    }

    public T dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue.");
            return null;
        }
        T item = (T) array[front];
        front = (front + 1) % capacity; //capacity=5, front=4일 때 다음 front 0
        size--;
        return item;
    }

    public T peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot peek.");
            return null;
        }
        return (T) array[front];
    }

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>(5);

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);

        System.out.println("Front of the queue: " + queue.peek());

        System.out.println("Dequeue: " + queue.dequeue());
        System.out.println("Dequeue: " + queue.dequeue());

        queue.enqueue(4);
        queue.enqueue(5);

        System.out.println("Front of the queue: " + queue.peek());

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

        System.out.println("Dequeue: " + queue.dequeue());
        System.out.println("Dequeue: " + queue.dequeue());
        System.out.println("Dequeue: " + queue.dequeue());

        System.out.println("Is queue empty? " + queue.isEmpty());
        
        //output:
        //    Front of the queue: 1
        //    Dequeue: 1
        //    Dequeue: 2
        //    Front of the queue: 3
        //    Queue size: 3
        //    Dequeue: 3
        //    Dequeue: 4
        //    Dequeue: 5
        //    Is queue empty? true
    }
}

 

• [Java] Queue와 PriorityQueue 정리