큐 (Queue)

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

연산

add

데이터 추가, 꽉 찼을 시 예외를 발생 시킴, 반환타입은 boolean

offer

데이터 추가, 꽉 찼을 시 null을 반환, 반환타입은 boolean

Rear				Data(1)	Front

Rear			Data(2)	Data(1)	Front

Rear		Data(3)	Data(2)	Data(1)	Front

poll

데이터 꺼내기, 꽉 찼을 시 null을 반환

Rear		Data(3)	Data(2)	Data(1)	Front

Rear			Data(3)	Data(2)	Front

Rear				Data(3)	Front

peek

요소를 읽어옴, 없으면 null 반환

remove

데이터 꺼내기, 꽉 찼을 시 예외를 발생 시킴

element

요소를 읽어옴, 없으면 예외를 발생시킴

메소드

• isEmpty: boolean 값으로 큐가 비었는지 확인
• isFull: boolean 값으로 큐가 꽉 찼는지 확인
• clear: 큐를 비움

유의사항

• 데이터를 꺼낼때 마다 빈 공간을 채우기 위해 데이터 복사가 일어나므로 LinkedList로 구현하면 좋음

Queue<> queue = new LinkedList<>();

• 큐의 크기가 고정되어있으면 데이터가 가득 찼을때 추가삽입이 불가능
• 삽입, 삭제가 각각 한쪽에서만 일어나끼 때문에 중간의 특정항목에 접근하려면 그 앞의 항목들 부터 삭제해야함
• 특정 항목을 찾기 위해서는 큐를 선형적으로 탐색 해야함

배열로 원형 Queue 구현

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

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

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

    public boolean isFull() {
        return (this.rear + 1) % this.arr.length == this.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];

    }

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

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

}

public class Practice2 {
    public static void main(String[] args) {
        // Test code
        MyQueue2 myQueue = new MyQueue2(5);
        myQueue.enqueue(1);
        myQueue.enqueue(2);
        myQueue.enqueue(3);
        myQueue.enqueue(4);
        myQueue.enqueue(5);
        myQueue.enqueue(6); // Queue is full!

        myQueue.printQueue();   // 1, 2, 3, 4, 5

        System.out.println(myQueue.dequeue());  // 1
        myQueue.printQueue();   // 2, 3, 4, 5

        System.out.println(myQueue.dequeue());  // 2
        myQueue.printQueue();   // 3, 4, 5

        myQueue.enqueue(6);
        myQueue.enqueue(7);
        myQueue.printQueue();   // 3, 4, 5, 6, 7

        System.out.println(myQueue.dequeue());  // 3
        System.out.println(myQueue.dequeue());  // 4
        System.out.println(myQueue.dequeue());  // 5
        myQueue.printQueue();   // 6, 7
        System.out.println(myQueue.dequeue());  // 6
        System.out.println(myQueue.dequeue());  // 7
        myQueue.dequeue();      // Queue is empty!
    }
}