[기초 자료구조] Queue

1. Queue 란?

• FIFO 방식으로 데이터를 저장하는 자료구조 입니다.

 

FIFO

• First-In, First-Out
• 먼저 추가된 요소가 먼저 제거되는 방식을 의미합니다.

 

2. 주요 연산

enqueue	항목을 추가합니다.	O(1)
dequeue	항목을 반환하고 제거합니다.	O(1)
peek	항목을 반환합니다.	O(1)

 

3. 종류

Linear Queue	막대 모양 형태의 큐입니다. 단점 - dequeue 시, 앞 공간이 비어있게 됩니다. (이 공간의 재사용이 불가합니다)
Circular Queue	환형 형태의 큐 입니다.   - 순환적으로 요소를 관리합니다. (시작과 끝이 연결되어 있음) 장점 (Linear Queue 단점 보완)  - 앞에 빈 공간이 있을 경우, 해당 공간 재사용 가능  - enqueue 시, 첫번째 요소로 포인터를 옮김
Priority Queue	요소가 우선순위를 가지는 큐 - 우선순위별로 출력됩니다. - Heap 자료구조를 사용하여 구현합니다.
Deque (Double-ended Queue)	양쪽 끝에서 삽입 삭제가 가능한 큐입니다. - 스택과 큐의 특성을 모두 가집니다.

 

4. 사용 사례

CPU Scheduling	프로세스들이 동시에 실행되며, 요청한 순서대로 처리하기 위해 사용합니다.
Printer	프린터에게 여러 요청을 보낼 경우, 순서대로 처리하기 위해 사용합니다.
Load Balancing	요청을 순서대로 분배하기 위해 사용합니다.
Data Streaming	실시간 스트리밍 시스템에서 데이터 패킷을 순서대로 처리하기 위해 사용
Messaging Queue	이기종 시스템 간에 메시지를 비동기적으로 전달할 때 사용하는 통신방식. 요청 순서대로 처리되도록 보장해줌
주문처리 시스템	사용자의 주문이 순서대로 처리되기 위해 사용합니다.

 

 

5. 구현

• 배열과 포인터를 사용하여 구현합니다.

 

포인터

• front: 출력될 요소의 인덱스를 가리킵니다.
• rear: 입력할 요소의 인덱스를 가리킵니다.

 

Linear Queue

public class MyLinearQueue<T> {
    private T[] arr;
    private int front, rear;

    public MyLinearQueue(int size) {
        arr = (T[]) new Object[size];
        front = rear = 0;
    }

    public void enqueue(T item) {
        fullCheck();

        arr[rear++] = item;
    }

    public T dequeue() {
        emptyCheck();

        return arr[front++];
    }

    public T peek() {
        emptyCheck();

        return arr[front];
    }

    public int size() {
        return rear - front;
    }

    private void emptyCheck() {
        if (front == rear) throw new IllegalStateException("queue is empty");
    }

    private void fullCheck() {
        if (rear == arr.length) throw new IllegalStateException("queue is full");
    }
}

 

Circular Queue

public class MyCircularQueue<T> {
    private T[] arr;
    private int front, rear;

    public MyCircularQueue(int size) {
        arr = (T[]) new Object[size+1]; // 가득 찬 상태와 비어있는 상태를 구분하기 위함
        front = rear = 0;
    }

    public void enqueue(T item) {
        fullCheck();

        arr[rear++] = item;

        if (rear == arr.length) rear %= arr.length;
    }

    public T dequeue() {
        emptyCheck();

        T item = arr[front++];
        
        if (front == arr.length) front %= arr.length;

        return item;
    }

    public int size() {
        return (rear + arr.length - front) % arr.length;
    }

    private void emptyCheck() {
        if (front == rear) throw new IllegalStateException("queue is empty");
    }

    private void fullCheck() {
        if ((rear + 1) % arr.length == front) throw new IllegalStateException("queue is full");
    }
}

 

 

 

출처

• Wiki - Queue