[백준10845] 큐(queue)란? 자바로 큐 구현하기

큐란?

한쪽 끝에서만 자료를 넣고 반대쪽 끝에서만 뺄 수 있는 자료구조

먼저 넣은 것이 먼저 나오기 때문에 FIFO(First In First Out) 이라고도 한다.

• push: 큐에 자료를 넣는 연산
• pop: 큐에서 자료를 빼는 연산
• front: 큐의 가장 앞에 있는 자료를 보는 연산
• back: 큐의 가장 뒤에 있는 자료를 보는 연산
• empty: 큐가 비어있는지 아닌지를 알아보는 연산
• size: 큐에 저장되어있는 자료의 개수를 알아보는 연산

 

bfs 알고리즘에서 많이 쓰이기 때문에 필수적으로 알아두어야 하는 자료구조이다.

java의 경우 java.util.Queue를 사용하면 된다.

 

 

Java로 큐 구현하기(백준 10845)

    int[] arr = new int[10000];
    int begin = 0;
    int end = 0;

자료를 넣을 배열과,

자료가 들어있는 시작위치와 끝 위치를 담을 변수를 선언해준다.

 

end는 마지막으로 담긴 위치가 아닌 다음으로 담길 위치를 나타내며,

begin ~ (end - 1)까지 자료가 담겨있다.

 

백준 문제 풀이를 위한 코드

참고로 백준 문제에 "출력한다" 라고 되어있었기 때문에 각 함수에 print를 찍어줬지만,

결과값을 return 시킨 뒤 Stringbuilder를 통해 한번에 출력시키면 더 빠른 결과를 얻을 수 있다.

package dataStructure;

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

public class Baekjoon10845 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        Queue queue = new Queue();
        int n = Integer.parseInt(br.readLine());

        while(n-- > 0){
            st = new StringTokenizer(br.readLine(), " ");
            switch (st.nextToken()){
                case "push":
                    queue.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    queue.pop();
                    break;
                case "size":
                    queue.size();
                    break;
                case "empty":
                    queue.empty();
                    break;
                case "front":
                    queue.front();
                    break;
                case "back":
                    queue.back();
                    break;
            }
        }

    }
}

class Queue{
    int[] arr = new int[10000];
    int begin = 0;
    int end = 0;

    void push(int x){
        arr[end] = x;
        end++;
    }

    void pop(){
        if (end == begin){
            System.out.println(-1);
        }else{
            System.out.println(arr[begin++]);
        }
    }

    void size(){
        System.out.println(end - begin);
    }

    void empty(){
        System.out.println((begin == end) ? 1 : 0);
    }

    void front(){
        System.out.println((begin == end) ? -1 : arr[begin]);
    }

    void back(){
        System.out.println((begin == end) ? -1 : arr[end - 1]);
    }
}