Queue

큐(Queue)의 개념

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 FIFO(First in First Out) 형식의 자료구조

큐의 연산

• add(item): item을 리스트의 끝부분(rear)에 추가
• remove(): 리스트의 첫 번째 항목(front) 제거
• peek(): 큐에서 가장 위에 있는 항목(rear) 반환
• isEmpty(): 큐가 비어 있을 때에 true 반환

큐의 구현

class Queue {
    private Integer array[];
    private int front;
    private int rear;
    private int size;

    public Queue(int size) {
        this.size = size;
        this.array = new Integer[size];
        this.front = -1;
        this.rear = -1;
    }

    void add(int data) {
        rear++;
        if (rear >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        array[rear] = data;
        if (front == -1) {
            front = rear;
        }
    }

    int remove() {
        if (front >= size || front < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return array[front++];
    }

    int peek() {
        if (isEmpty()) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            return array[front];
        }
    }

    boolean isEmpty() {
        return front == rear;
    }
}

큐의 성질

1. 원소의 추가 : O(1)
2. 원소의 제거 : O(1)
3. 제일 앞/뒤의 원소 확인 : O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인 및 변경 불가능

큐의 활용 사례

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

1. 너비 우선 탐색(BFS, Breadth-First Search) 구현
   • 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다.
   • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다.
   • 노드를 접근한 순서대로 처리할 수 있다.
2. 우선순위가 같은 작업 예약 (인쇄 대기열)
3. 프린터의 출력 처리
4. 프로세스 관리

Reference

• https://blog.encrypted.gg/934
• https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html