백준 18258 - JAVA 큐 구현하기

일반적으로 큐는 선입선출의 형태이므로, front와 back 을 지정해두고, front가 pop되면 모든 요소를 다 한칸 앞으로 당겨야한다 .

하지만 모든 연산의 시간복잡도가 O(1) 이 되기를 요구했으므로, 위의 방법을 사용하게 되면 n개의 요소를 모두 옮겨야해서 O(n)의 시간복잡도가 나올것이다 .

 

그렇기때문에, 요소가 추가되고 빠짐에 따라 요소를 옮기지 않고, front 와 back 을 값을 새로고침 하기로 하였다 .

요소가 하나 추가 : back ++

젤 앞의 요소가 pop : front-- 

 

import java.util.*;
import java.io.*;
class Main{
    static int que[];
    static int size=0;
    static int front=0;
    static int back=0;
    static void push(int x){
        que[back++]=x;
        size++;
    }
    static int pop() {
        if(size<=0) 
            return -1;
        else {
            size--;
            return que[front++];
        }
    }
    static int size() {
        return size;
    }
    static int empty() {
        return size<=0?1:0;
    }
    static int front() {
        if(size<=0) return -1;
        return que[front];
    } 
    static int back() {
        if(size<=0) return -1;
        return que[back-1];
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder();
    
        int num=Integer.parseInt(br.readLine());    
        que=new int[num];
        
        StringTokenizer st;
        
        while(num-- >0) {
            String test=br.readLine();
            st=new StringTokenizer(test," ");
            switch(st.nextToken()) {
             
            case "push" :
                push(Integer.parseInt(st.nextToken()));
                break;
            case "pop" :
                sb.append(pop()).append('\n');
                break;
            case "size":
                sb.append(size()).append('\n');
                break;
            case "empty":
                sb.append(empty()).append('\n');
                break;
            case "front":
                sb.append(front()).append('\n');
                break;
            case "back":
                sb.append(back()).append('\n');
                break;
                
                
            }
        }
        System.out.println(sb);
    }
}
 

+)어제 스택을 구현하면서 터득한 bufferedreader 와 stringbuilder 을 잘 사용하여서 열심히 구현하였는데, 계속 front 값이 제대로 출력되지 않는 오류가 발생하였다 .

알고보니 push() 부분의 함수를 que[front++]로 하고있었다 .. 몽총이

que[back++]으로 하여서  , back 부분에 하나를 요소를 넣고 back 값을 1더해주면 제대로 자~알 돌아갔다 !!