[JAVA] Queue 알고쓰자!

*** 자바에서는 기본적으로 Queue클래스를 지원해주지만, 기본적인 Queue의 구조를 알고 쓰고자 작성하였습니다.

1. Queue(큐)

Queue는 자료구조의 스택과 반대의 구조라고 생각하면 되며, 큐는 FIFO(First In First Out)의 형태를 가지게 됩니다. 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다.

Enqueue : 큐 맨 뒤에 데이터를 추가
Dequeue : 큐 맨 앞쪽의 데이터를 삭제

특징

• 큐의 한쪽 끝은 Front로 정하여 삭제연산만 수행한다.
• 다른 한쪽 끝은 Rear로 정하여 삽입연삼나 수행한다.
• 그래프 넓이 우선 탐색(BFS)에서 사용된다.
• 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다. 먼저 들어온 입력먼저 처리

1.1 큐 구현

• pop
  큐의의 가장 먼저들어온 데이터를 추출한 후에 큐에서 삭제합니다.
• push
  큐의 가장 최상위(마지막)에 데이터를 삽입합니다.
• isEmpty
  스택이 empty 상태인지 확인합니다.
• clear
  스택에 저장된 모든 데이터를 삭제하고 스택을 초기화합니다.
• front
  큐의의 가장 앞에 위치한 데이터를 추출합니다.
  pop 메서드와는 달리 큐에서 데이터를 삭제하지 않습니다.
• back
  큐의의 가장 뒤에 위치한 데이터를 추출합니다.
  pop 메서드와는 달리 큐에서 데이터를 삭제하지 않습니다.
• size
  queue에 현재 들어가 있는 데이터의 개수를 return 합니다.

• BOJ 10845 큐 문제 풀이
  https://www.acmicpc.net/problem/10845

import java.io.*;

class Queue{
    private int[] arr;
    private int front;
    private int capacity;

    Queue(int size){
        arr = new int[size];
        front = -1;
        capacity = size;
    }

    public void push(int X){
        arr[++front] = X;
    }

    public int pop(){
        if(isEmpty() == 1)
            return -1;
        else {
            int x = arr[0];
            for(int i=0;i<arr.length-1;i++){
                arr[i] = arr[i+1];
            }
            front--;
            return x;
        }
    }
    public int size() {
        return front + 1;
    }

    public int isEmpty(){
        if(front == -1)
            return 1;
        else
            return 0;
    }
    public int front(){
        if(isEmpty() != 1)
            return arr[0];
        else
            return -1;
    }
    public int back(){
        if(isEmpty() != 1)
            return arr[front];
        else
            return -1;
    }
    public boolean isFull(){
        return front == capacity - 1;
    }
    public void clear() {
        arr = null;
        front = -1;
    }

}


class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int n = Integer.parseInt(br.readLine());

        Queue queue = new Queue(n);

        for(int i=0;i<n;i++){
            String str = br.readLine();

            if(str.contains(" ")){
                int X = Integer.parseInt(str.split(" ")[1]);
                queue.push(X);
            }
            else {
                switch(str) {
                    case "front" :
                        bw.write(queue.front() + "\n");
                        break;
                    case "back" :
                        bw.write(queue.back()+ "\n");
                        break;
                    case "size" :
                        bw.write(queue.size() + "\n");
                        break;
                    case "empty" :
                        bw.write(queue.isEmpty() + "\n");
                        break;
                    case "pop" :
                        bw.write(queue.pop()+ "\n");
                        break;
                }
            }
        }
        bw.flush();
        bw.close();
    }
}

출처 : https://go-coding.tistory.com/6