[Java] 10866번. 덱

1. 문제 분석

이전에, 큐와 스택을 구현할 때는 Linked List를 이용하여 구현하였다.

 

이번에 구현할 deque도 Linked List를 이용해 구현할 수 있지만,

deque는방향이 정방향/역방향 두 방향이기 때문에 Double Linked List로 구현해야겠다는 생각이 들었다.

 

deque를 양방향 링크드 리스트(Double Linked List)로 구현하면 다음과 같은 차이점이 있다.

 

장점

각 노드가 이전 노드와 다음 노드를 모두 참조하므로, 앞과 뒤 양쪽에서 삽입과 삭제가 용이하다.

덱의 앞과 뒤에서 O(1)시간에 삽입과 삭제를 할 수 있다.

 

단점

양방향 포인터를 관리해야 하므로 구현이 더 복잡하다.

각 노드가 두 개의 포인터를 가지고 있으므로 메모리가 더 많이 사용된다.

 

2. 구현

Deque 클래스는 다음 값들로 구성되어 있다.

head : 가장 앞 노드를 의미하는 노드

tail : 마지막 노드를 의미하는 노드

size : Deque의 크기

 

push_front

정수 x를 덱의 가장 앞에 넣는다.

(1) 새로운 노드 생성

x의 값을 매개 변수로 받아 새로 추가될 노드(이하 X노드)로 만든다.

 

(2) 빈 Deque일 경우 가장 앞에 추가

만약 deque의 head가 없으면 현재 deque가 비어있다는 의미이므로

head를 X노드로 설정하고, tail도 X노드로 설정한다.

 

(3) 비어 있지 않을 경우 추가

X노드의 next 값을 deque의 head를 값으로 설정하고

기존 head 값의 prev 값을 X노드로 설정한다.

그리고, head가 바꼈으므로 head를 X노드로 변경한다.

 

(4) 사이즈 증가

가장 앞에 요소를 추가하였으므로 길이가 한 칸 늘어난다.

size값을 1 증가시킨다.

 

push_back

정수 x를 덱의 가장 뒤에 넣는다.

*push_front 과정과 3번만 다르다.

(1) 새로운 노드 생성

x의 값을 매개 변수로 받아 새로 추가될 노드(이하 X노드)로 만든다.

 

(2) 빈 Deque일 경우 가장 앞에 추가

만약 deque의 tail이 없으면 현재 deque가 비어있다는 의미이므로

tail를 X노드로 설정하고, head도 X노드로 설정한다.

 

(3) 비어 있지 않을 경우 추가

X노드의 prev 값을 deque의 tail로 설정하고

기존 tail의 next값을  X노드로 설정한다.

그리고 tail이 바꼈으므로 tail을 X노드로 변경한다.

 

(4) 사이즈 증가

가장 뒤에 요소를 추가하였으므로 길이가 한 칸 늘어난다.

size값을 1 증가시킨다.

 

pop_front

덱의 가장 앞에 있는 수를 제거하고 그 수를 반환한다. 덱이 비어있으면 -1을 반환한다.

(1) 빈 Deque일 경우 -1 리턴

head가 없으면, -1을 리턴한다.

 

(2) 비어 있지 않을 경우 가장 앞 노드 변경

head의 value값을 return 해야 하므로 변수를 생성해 저장한다.

head를 head.next로 바꾼다.

 

(3) 삭제되어서 Deque가 비어졌을 때 처리

pop이 되면서 deque가 비어진 경우에는 2번 과정을 통해서 head가 null로 지정이 된다.

deque가 비어있으면 tail도 null이 되는데 현재 tail에는 이전의 tail이 그대로 남아있기 때문에 tail도 null로 바꾼다.

 

(4) 값을 삭제한 후 head 처리

head의 prev값을 null로 바꾼다.

 

(5) 크기 감소

가장 앞 요소를 삭제하였으므로 size를 1 줄인다.

 

(6) 값 리턴

저장해둔 value값을 return한다.

 

pop_back

덱의 가장 뒤에 있는 수를 제거하고 그 수를 반환한다. 덱이 비어있으면 -1을 반환한다.

(1) 빈 Deque일 경우 -1 리턴

head가 없으면, -1을 리턴한다.

 

(2) 비어 있지 않을 경우 tail 변경

tail의 value값을 return 해야 하므로 변수를 생성해 저장한다.

tail의값을 tail.prev로 바꾼다.

 

(3) 삭제되어서 Deque가 비어졌을 때 처리

pop이 되면서 deque가 비어진 경우에는 2번 과정을 통해서 tail이 null로 지정이 된다.

deque가 비어있으면 head도 null이 되는데 현재 head에는 이전의 head가 그대로 남아있기 때문에 head도 null로 바꾼다.

 

(4) 값을 삭제한 후 head 처리

tail이 null이 아닐 때는 tail의 next값을 null로 바꾼다.

 

(5) 크기 감소

가장 앞 요소를 삭제하였으므로 size를 1 줄인다.

 

(6) 값 리턴

저장해둔 value값을 return한다.

 

size

덱에 들어있는 수의 개수를 반환한다.

(1) 사이즈 리턴

size변수를 return 한다.

 

empty

덱이 비어있으면 1을, 아니면 0을 반환한다.

(1) 비어 있을 때

size가 0이면 1을 return 한다.

 

(2) 비어 있지 않을 때

size가 0이 아니면 0을 return 한다.

 

front

덱의 가장 앞에 있는 수를 반환한다. 덱이 비어있으면 -1을 반환한다.

(1) head가 null일 때

-1을 return한다.

 

(2) head가 null이 아닐 때

head.value를 return 한다.

 

back

덱의 가장 뒤에 있는 수를 반환한다. 덱이 비어있으면 -1을 반환한다.

(1) back이 null일 때

-1을 return한다.

 

(2) back이 null이 아닐 때

back.value를 return 한다.

 

3. 최종 코드

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

class Node
{
    int value;
    Node next;
    Node prev;

    Node(int value)
    {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class MyDeque{
    private Node head;
    private Node tail;
    private int size;

    public MyDeque(){
        head = null;
        tail = null;
        size = 0;
    }

    public void pushFront(int value){
        Node newNode = new Node(value);
        if(head == null){
            head = newNode;
            tail = newNode;
        }
        else{
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }

        size++;
    }

    public void pushBack(int value){
        Node newNode = new Node(value);
        if(head == null){
            head = newNode;
            tail = newNode;
        }
        else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }

        size++;
    }

    public int popFront(){
        if(head == null)
            return -1;
        else{
            int value = head.value;
            head = head.next;

            if(head == null)
                tail = null;
            else{
                head.prev = null;
            }
            size--;

            return value;
        }
    }

    public int popBack(){
        if(tail == null)
            return -1;
        else{
            int value = tail.value;
            tail = tail.prev;

            if(tail == null)
                head = null;
            else{
                tail.next = null;
            }
            size --;

            return value;
        }
    }

    public int size(){
        return size;
    }

    public int empty(){
        if(size==0)
            return 1;
        else
            return 0;
    }

    public int front(){
        if(head == null)
            return -1;
        else
            return head.value;
    }

    public int back(){
        if(tail==null)
            return -1;
        else
            return tail.value;
    }
}


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));

        int num = Integer.parseInt(br.readLine());
        MyDeque deque = new MyDeque();

        for(int i=0; i<num; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            switch (command){
                case "push_back":
                    int value = Integer.parseInt(st.nextToken());
                    deque.pushBack(value);
                    break;
                case "push_front":
                    value = Integer.parseInt(st.nextToken());
                    deque.pushFront(value);
                    break;
                case "pop_front":
                    value = deque.popFront();
                    bw.write(Integer.toString(value)+'\n');
                    break;
                case "pop_back":
                    value = deque.popBack();
                    bw.write(Integer.toString(value)+'\n');
                    break;
                case "size":
                    value = deque.size();
                    bw.write(Integer.toString(value)+'\n');
                    break;
                case "empty":
                    value = deque.empty();
                    bw.write(Integer.toString(value)+'\n');
                    break;
                case "front":
                    value = deque.front();
                    bw.write(Integer.toString(value)+'\n');
                    break;
                case "back":
                    value = deque.back();
                    bw.write(Integer.toString(value)+'\n');
                    break;
                default:
                    bw.write("ERROR : WRONG COMMAND!\n");
            }
        }

        br.close();
        bw.close();
    }
}