[자료구조] 큐(Queue)

큐(Queue)란?

큐(Queue)는 선형 자료구조 중 하나로, 데이터를 일렬로 저장하며 먼저 저장된 데이터가 먼저 나가는 (FIFO, First In First Out) 자료구조다.

큐의 구조 [wikipedia]

큐는 Back에서 들어온 데이터가 순서대로 Front로 나가는 구조를 가지며, 일렬로 서서 순서를 기다리는 사람을 연상시킨다. 나중에 들어온 데이터가 먼저 나가는 스택(Stack)의 후입선출(Last-In-First-Out, LIFO)과는 반대되는 개념이다.

 

큐의 활용

• 자원 공유 및 동기화
• 네트워크 통신
• 대기열 관리
• 버퍼링
• 작업 스케줄링

이외에도 대기열을 관리하거나 순서대로 데이터를 입력 받고 처리해야 할때 유용하게 사용되는 자료구조다.

 

큐의 주요 명령어

자바에서는 큐를 구현하는 방법이 LinkedList 클래스를 이용하는 방법과 ArrayDeque 클래스를 이용하는 방법, 크게 두가지가 있는데, 먼저 LinkedList 클래스를 이용하여 구현했을 때 명령어는 다음과 같다.

• add(element), offer(element): 큐의 뒤쪽에 요소를 추가
• remove(), poll(): 큐의 가장 앞쪽에 있는 요소를 제거하고 그 값을 반환
• element(), peek(): 큐의 가장 앞쪽에 있는 요소를 반환 (큐의 요소를 제거하지 않음)
• size(): 큐에 포함된 요소의 개수를 반환

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

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

        // 큐에 요소 추가
        queue.add("apple");
        queue.add("orange");
        queue.offer("banana");
        queue.offer("kiwi");

        // 큐에서 요소 제거 및 조회
        String head1 = queue.remove();
        String head2 = queue.poll();
        String peeked1 = queue.peek();
        String peeked2 = queue.element();
        int size = queue.size();

        System.out.println(head1); // "apple"
        System.out.println(head2); // "orange"
        System.out.println(peeked1); // "banana"
        System.out.println(peeked2); // "banana"
        System.out.println(size); // 2
    }
}

 

ArrayDeque는 배열(Array)을 이용하여 덱(Deque)을 구현한 것으로, 큐(Queue)와 스택(Stack)의 기능을 모두 제공한다.

크기가 가변적인 큐를 구현할 때 주로 사용되며 명령어는 다음과 같다.

• add(element), offer(element): 큐의 뒤쪽에 요소를 추가
• addfirst(element), offerfirst(element): 큐의 앞쪽에 요소를 추가
• remove(), poll(): 큐 앞쪽의 요소를 제거 및 반환
• removeLast(), pollLast(): 큐 뒤쪽의 요소를 제거 및 반환
• getFirst(), peekFirst(): 큐 앞쪽의 요소를 반환 (제거 x)
• getLast(), peekLast(): 큐 뒤쪽의 요소를 반환 (제거 x)
• size(): 큐에 있는 요소의 개수를 반환
• isEmpty: 큐가 비어있는지 여부를 반환

import java.util.ArrayDeque;

public class Main {

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

        // 큐에 요소 추가
        queue.add("apple");
        queue.offer("orange");
        queue.addFirst("banana");
        queue.offerFirst("kiwi");
        queue.add("grapes");
        queue.add("mango");

        // 큐에서 요소 제거
        String removed1 = queue.remove();
        String removed2 = queue.poll();
        String removed3 = queue.removeFirst();
        String removed4 = queue.pollFirst();
        System.out.println(removed1); // "kiwi"
        System.out.println(removed2); // "banana"
        System.out.println(removed3); // "apple"
        System.out.println(removed4); // "orange"

        // 큐의 요소 조회
        String front1 = queue.getFirst();
        String front2 = queue.peekFirst();
        String back1 = queue.getLast();
        String back2 = queue.peekLast();
        System.out.println(front1); // "grapes"
        System.out.println(front2); // "grapes"
        System.out.println(back1); // "mango"
        System.out.println(back2); // "mango"

        // 큐의 사이즈 조회
        int size = queue.size();
        System.out.println(size); // 2

        // 큐가 비어있는지 여부 확인
        boolean isEmpty = queue.isEmpty();
        System.out.println(isEmpty); // false
    }
}

큐의 시간 복잡도

 

일반적으로 add나 offer, remove, poll같은 큐에 요소를 추가하거나 제거하는 연산의 시간 복잡도는 O(1)이지만, 이외의 큐 내에 탐색이 필요한 연산은 시간 복잡도가 O(n)이다.