BOJ 10866 덱 [Java]

BOJ 10866 덱

- 문제 링크

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

- 문제 해설

util.Deque를 이용하면 쉽게 풀 수 있는 문제이지만 덱을 구현해보는 것에 목적을 두고 풀었다.
명령 수가 n이면 최대로 커질 수 있는 덱의 크기가 n이다.
크기가 2n이고 가운데서 head와 tail이 시작하는 배열로 덱을 구현하였다.
크기가 n인 배열로 원형 큐처럼 덱을 구현을 할 수도 있지만, 그렇게하면 push하거나 pop할 때, 기존 원소들의 위치를 이동시켜줘야하는 등의 추가로 신경써야할 것이 많아져서 그렇게 하지 않았다.

- 코드 보기

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

class Deque
{
    int head;
    int tail;
    int arr[];

    public Deque(int size)
    {
        head = size / 2;
        tail = size / 2;
        arr = new int[2 * size];
    }

    public void push_front(int x)
    {
        arr[--head] = x;
    }

    public void push_back(int x)
    {
        arr[tail++] = x;
    }

    public int pop_front()
    {
        if (head == tail)
            return -1;
        return arr[head++];
    }

    public int pop_back()
    {
        if (head == tail)
            return -1;
        return arr[--tail];
    }

    public int size()
    {
        return (tail - head);
    }

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

    public int front()
    {
        if (head == tail)
            return -1;
        return arr[head];
    }

    public int back()
    {
        if (head == tail)
            return -1;
        return arr[tail - 1];
    }
}

public class Main
{
    static int n;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        Deque deq = new Deque(n);

        for (int i = 0; i < n; i++)
        {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            if (str.equals("push_front"))
                deq.push_front(Integer.parseInt(st.nextToken()));
            else if (str.equals("push_back"))
                deq.push_back(Integer.parseInt(st.nextToken()));
            else if (str.equals("pop_front"))
                bw.write(String.valueOf(deq.pop_front()) + "\n");
            else if (str.equals("pop_back"))
                bw.write(String.valueOf(deq.pop_back()) + "\n");
            else if (str.equals("size"))
                bw.write(String.valueOf(deq.size()) + "\n");
            else if (str.equals("empty"))
                bw.write(String.valueOf(deq.empty()) + "\n");
            else if (str.equals("front"))
                bw.write(String.valueOf(deq.front()) + "\n");
            else if (str.equals("back"))
                bw.write(String.valueOf(deq.back()) + "\n");
        }

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