[queue] 큐 기본문제와 상속

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

명령은 총 여섯가지이다.

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

(출처: https://www.acmicpc.net/problem/10845)

저번에 스택에서 풀던 문제랑 같아서 별반 어려움은 없었다. 다만 큐를 받는 실 클래스에 대한 의문을 안 품을 수가 없었다.

내가 알고 있는 큐를 받는 구현 클래스는 ArrayDeque, LinkedList, PriorityQueue정도인데 P.Q는 보통 알고 있는 큐와는 좀 다른 식으로 작동하는 거라서 우선 제외를 했고, linkedlist 로 하려다 그래도 이름이 가장 큐스러운 arraydeque로 결정했다. 

별 생각없이 문제를 풀다가 잠시 막혔던 부분이 있었는데 바로 "back: 큐의 가장 뒤에 있는 정수를 출력한다." 요것이었다. 큐의 경우 집어넣은 순서대로 밖으로 빠져나가는데, 가장 앞에 있는 숫자는 peek()으로 가져오면 되지만 맨 마지막의 경우는 어떻게 가져와야 할까 고민스러웠기 때문이다.

Queue<Integer> que = new ArrayDeque<Integer>();

처음 구현할 때는 이렇게 구현을 했다. 그런데 저 메소드에 부딪히자 고민이 시작되었다. 어떻게 마지막 정수를 가져올 것인가. 

queue 인터페이스의 경우 메소드가 offer(집어넣기-push), peek(맨 앞의 정수 가져오되 안 지우기), poll(맨 앞의 정수 가져오고 목록에서 빼기) 요정도뿐이었기에 어떻게 할까 고민을 해야했다. 그래서 앗싸리 ArrayDeque클래스를 그냥 뒤져봤다. 오메 그랬더니말야

 

보란듯이 getLast가 있었다. getFirst도 있다. 하여간 괜찮은 메소드들이 좌르르 있었다.

하지만 getLast를 아무리 쳐도 빨간줄로 에러만 나는 것이것이것이것이었다. 매우 짜증나지 않을 수가 없었다. 

그래서 다시 확인할 수 밖에 없었는데, 

어째서인지 implements에 Queue는 없고 Deque만 있다.

??????????????????

그래서 이름이 Queue스러운 Deque를 확인했다.

그런 거시었음다음다음다음다음다음다

음다음다음다음다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

deque가 큐를 상속받고 있었고 getFirst, getLast와 같은 메소드들은 모두 queue가 아닌 deque에서 구현되고 있었다. 

그래서 queue로만 생성하면 자꾸 빨간줄 뜨고 난리나고 화가나고 자증이 스멀스멀 나고 오메야 저메야 했던 것.

사실 문제를 제출 할 때는 이런거 찾아보기 전에 아이 나몰라라~ 하고 

ArrayDeque<Integer> que = new ArrayDeque<>();

로 구현해서 문제를 풀었는데, 이렇게 찾아보면서 

Deque<Integer> que = new ArrayDeque<Integer>();

로 다시 만들어보니 빨간 줄 안 뜨고 잘 돌아간다. (사실 당연한거슬)

창피한 이야기이지만 

상속과 다형성을 이제야 비로소 이해합니다. 기념비스러운 날이 아닐 수 없습니다.

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

그래서 앞으로는 어떤걸 구현 할 때 가장 최고 위에 있는거, 이거저거 다 상속받은애를 직접 선언해서 구현해야겠다는 생각을 했습니다.

(근데 메모리가 좀 크던데, 그래서 그런건가? 아예 필요한 기능만 갖춘 애로 선언을 하는게 메모리나 속도면에서는 더 나으려나?)

사실 친근한 LinkedList하다가 queue로 선언했을 때 왜 안돼 왜 안돼 했었는데, List, deque를 상속받지 않은 링크드여서 이거저거 다 안됐던 것. ㅋㅋㅋㅋ 링크드 리스트도

deque를 받고 있으므로. 게다가 리스트도 받고 있어서 인덱스로 접근할 수도 있다. 여러모로 편리왕편리

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 만약 예전에 하던 것처럼 List<Integer>list = LinkedList<>();로 구현하면 list만 있고 큐기능은 없는 링크드를 사용하게 되겠쪙!? 그런거 맞쪙!?!?!??

기분좋은 문제풀이였다. 전혀 상관없는 문제였지만.... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

쨌든 맞음!!

import java.util.*;
 
public class Queue1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        ArrayDeque<Integer> que = new ArrayDeque<Integer>();
        
        int N = scan.nextInt();
        for(int i=0 ; i<=N ; i++) {
            String phrase = scan.nextLine();
            if(phrase.equals("pop")) {
                if(que.isEmpty()) {
                    System.out.println("-1");
                } else {
                    System.out.println("pop: " + que.poll());
                }
            }else if(phrase.equals("size")) {
                System.out.println(que.size());
            }else if(phrase.equals("empty")) {
                if(que.isEmpty()) {
                    System.out.println("1");
                } else {
                    System.out.println("0");
                }
            }else if(phrase.equals("front")) {
                if(que.isEmpty()) {
                    System.out.println("-1");
                } else {
                    System.out.println("front: " + que.peek() );
                }
            }else if(phrase.equals("back")) {
                if(que.isEmpty()) {
                    System.out.println("-1");
                } else {
                    que.getLast();
                    System.out.println("back: " +que.getLast());
                }
            }else if(phrase.split(" ").length == 2) {
                String voca [] = phrase.split(" ");
                int B = Integer.parseInt(voca[1]);
                que.offer(B);
                System.out.println("push: " + B );
            }
        }
        
        scan.close();
    }
 
}