JAVA)10866번 Deque(덱) 구현하기 (DoublyLinkedList (이중연결리스트) 사용)

Deque(덱)은 양 끝에서만 데이터를 넣거나 뺄 수 있는 자료구조이다.

Double-ended queue의 약자이다.

덱에는 front와 back 요소가 있으며, 각 각 맨앞과 맨뒤를 의미한다.

front 또는 back에만 원소를 추가할 수 있고, front 또는 back에 위치한 원소만 빼낼 수 있다.

이러한 특성을 가진 덱을 구현하기 위해, DoublyLinkedList(이중연결리스트)를 사용하여 구현하였다.

 

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        MyDeque deque = new MyDeque();
        int N = Integer.parseInt(br.readLine());
        for (int i=0;i<N;i++) {
            String[] command = br.readLine().split(" ");
            switch (command[0]) {
                case "push_front" :
                    deque.push_front(Integer.parseInt(command[1]));
                    break;
                case "push_back" :
                    deque.push_back(Integer.parseInt(command[1]));
                    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.getSize());
                    break;
                case "empty" :
                    System.out.println(deque.isEmpty());
                    break;
                case "front" :
                    System.out.println(deque.getFront());
                    break;
                case "back" :
                    System.out.println(deque.getBack());
                    break;
            }
        }
    }
}

class MyDeque { // Doubly Linked List로 구현
    Node head, tail = null;
    int size = 0;

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

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

    public void push_front(int item) {
        Node node = new Node(item);
        Node temp = head;
        head = node;
        head.next = temp;
        if (temp != null) {
            temp.prev = head;
        }
        size++;
        if (size == 1) {
            tail = head;
        }
    }

    public void push_back(int item) {
        Node node = new Node(item);
        Node temp = tail;
        tail = node;
        tail.prev = temp;
        if (temp != null) {
            temp.next = tail;
        }
        size++;
        if (size == 1) {
            head = tail;
        }
    }

    public int pop_front() {
        if (head == null) {
            return -1;
        }
        Node temp = head;
        head = temp.next;
        int val = temp.value;
        if (head != null) {
            head.prev = null;
        } else {
            tail = head;
        }
        size--;
        return val;
    }

    public int pop_back() {
        if (tail == null) {
            return -1;
        }
        Node temp = tail;
        tail = temp.prev;
        int val = temp.value;
        if (tail != null) {
            tail.next = null;
        } else {
            head = tail;
        }
        size--;
        return val;
    }

    public int getSize() {
        return size;
    }

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

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

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

 

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