► Queue 란?

Queue 자료구조는 입구와 출구가 따로 있는 통로라고 볼 수 있습니다.

먼저 들어간 사람이 먼저 나가는, 한마디로 음식점에서 대기하는 줄이라고 생각하면 됩니다.

👉

큐는 FIFO다 (First In First Out 선입선출) 먼저 들어간 물건이 가장 먼저 나온다.

✔︎ 큐의 동작원리

큐는 기본적으로 한쪽에서는 데이터 삽입이 이루어지고 한쪽에서는 데이터 추출이 이루어진다. (예외적으로 Deque 데크라는 자료구조는 앞뒤에서 삽입/추출이 이루어진다.)

⇒ 데이터 삽입 : enQueue

큐에서 데이터를 삽입할때는 enQueue라고 한다. 큐가 비어있다면 rear(꼬리)와 front(머리)값이 같다. (비어있을시 둘다 -1)

데이터를 삽입하면 rear에 +1 가 된다.

⇒ 데이터 추출 : deQueue

데이터 추출은 맨앞에 데이터인 front데이터를 추출한다. 추출한뒤에는 뒤에있는 데이터들이 한칸씩 앞으로 가서 빈곳을 채워줘야한다.

✔︎ LinkedList를 이용해서 Queue 구현

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

public class Main {

  public static void main(String[] args) {
    // LinkedList를 이용한 Queue 구현
    Queue<Integer> queue = new 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]

    // poll() : 큐의 첫 번째 요소를 반환하고 제거
    System.out.println(queue.poll()); // 1
    System.out.println(queue);

    // peek() : 큐의 첫 번째 요소를 반환
    System.out.println(queue.peek()); // 2

    // isEmpty() : 큐가 비어있는지 확인
    System.out.println(queue.isEmpty()); // false

    // size() : 큐의 크기 확인
    System.out.println(queue.size()); // 4

    // contains() : 큐에 특정 요소가 있는지 확인
    System.out.println(queue.contains(3)); // true

    // clear() : 큐의 모든 요소 제거
    queue.clear();
    System.out.println(queue.isEmpty()); // true
  }
}

✔︎ ArrayList를 이용해 Queue 구현

import java.util.ArrayList;

class MyQueue1 {

  ArrayList<Integer> list;

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

  public boolean isEmpty() {
    return this.list.isEmpty();

  }

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

✔︎ 배열을 이용해서 원형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;
    }
    this.front = (this.front + 1) % this.arr.length;
    return this.arr[this.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!
  }
}