큐 (Queue)

🐶 큐에 대해서 알아봐요

- 선입선출 자료구조

- First In First Out (FIFO)

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

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

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

제로베이스 백엔드 스쿨 인강 참조

🐶 큐 기본 연산

- 데이터 추가 (Enqueue) : 큐에 데이터 추가

- 데이터 꺼내기 (Dequeue) : 큐에서 데이터 꺼내기

🐶 java로 queue 흉내내기

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

public class Main {
    public static void main(String[] args) {
        Queue queue = new LinkedList();

        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);

        System.out.println(queue);

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

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

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

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

        queue.clear();
        System.out.println(queue);
        System.out.println(queue.poll());
    }
}

🐶 ArrayList를 활용해서 queue 구현하기

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

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

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

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

        myQueue.printQueue();

        System.out.println(myQueue.peek());
        myQueue.printQueue();

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

🐶 java 배열을 활용한 queue 구현

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

    MyQueue2(int size) {
        this.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.println(this.arr[i] + " ");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        MyQueue2 myQueue = new MyQueue2(5);
        myQueue.enqueue(1);
        myQueue.enqueue(2);
        myQueue.enqueue(3);
        myQueue.enqueue(4);

        myQueue.printQueue();

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