ShaShaKa Dev Note

덱

29 June 2019

문제 : https://www.acmicpc.net/problem/10866

이번은 덱의 개념을 익히고 실습하는 문제를 풀어보도록 하겠습니다.

import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        Deque deque = new Deque();

        for (int i = 0; i < size; i++) {
            switch (sc.next()) {
                case "push_front":
                    deque.push_front(sc.nextInt());
                    break;
                case "push_back":
                    deque.push_back(sc.nextInt());
                    break;
                case "pop_front":
                    System.out.println(deque.pop_front());
                    break;
                case "pop_back":
                    System.out.println(deque.pop_back());
                    break;
                case "size":
                    System.out.println(deque.size());
                    break;
                case "empty":
                    System.out.println(deque.empty());
                    break;
                case "front":
                    System.out.println(deque.front());
                    break;
                case "back":
                    System.out.println(deque.back());
                    break;
            }
        }
    }
}

class Deque {

    private Node head;

    private Node tail;

    private int size;

    Deque() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void push_front(int val) {
        if (this.size == 0) {
            head = tail = new Node(val, null, null);
        } else {
            Node node = new Node(val, null, head);
            head.prev = node;
            head = node;
        }
        this.size++;
    }

    public void push_back(int val) {
        if (this.size == 0) {
            head = tail = new Node(val, null, null);
        } else {
            Node node = new Node(val, tail, null);
            tail.next = node;
            tail = node;
        }
        this.size++;
    }

    public int pop_front() {
        if (this.size == 0) {
            return -1;
        } else {
            this.size--;
            int ret = head.data;
            head = head.next;
            return ret;
        }
    }

    public int pop_back() {
        if (this.size == 0) {
            return -1;
        } else {
            this.size--;
            int ret = tail.data;
            tail = tail.prev;
            return ret;
        }
    }

    public int size() {
        return this.size;
    }

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

    public int front() {
        if (this.size == 0) {
            return -1;
        } else {
            return head.data;
        }
    }

    public int back() {
        if (this.size == 0) {
            return -1;
        } else {
            return tail.data;
        }
    }
}

class Node {
    int data;
    Node prev;
    Node next;

    Node(int data) {
        this.data = data;
    }

    Node(int data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}

이번에는 덱을 구현하는 문제를 풀어보도록 하겠습니다.
덱은 head와 tail을 모두 가지고 있고, head와 tail에서 각각 입력과 출력이 가능하므로 각각을 선언해주고 구현해주도록 합니다.
이번 에제에서는 class로 Deque를 선언하고, 해당 class로 객체를 만들어 진행하도록 합니다.