[자료구조/알고리즘] 큐(Queue)

큐(Queue)

• 정의
  - 선입선출(First In First Out -> FIFO) 자료구조
  • 먼저 들어온 데이터가 먼저 나가는 구조
• 사용처
  - 입력순서대로 데이터 처리가 필요할 때 사용
  ex) 각종 대기열, BFS(Breath-First Search: 너비 우선 탐색) 등
• 구조
  
  Rear: 데이터 추가가 이루어지는 곳
  Enqueue: 데이터 추가
  Front: 데이터 삭제가 이루지는 곳
  Dequeue: 데이터 삭제

원형 큐(Circular Queue)

• 정의
  - 선형 큐 구조에서 Dequeue 연산 시 배열의 공백을 사용할 수 없는 문제를 해결하기 위한 자료구조
• 특징
  - 데이터 추가 시 Rear를 1씩 증가시키며 해당 위치에 데이터를 추가
  - 데이터 삭제 시 Front를 1씩 증가시키며 해당 위치의 데이터를 삭제
  - Front가 가르키는 위치는 항상 초기생성값과 동일

시간복잡도

• 삽입, 삭제: O(1)(삽입은 항상 Rear, 삭제는 항상 Front에서만 실행되기 때문)
• 탐색: O(n)

구현

• 원형 큐 형태로 구현
• 아이탬이 있는 부분만 출력하는 함수와 배열 전체를 출력하는 함수 별도로 구현
• dequeue시 해당 위치는 초기 값으로 재선언

import java.util.Arrays;

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

    MyQueue(int size) {
        arr = new int[size + 1]; // 첫 위치의 공백을 유지하기 위함
    }

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

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

    public void enqueue(int x) {
        if (isFull()) {
            System.out.println("Error: Queue is full");
        } else {
            this.rear = (this.rear + 1) % this.arr.length;
            this.arr[this.rear] = x;
        }
    }

    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Error: Queue is empty");
            return -1;
        } else {
            int res = this.arr[front];
            this.front = (this.front + 1) % this.arr.length;
            int x = this.arr[this.front];
            this.arr[this.front] = res;
            return x;
        }
    }

    public void print() {
        int start = (this.front + 1) % this.arr.length;
        int end = (this.rear + 1) % this.arr.length;
        String out = "";
        for (int i = start; i != end; i = (i + 1) % this.arr.length) {
            out += this.arr[i] + ", ";
        }
        out = "Only Items: " + "[" + out.substring(0, out.length() - 2)+ "]";
        System.out.println(out);
    }

    public void printOrg() {
        System.out.println("Actual Array: " + Arrays.toString(this.arr));
    }
}
public class Main {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue(4);
        myQueue.enqueue(1);
        myQueue.print();
        myQueue.enqueue(2);
        myQueue.print();
        myQueue.enqueue(3);
        myQueue.print();
        myQueue.enqueue(4);
        myQueue.print();
        myQueue.enqueue(5);
        myQueue.printOrg();

        myQueue.dequeue(); // 1
        myQueue.print();
        myQueue.dequeue(); // 2
        myQueue.print();
        myQueue.dequeue(); // 3
        myQueue.enqueue(5);
        myQueue.printOrg();
        myQueue.print();
        myQueue.dequeue(); // 4
        myQueue.print();
        myQueue.dequeue(); // 5
        myQueue.dequeue();
        myQueue.printOrg();
    }
}

이미지 출처

https://yoongrammer.tistory.com/46