[알고리즘] Queue(큐 알고리즘)_JAVA[자바] 백준-18258번 풀이

 

 

큐의 동작방식을 알아보고 문제를 풀어보자!

 

 

들어가며

큐의 개념과 기본적인 사용법을 알아보고, 백준의 문제를 통해 한번 풀어보도록 하겠습니다.

---

 

큐(Queue)란?

큐는 FIFO(First-in First-Out)의 원칙을 따르는 자료구조입니다. LIFO를 사용하는 스택과는 달리 큐는 먼저 들어간 데이터부터 먼저 꺼내는 특징을 가지고 있습니다.

큐에서 데이터를 넣을 때는 en-queue라고하며 데이터를 꺼낼 때에는 dequeue라고 부릅니다.

 

이제 {1,3,21}을 큐를 이용해 입출력을 한번 해보겠습니다.

위와 같이 먼저 들어온 데이터부터 출력되는 것을 볼 수 있습니다. 하지만 이와 같이 큐를 사용하게 된다면 1을 디큐 했을 때 

배열[1], 배열[2]의 값을 한 칸식 앞으로 이동해야 하는 문제점이 생깁니다. 

 

이러한 문제를 해결하기 위해 논리적으로 큐의 앞단(Front)과 뒷단(Rear)을 추가하여 개선된 큐를 구현할 수 있습니다. 개선된 큐에서는 Front는 큐의 맨 앞에 위치하고, Rear는 큐의 맨 뒤에 위치합니다. 요소를 큐에 추가할 때는 Rear에서 원소를 추가하고, 큐에서 제거할 때는 Front에서 원소를 제거하는 방법으로 사용한다면 훨씬 효율적으로 구성할 수 있습니다.

 

다음은 논리적인 Front와 Rear을 추가한 큐입니다.

---

 

문제풀이

자바에서 제공하는 큐 메서드가 있지만 스스로 큐알고리즘을 짤 수 있어야 해당 메서드를 사용해야 한다고 생각해 문제풀이에는 직접 큐 알고리즘을 만들어 사용할 예정입니다.

 

다음과 같이 백준 18258 문제는 기본저인 스택을 사용하는 알고리즘입니다. 

front와 back은 변수로 선언해서 front는 변수 front를  반환해주고 rear은 변수 rear에 -1을 반환해 주면 되는 아주 간단한 문제입니다.

이제 코드를 작성해 보겠습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 문제번호 18258번
 */
public class 큐2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        Queue queue = new Queue(n);

        for (int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String token = st.nextToken();
            switch (token){
                case "push":
                    int x = Integer.parseInt(st.nextToken());
                    queue.push(x);
                    break;
                case "pop":
                    int pop = queue.pop();
                    sb.append(pop+"\n");
                    break;
                case "size":
                    int size = queue.size();
                    sb.append(size+"\n");
                    break;
                case "empty":
                    int empty = queue.empty();
                    sb.append(empty+"\n");
                    break;
                case "front":
                    int front = queue.front();
                    sb.append(front+"\n");
                    break;
                case "back":
                    int back = queue.back();
                    sb.append(back+"\n");
                    break;
            }
        }

        System.out.println(sb);
        br.close();
    }

    public static class Queue{
        private int[] que;          // 큐의 용량
        private int front;          // 맨 앞
        private int rear;           // 맨끝
        private int num;            // 배열의 요소수 갯수
        private int capacity;      // 배열 용량

        public Queue(int max){
            num = front = rear = 0;     //해당을 모두 0으로 변수 초기화
            capacity=max;       //배열의 용량을 넘어온 파라미터값으로 설정
            que = new int[capacity];        //용량의 값으로 큐의 배열용량 초기화
        }

        //파라미터 x의 값으로 인큐 실행 rear의 값을 증가해주면 되며 rear의 값이 용량보다 커지면 배열의 처음으로 초기화
        public void push(int x){
            que[rear++]= x;     
            num++;
            if (rear==capacity)
                rear=0;
        }

        //인큐 만약 num이 0이라면 -1반환하며 front과 용량과 같다면 0으로 초기화
        public int pop(){
            if (num<=0) {
                return -1;
            }
            int x= que[front++];
            num--;

            if (front==capacity)
                front=0;
            return x;
        }

        //num값만 반환해 개수 확인
        public int size(){
            return num;
        }

        public int empty(){
            if (num>0)return 0;
            else return 1;
        }

        //논리적 위치 front만 반환
        public int front(){
            if (num<=0){
                return -1;
            }else
            return que[front];
        }

        //논리적 위치인 rear의 -1을 반환
        public int back(){
            if (num<=0){
                return -1;
            }
            return que[rear-1];
        }
    }
}

위와 같이 직접 큐의 알고리즘으로 작성했습니다.

 

직접 작성한 큐 알고리즘을 사용해도 성공하는 것을 볼 수 있습니다.