특징

큐는 먼저 들어온 것이 먼저 나가는 FIFO(First In First Out) 방식의 자료구조이다.

큐의 한 쪽 끝(Rear)에서는 데이터 삽입만 가능하며, 다른 한 쪽 끝(Front)에서는 데이터 삭제만 가능하다.
큐에서 데이터가 추가되는 것을 Enqueue, 데이터가 삭제되는 것을 Dequeue라고 한다.

큐에는 종류가 총 3가지가 존재한다.
1. 선형 큐(Linear Queue)
2. 원형 큐(Circular Queue)
3. 우선순위 큐(Priority Queue)

원형 큐와 우선순위 큐는 다음 글에서 정리할 예정이다.

연산

큐의 연산은 삽입(add), 삭제(remove), 첫 번째 데이터(가장 오래전에 삽입된 데이터) 확인(peek), 큐가 비었는지 확인(isEmpty) 이렇게 4가지의 연산이 있다.

1. add()

add() 연산은 큐에 데이터를 추가하는 연산이다.

큐에 데이터를 추가하면 Rear의 값이 1이 증가된다.
만일 큐가 꽉 차게 된다면 더 이상 삽입할 수 없다.

2. remove()

remove() 연산은 큐에서 데이터를 제거하는 연산이다.

큐에서 front가 가리키는 데이터를 삭제한 뒤, front의 값을 1 증가시킨다.
만일 rear와 front의 위치가 동일하다면, 이는 큐에 남은 데이터가 없음을 의미하고 더이상 삭제할 수 없다.

3. peek()

peek() 연산은 큐에서 가장 앞에 있는 데이터(가장 오래전에 삽입 된 데이터)를 확인하는 연산이다.
peek() 연산과 remove() 연산의 차이점은 remove() 연산은 데이터를 삭제한 후 읽는다면, peek() 연산은 데이터를 삭제하지 않고 확인할 수 있다.

4. isEmpty()

isEmpty() 연산은 큐가 비어있는지 확인해주는 연산이다.
반환 타입은 boolean으로 큐가 비어있다면 true, 비어있지 않다면 false를 반환한다.

시간복잡도

연산	복잡도
Insertion	O(1)
Deletion	O(1)
Selection	O(n)

삽입 연산의 경우, 데이터를 넣으면 데이터의 개수에 상관없이 삽입할 수 있으므로 O(1)이다.
삭제 연산은 삽입 연산과 마찬가지로 데이터를 삭제할 때 데이터의 개수에 상관없이 삭제할 수 있으므로 O(1)이다.
검색 연산의 경우, 현재 큐에 들어있는 데이터를 모두 찾는 것이므로 데이터의 개수에 따라 복잡도가 달라지므로 O(n)이다.

장단점

장점

• 데이터의 삽입 삭제가 빠르다.
• 순차적으로 되어 있어서 입력 순서에 따라 처리할 때 유용하다.

단점

• 중간에 위치한 데이터에 접근하기 어렵다.
• 배열로 구현하면 삽입, 삭제에 한계가 존재한다.
  - 이 문제를 해결하고자 나온 것이 바로 원형 큐이다.

사용사례

• 프린터와 같은 우선순위 작업 예약
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache) 구현

예제코드

Java

Queue

자바에서는 기본적으로 Queue 객체를 지원해준다.

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

public class QueueEx {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.add(2);
        queue.add(4);
        queue.add(3);

        while(!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

배열

Queue 객체를 사용하지 않고 배열로 구현한다면 다음과 같이 구현할 수 있다.

public class Queue {

    private int[] array = new int[100];
    int lastIdx = 0;

    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }

    public int peek() {
        return array[0];
    }

    public int poll() {
        int rs = array[0];

        for(int i=1; i<=lastIdx; i++) {
            array[i-1] = array[i];
        }
        lastIdx--;

        return rs;
    }

    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}

Kotlin

코틀린에서는 따로 Queue 객체를 구현해놓지 않았다.
그래서 ArrayList를 사용하여 Queue를 구현할 수 있다.

fun main() {
    var queue = arrayListOf<Int>()

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

    queue.removeAt(0)

    print(queue[0])
}