[백준 10845] 큐 - 자바

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

10845번: 큐

---

1. 풀이

큐에 대해서 간단히 구현을 해보는 문제이다.

 

C언어를 공부할 때 배열을 사용한 원형 큐가 생각나서 구현해볼겸 한번 해봤더니 잘 통과한다. 

 

굳이 이렇게 풀 필요는 없다. 그저 복습할 겸 한번 구현 해보았다.

 

원형 큐는 아래와 같다.

주의 할 점은 end가 배열의 마지막 위치에 오면 다시 원점(0)으로 돌려줘야한다.

이때, 만약 f가 0에 있다면 에러를 띄워줘야 한다.

( 큐의 사이즈를 end-first로 측정하는데 큐가 꽉 찼을때 사이즈가 0이 나오면 안되기 때문. )

 

end가 마지막 위치에 있을때 원점으로 보내는 원형 큐 말고도 그냥 배열을 사용해서 풀 수도 있다.
이번 포스트는 그저 복습을 위해 원형 큐를 사용해서 구현해보았다.

---

2. 코드

import java.util.*;

// 원형 큐
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		int[] circularQueue = new int[num];
		int first = 0;
		int end = 0;
		
		while(num-- > 0) {
			String input = sc.next();
			
			if(input.equals("push")) {
				// 큐가 꽉 찼다면.
				if(end == circularQueue.length-1 && first == 0) {
					System.out.println("Error! 메모리에 남는 공간이 없습니다.");
				} else {
					// end가 배열의 끝에 있다면 원점으로 돌린다.
					if(end == circularQueue.length-1) {
						end = 0;
						circularQueue[end] = sc.nextInt();
					} else
						circularQueue[++end] = sc.nextInt();
				}
			} else if(input.equals("pop")) {
				if(first == end) // 큐가 비어 있다
					System.out.println(-1);
				else {
					System.out.println(circularQueue[++first]);
					circularQueue[first] = 0;
				} 
			} else if(input.equals("size")) {
				System.out.println(end-first);
			} else if(input.equals("empty")) {
				if(end-first == 0)
					System.out.println(1);
				else
					System.out.println(0);
			} else if(input.equals("front")) {
				if(end-first == 0)
					System.out.println(-1);
				else
					System.out.println(circularQueue[first+1]);
			} else if(input.equals("back")) {
				if(end-first == 0)
					System.out.println(-1);
				else
					System.out.println(circularQueue[end]);
			}
		}
		sc.close();
		return;
	}
}

아래는 원형큐를 사용하지 않고 그냥 배열을 사용한 코드이다.  

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		int[] arr = new int[num];
		int first = 0;
		int end = 0;
		
		while(num-- > 0) {
			String input = sc.next();
			
			if(input.equals("push")) {
				arr[end] = sc.nextInt();
				end++;
			} else if(input.equals("pop")) {
				if(first == end)
					System.out.println(-1);
				else {
					System.out.println(arr[first]);
					arr[first] = 0;
					first++;
				}
			} else if(input.equals("front")) {
				if(first == end)
					System.out.println(-1);
				else
					System.out.println(arr[first]);
			} else if(input.equals("back")) {
				if(first == end)
					System.out.println(-1);
				else
					System.out.println(arr[end-1]);
			} else if(input.equals("empty")) {
				if(first == end)
					System.out.println(1);
				else
					System.out.println(0);
			} else if(input.equals("size")) {
				System.out.println(end-first);
			}
		}
		sc.close();
		return;
	}
}

또한, 덱을 사용하여 풀이도 가능하다.

import java.util.*;
import java.io.*;

// 덱 사용
public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new 	OutputStreamWriter(System.out));//선언
        Deque<Integer> deque = new ArrayDeque<Integer>();

        int N = Integer.parseInt(br.readLine());

        while(N-- > 0){
            String[] inputs = br.readLine().split(" ");

            if(inputs[0].equals("push")){
                deque.addFirst(Integer.parseInt(inputs[1]));
            } else if(inputs[0].equals("pop")){
                if(deque.isEmpty())
                    System.out.println(-1);
                else
                    System.out.println(deque.pollLast());
            } else if(inputs[0].equals("size")){
                System.out.println(deque.size());
            } else if(inputs[0].equals("empty")){
                if(deque.isEmpty())
                    System.out.println(1);
                else
                    System.out.println(0);
            } else if(inputs[0].equals("front")){
                if(deque.isEmpty())
                    System.out.println(-1);
                else
                    System.out.println(deque.peekLast());
            } else if(inputs[0].equals("back")){
                if(deque.isEmpty())
                    System.out.println(-1);
                else
                    System.out.println(deque.peekFirst());
            }

        }
    }

}