큐

큐

• 선입선출 (First In First Out; FIFO) 자료구조
  • 먼저 들어온 데이터가 먼저 나가는 구조
• 입력 순서대로 데이터 처리가 필요할 때 사용
  • 프린터 출력 대기열, BFS (Breath-First Search) 등

배열을 이용한 큐

class Queue {
    int[] arr;
    int front = 0;
    int rear = 0;

    Queue(int size) {
        arr = new int[size + 1]; // front를 비워두는 방식으로 원형 큐를 구현하기 위해서 +1
    }

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

    public boolean isFull() {
        return (rear + 1) % arr.length == front;
    }

    public void enqueue(int data) {
        if (isFull()) {
            System.out.println("Queue is full!");
            return;
        }

        rear = (rear + 1) % arr.length;
        arr[rear] = data;
    }

    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty!");
            return null;
        }

        front = (front + 1) % arr.length;
        return arr[front];
    }

    public void printQueue() {
        int start = (front + 1) % arr.length;
        int end = (rear + 1) % arr.length;

        for (int i = start; i != end; i = (i + 1) % arr.length) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

리스트를 이용한 큐

class Queue {
    ArrayList list;

    Queue() {
        this.list = new ArrayList();
    }

    public boolean isEmpty() {
        if (list.size() == 0) {
            return true;
        }

        return false;
    }

    public void push(int data) {
        list.add(data);
    }

    public Integer pop() {
        if (isEmpty()) {
            System.out.println("Queue is empty!");
            return null;
        }

        int data = (int) list.get(0);
        list.remove(0);
        return data;
    }

    public Integer peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty!");
            return null;
        }

        return (int) list.get(0);
    }

    public void printQueue() {
        System.out.println(list);
    }
}