[백준] 10845 : 큐 (Queue와 ArrayDeque) - JAVA

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

10845번: 큐

 

 

# 문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

# 예제

입력

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

 

출력

1
2
2
0
1
2
-1
0
1
-1
0
3

 

 

# 필요개념

사실 if문 때려박고 메소드 활용하면 되는 문제지만 큐에 대해 정리하고 싶어서 쓰려고 한다.

Queue는 메소드이고, 클래스를 사용해줘야 하는데 스택과 달리 큐는 선택지가 2가지였다.

• ArrayDeque
• LinkedList

구현할 때 둘의 차이에 대해 알아보자.

 

ArrayDeque와 LinkedList

우선 Deque는 Double-Ended Queue의 줄임말로, 큐의 양쪽에서 데이터를 삭제, 삽입할 수 있는 자료구조이다.

ArrayDeque는 Deque의 구현체로 배열의 특성을 가지고 있다. 이와 달리 LinkedList는 List와 Queue의 구현체라서 List의 특성을 가지고 있다.

 

원소를 넣고 뺄 것을 생각하면 공간 비효율성을 고려해 리스트의 구현체인 LinkedList가 더 좋지 않을까 하는 생각을 할 수 있으나, 자바의 공식문서에 따르면 ArrayDeque로 구현하는 게 LinkedList로 구현하는 것보다 빠르다고 한다.

 

>> 수행속도 : ArrayDeque는 Array에 의해 지원되고, Array는 LinkedList보단 cache-locality에 더 친숙하다고 한다. 바꿔말하면 LinkedList는 다음 노드가 있는 곳으로 가려면 다른 간접적 경로들을 거쳐야 한다는 것이다.

 

>> 메모리 : ArrayDeque는 다음 노드에 대한 추가 참조를 유지할 필요가 없어 메모리 효율적이다.

 

따라서 구현할 땐 ArrayDeque를 사용하는 게 효율적일 수 있다. 그럼 메소드를 살펴보자

 

 

ArrayDeque 메소드

메소드	설명
addFirst()	Deque의 맨 앞에 데이터 삽입. 초과시 Exception 발생
addLast() (= add())	Deque의 맨 뒤에 데이터 삽입. 초과시 Exception 발생
removeFirst()	첫번째부터 삭제 (순서대로). 비어있으면 Exception 발생
poll()	첫번째부터 삭제. 비어잇으면 null 리턴
removeList()	마지막부터 삭제. 비어있으면 Exception 발생
size()	크기 리턴
getFirst(), peekFirst(), peek()	첫번째 데이터 가져오기
getLast(), peekLast()	마지막 데이터 가져오기
clear()	모두 삭제

 

자주 쓸법한 것만 정리했다.

 

# Code

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0 ; i < n ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            if (s.equals("push")) {
                int a = Integer.parseInt(st.nextToken());
                queue.add(a);
            }
            else if (s.equals("pop")) {
                if (queue.isEmpty()) sb.append(-1).append("\n");
                else sb.append(queue.poll()).append("\n");
            }
            else if (s.equals("size")) sb.append(queue.size()).append("\n");
            else if (s.equals("empty")) sb.append(queue.isEmpty() ? 1 : 0).append("\n");
            else if (s.equals("front")) {
                if (queue.isEmpty()) sb.append(-1).append("\n");
                else sb.append(queue.peek()).append("\n");
            }
            else if (s.equals("back")) {
                if (queue.isEmpty()) sb.append(-1).append("\n");
                else {
                    Object[] arr = queue.toArray();
                    sb.append(arr[arr.length - 1]).append("\n");
                }
            }
        }
        System.out.println(sb);
    }
}

 

# 결과