[백준] java 28279 덱 2

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

문제

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

명령은 총 여덟 가지이다.

1 X: 정수 X를 덱의 앞에 넣는다. (1 ≤ X ≤ 100,000)
2 X: 정수 X를 덱의 뒤에 넣는다. (1 ≤ X ≤ 100,000)
3: 덱에 정수가 있다면 맨 앞의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
4: 덱에 정수가 있다면 맨 뒤의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
5: 덱에 들어있는 정수의 개수를 출력한다.
6: 덱이 비어있으면 1, 아니면 0을 출력한다.
7: 덱에 정수가 있다면 맨 앞의 정수를 출력한다. 없다면 -1을 대신 출력한다.
8: 덱에 정수가 있다면 맨 뒤의 정수를 출력한다. 없다면 -1을 대신 출력한다.

입력

첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.

출력을 요구하는 명령은 하나 이상 주어진다.

풀이과정

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

이중 연결 리스트로 덱을 구현하면 쉽게 풀 수 있는 문제이다. CustomLinkedList와 Node 클래스를 통해 덱을 구현하여 풀이하였다.

    static class CustomLinkedList{
        Node firstNode;
        Node lastNode;
        int size;
        CustomLinkedList(){
            firstNode = null;
            lastNode = null;
            size = 0;
        }
        // 1.
        public void addFront( int X ){
            Node node = new Node(X);
            if( firstNode == null ){
                firstNode = node;
                lastNode = node;
            }else {
                node.nextNode = firstNode;
                firstNode.previousNode = node;
                firstNode = node;
            }
            size++;
        }
        // 2.
        public void addBack( int X ){
            Node node = new Node(X);
            if( firstNode == null ){
                firstNode = node;
                lastNode = node;
            }else {
                lastNode.nextNode = node;
                node.previousNode = lastNode;
                lastNode = node;
            }
            size++;
        }
        // 3.
        public int popFront(){
            if( size == 0 )
                return -1;
            else if( size == 1 ){
                Node node = firstNode;
                firstNode = null;
                lastNode = null;
                size--;
                return node.value;
            }
            else {
                Node node = firstNode;
                firstNode = firstNode.nextNode;
                size--;
                return node.value;
            }
        }
        // 4.
        public int popBack(){
            if( size == 0 )
                return -1;
            else if( size == 1 ){
                Node node = lastNode;
                firstNode = null;
                lastNode = null;
                size--;
                return node.value;
            }
            else {
                Node node = lastNode;
                lastNode = lastNode.previousNode;
                size--;
                return node.value;
            }
        }
        // 5.
        public int size(){
            return size;
        }
        // 6.
        public int isEmpty(){
            if( size == 0 )
                return 1;
            else
                return 0;
        }
        // 7.
        public int readFront(){
            if( size == 0 )
                return -1;
            else
                return firstNode.value;
        }
        // 8.
        public int readBack(){
            if( size == 0 )
                return -1;
            else
                return lastNode.value;
        }
    }
    
    static class Node{
        int value;
        Node nextNode;
        Node previousNode;
        Node( int value ){
            this.value = value;
            this.nextNode = null;
            this.previousNode = null;
        }
    }

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

        CustomLinkedList dequeue = new CustomLinkedList();
		// 명령에 따른 메서드 호출
        while( N-- > 0 ){
            st = new StringTokenizer(br.readLine(), " ");
            int order = Integer.parseInt(st.nextToken());
            switch (order){
                case 1:
                    dequeue.addFront(Integer.parseInt(st.nextToken()));
                    break;
                case 2:
                    dequeue.addBack(Integer.parseInt(st.nextToken()));
                    break;
                case 3:
                    sb.append(dequeue.popFront()).append("\n");
                    break;
                case 4:
                    sb.append(dequeue.popBack()).append("\n");
                    break;
                case 5:
                    sb.append(dequeue.size()).append("\n");
                    break;
                case 6:
                    sb.append(dequeue.isEmpty()).append("\n");
                    break;
                case 7:
                    sb.append(dequeue.readFront()).append("\n");
                    break;
                case 8:
                    sb.append(dequeue.readBack()).append("\n");
                    break;
            }
        }
        System.out.println(sb.toString());
    }