[자료구조] 큐

큐 (Queue) 란?

• 입력 순서대로 데이터 처리가 필요할 때 사용하는 선입선출 구조 (FIFO)

• BFS (그래프 넓이 우선 탐색), 프린터 출력 대기열과 같은 상황에서 사용

큐의 연산

• enqueue() : 큐 맨 뒤에 데이터 추가

• dequeue() : 큐 맨 앞쪽의 데이터 삭제

위 연산 뿐만 아니라, poll(), peek(), contains(), size(), isEmpty()도 사용가능하다.

큐의 특징

• 한 쪽 끝은 front로 정하여 삭제 연산만 수행한다.

• 다른 한 쪽 끝은 rear로 설정하여 삽입 연산만 수행한다.

• ArrayList와 배열로 구현 가능하다.

---

큐의 구현1 - LinkedList

아래 구현한 것과 같이, LinkedList로 생성하여 Queue의 다양한 메서드를 사용해보고 결과를 확인할 수 있다.

import java.util.LinkedList;
import java.util.Queue;
 
public class Queue01 {
    public static void main(String[] args) {
        Queue queue = new LinkedList();
 
        queue.add(1);
        queue.add(2);
 
        System.out.println(queue.contains(2));
        System.out.println(queue.poll());
        System.out.println(queue.peek());
        System.out.println(queue);
 
        System.out.println(queue.size());
        System.out.println(queue.isEmpty());
 
        queue.clear();
    }
}

큐의 구현2 - ArrayList

MyQueue 클래스를 ArrayList를 통해 구현해보겠다.

import java.util.ArrayList;

class MyQueue {
    ArrayList list;

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

ArrayList를 통한 isEmpty의 경우, list의 사이즈가 0일 경우 true를 반환하고 아닐 경우 false를 반환한다.

 public boolean isEmpty() {
        if (this.list.size() == 0) {
            return true;
        } else {
            return false;
        }
    }
    
 public void push(int data) {
        this.list.add(data);
    }

pop()과 peek()를 구현할 때는 큐가 빈 경우를 꼭 확인해주어야한다. 먼저 구현한 isEmpty를 통해 확인한다.

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

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

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

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

큐의 구현3 - 배열 (원형 큐)

• 원형 큐 관리를 위해 front 값을 처음에 비워두기 때문에 하나 더 크게 만들어야한다.

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

    MyQueue2(int size) { 
        arr = new int[size + 1];
    }
}

• 배열이 비어 있을 때, rear와 front가 같은 곳을 가리킨다.

• 또한, rear가 끝인데 길이로 나누었을 때 front 위치일 경우 full. 즉, 큐가 꽉찬 상태이다.

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

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

• enqueue 구현 시, 원형 큐 관리를 위해 front는 비워두고, rear을 왼쪽으로 하나씩 옮기면서 값을 넣는다.

• dequeue 구현 시, front 값에 1을 더해 길이로 나눈 값을 front로 하여 해당 위치에 존재하는 값을 반환한다.

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

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

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

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