백준 알고리즘 18258 큐 자료구조 구현하기

 

 

 

큐(Queue)는 선형 자료구조다. 데이터 대응관계가 1:1로 매칭이 된다. 선형 자료구조에는 순차(Sequential) 구조와 연결(Linked) 구조가 있다.순차 구조로 삽입과 삭제 시간이 상당히 많이 소요되는 구조다. 그럼에도 불구하고 논리가 명확한 자료구조이기 때문에 함수호출이나 대기행렬에 주로 사용되는 자료구조다.

 

큐(Queue)에서는 스택(Stack)과는 다르게 포인터가 2개의 포인터가 존재한다. 삽입포인터(Rear)는 1씩 증가하면서 큐 자료구조에 자료를 추가하는 역할을 담당한다. 삭제포인터(Front)는 저장된 데이터 중 가장 처음 입력된 데이터를 출력하고 1씩 증가한다. 큐 자료구조에 데이터가 없는 상황은 삭제포인터와 삽입포인터가 같아지는 경우다.

 

큐(Queue) 구조는 데이터의 입구와 출구가 다르다. 삽입과 삭제가 반대쪽에서 발생하게 된다. 스택(Stack)과 마찬가지로 포인터가 존재하여 현재 자료구조의 위치를 알 수 있다. 삽입 포인터는 저장된 데이터 중에서 가장 마지막에 삽입된 데이터 위치를 가리키게 된다. 자료가 입력되면 삽입 포인터는 1씩 증가하게 되며, 큐의 크기를 넘어가게 되면 Overflow Error를 발생시킨다. 마치 스택 자료구조에서 스택포인터가 스택의 크기를 넘어가게 되면 스택오버플로우(Stack Overflow Error) 

 

 

큐(Queue)는 대표적인 FIFO 형식의 자료구조다. 가장 먼저 삽입된 데이터가 가장 먼저 출력되는 자료구조로, 프린터 스풀이나 입출력 버퍼에 많이 활용된다.

 

 

백준 알고리즘 18258번은 선형 순차 자료구조 중에서도 큐(Queue)를 구현하는 문제다. 큐(Queue) 자료구조를 일반적으로 구현하면 간단하게 구현이 가능한데, 백준 알고리즘 18258번을 통해서 구현하게 되면 시간초과 문제 때문에, StringTokenizer, BufferedReader 객체를 반드시 사용해야 한다.

 

 

JAVA CODE

백준 알고리즘 18258번을 푸는 과정에서 StringBuilder로 문자열을 입력받아서 처리하면 시간초과로 실패한다. 문자열을 입력받을 때 BufferedReader를 사용해줘야 하고, 문자열을 파싱하는 과정에서는 StringTokenizer 객체를 사용해야 한다.

 

/*
    큐(Queue) 구현하기
*/

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

public class A_18258 {

    // 전역 변수
    public static StringBuilder sb = new StringBuilder();
    public static int[] arr;
    public static int queuePointerFront=0;
    public static int queuePointerRear=0;

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

        for(int i=0; i<X; i++){
            st = new StringTokenizer(br.readLine(), " ");
            switch(st.nextToken()){
                case "push":
                    push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    pop();
                    if(queuePointerFront==queuePointerRear) queuePointerRear=queuePointerFront;
                    else queuePointerRear++;
                    break;
                case "front":
                    front();
                    break;
                case "back":
                    back();
                    break;
                case "size":
                    size();
                    break;
                case "empty":
                    empty();
                    break;
            }
        }
        System.out.println(sb);
    }

    public static void push(int N){
        arr[queuePointerFront]=N;
        queuePointerFront++;
    }
    public static void pop(){
        if(queuePointerFront==queuePointerRear){
            sb.append(-1+"\n");
        }else{
            sb.append(arr[queuePointerRear]+"\n");
        }
        
        
    }
    public static void size(){
        if(queuePointerRear>=queuePointerFront) sb.append(0+"\n");
        else sb.append(queuePointerFront-queuePointerRear+"\n");
    }
    public static void empty(){
        if(queuePointerFront==queuePointerRear) sb.append(1+"\n");
        else sb.append(0+"\n");
    }
    public static void front(){
        if(queuePointerFront==queuePointerRear) sb.append(-1+"\n");
        else sb.append(arr[queuePointerRear]+"\n");
    }
    public static void back(){
        if(queuePointerFront==queuePointerRear) sb.append(-1+"\n");
        else sb.append(arr[queuePointerFront-1]+"\n");
        
    }
}