큐(Queue)

큐(Queue)

- 선입선출(First In First Out; FIFO) 자료구조

: 먼저 들어온 데이터가 먼저 나가는 구조

- 입력 순서대로 데이터 처리가 필요할 때 사용

: 프린터 출력 대기열, BFS(Breath-First Search) 등

 

큐 기본 구조

- 선입선출 구조를 따름

- 기본적으로 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어짐

데이터 추가(Enqueue)

- 큐에 데이터 추가

데이터 꺼내기(Dequeue)

- 큐에서 데이터 꺼내기

---

실습 코드

// 선형 자료구조 - 큐


import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue queue = new LinkedList(); // LinkedList에 큐에 필요한 연산들이 다 구현이 되어있음

        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        System.out.println(queue); // [1, 2, 3, 4, 5]

        System.out.println(queue.poll()); // 1
        System.out.println(queue); // [2, 3, 4, 5]

        System.out.println(queue.poll()); // 2
        System.out.println(queue); // [3, 4, 5]

        System.out.println(queue.peek());

        System.out.println(queue.contains(3));
        System.out.println(queue.size());
        System.out.println(queue.isEmpty());

        queue.clear();
        System.out.println(queue); // []

        // queue는 clear 후 poll()을 하게되면 null 출력
        // stack은 예외 발생
        System.out.println(queue.poll());
    }
}

---

연습 코드1_ArrayList

// Practice1
// ArrayList 를 이용한 큐 구현

import java.util.ArrayList;

class MyQueue1 {
    ArrayList list;

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

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

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

    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);
    }

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

public class Practice1 {
    public static void main(String[] args) {
        // Test code
        MyQueue1 myQueue = new MyQueue1();
        myQueue.push(1);
        myQueue.push(2);
        myQueue.push(3);
        myQueue.push(4);
        myQueue.push(5);

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

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

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

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

        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
        System.out.println(myQueue.pop());
        myQueue.printQueue();
    }
}

---

연습 코드2_배열

// Practice2
// 배열을 이용한 기본 큐 직접 구현 (원형 큐)

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

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

    }

    public boolean isEmpty() {
        // 비어있다라는 의미 rear와 front가 같다는 것은
        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!
    }
}