백준 10845-큐

깃허브:

https://github.com/MSIQOC/BOJ/blob/master/b10845_%ED%81%90.java

 

https://www.acmicpc.net/problem/10845

10845번: 큐

이전에 스택을 직접 자바로 구현해봤다면, 이번엔 큐를 자바로 구현해보았다.

 

스택과 큐의 차이:

1.스택 - LIFO (Last In First Out)

스택이란, 한쪽이 막히고 한쪽이 뚫린 구조로 마지막으로 들어온 것이 처음으로 나가게 되는 구조를 가진다. 위의 그림에서는 처음에 0, 1, 2 순서로 스택에 쌓이게 되는데, 나갈 때는 그 반대로 2, 1, 0의 순서로 나가게 된다.

 

2.큐 - FIFO (First In First Out)

큐는 스택과 달리 양쪽이 다 뚫려있는 구조를 가지고있고, 때문에 들어온 순서대로 나가게 된다고 해서 First In First Out라는 이름을 가지고있다. 위 그림에서는 0, 1, 2 순서로 들어왔기 때문에 나갈 때에도 0, 1, 2 순서로 나가게된다.

 

스택은 한 쪽이 막혀있기 때문에 스택을 나타내는 변수 stack과 스택의 사이즈 size 변수만 사용하면 됐지만, 큐는 양쪽이 다 뚫려있기 때문에 어떻게 구현해야 할지가 막막했었지만, 나중에 size 변수 하나만을 사용하는 대신 큐의 첫 숫자의 위치를 가리키는 변수 front와 마지막 숫자의 위치를 가리키는 변수 back을 사용해서 구현하는 방식을 생각해냈다. 이 때 큐의 사이즈는 back-front로 구해주었다.

 

import java.io.*;
import java.util.*;
public class b10845_ť {
    public static void main(String args[]) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int back = 0;
        int front = 0;
        int q[] = new int[10000];
        while(n-->0) {
            String s = sc.next();
            if(s.equals("push")) {
                int a = sc.nextInt();
                q[back] = a;
                ++back;
            }
            else if(s.equals("pop")) {
                if(back-front==0) 
                    bw.write("-1\n");
                else {
                    bw.write(q[front]+"\n");
                    ++front;
                }
            }
            else if(s.equals("size")) {
                bw.write(back-front+"\n");
            }
            else if(s.equals("front")){
                if(back-front==0)
                    bw.write("-1\n");
                else
                    bw.write(q[front]+"\n");
            }
            else if(s.equals("back")) {
                if(back-front==0)
                    bw.write("-1\n");
                else
                    bw.write(q[back-1]+"\n");
            }
            else if(s.equals("empty")) {
                if(back-front==0)
                    bw.write("1\n");
                else bw.write("0\n");
            }
                
        }
        bw.flush();
    }
}