[알고리즘/백준] 10866 덱(자바, 링 버퍼)

문제

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

풀이 코드

• 덱(Deque)이란? 양방향으로 삽입과 삭제를 모두 할 수 있는 자료구조이다.
• 배열의 처음과 끝이 논리적으로 연결 되어있는 링버퍼 구조를 사용하여 구현.
  • 첫번째 요소, 마지막 요소를 식별하기 위한 front, rear 변수 필요

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static class Deque {
        int[] arr;
        int front = 0; //앞쪽에 삽입할 위치
        int rear = 1; //뒤쪽에 삽입할 위치
        int size = 0;

        public Deque(int n) {
            arr = new int[n];
        }

        public void pushFront(int x) {
            arr[front--] = x;
            size++;

            //배열의 앞뒤가 이어져 있는 구조이기 때문에
            //front가 가리키는 위치가 배열의 맨앞을 넘어서면 배열의 마지막으로 이동
            if (front <= -1) {
                front = arr.length - 1;
            }
        }

        public void pushBack(int x) {
            arr[rear++] = x;
            size++;

            //배열의 앞뒤가 이어져 있는 구조이기 때문에
            //rear가 가리키는 위치가 배열의 맨 뒤를 넘어서면 맨 앞으로 이동
            if (rear >= arr.length) {
                rear = 0;
            }
        }

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

            //front가 가리키는 위치는 삽입할 위치이기 때문에
            //pop을 하려면 front의 위치를 이전으로 옮기고 그 값을 반환해주어야한다.
            //배열의 앞뒤가 이어져있는 구조이기 떄문에 front의 위치가 배열의 맨 끝이라면 이전 front의 위치는 맨 앞인 0일 것이다.
            // 그렇기 때문에 front가 배열의 끝일 경우 front를 0으로 바꿔주고, 나머지의 경우 front를 +1 해준다.
            if (front >= arr.length-1) {
                front = 0;
            } else {
                front++;
            }

            size--;

            return arr[front];
        }

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

            //rear가 가리키는 위치는 삽입할 위치이기 때문에
            //pop을 하려면 rear의 위치를 이전으로 옮기고 그 값을 반환해주어야한다.
            //배열의 앞뒤가 이어져있는 구조이기 때문에 rear의 위치가 배열의 맨 앞이라면 이전 rear의 위치는 배열의 맨 뒤일 것이다.
            // 그렇기 때문에 rear가 배열의 맨 앞일 경우 rear가 가리키는 곳을 배열의 맨 뒤로 바꿔주고, 나머지의 경우 rear를 -1 해준다.
            if (rear <= 0) {
                rear = arr.length-1;
            } else {
                rear--;
            }

            size--;

            return arr[rear];
        }

        public int size() {
            return size;
        }

        public int empty() {
            return size == 0 ? 1 : 0;
        }

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

            //배열의 앞뒤가 이어져있는 구조이고, front 변수가 가리키는 위치는 삽입할 위치이기 때문에 front의 이전 위치를 반환해줘야한다.
            //그렇기 때문에 현재 front가 가리키는 위치가 배열의 맨 끝이라면, 배열의 첫번째 요소를 반환해주어야한다.
            if (front >= arr.length-1) {
                return arr[0];
            }

            return arr[front+1];
        }

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

            //배열의 앞뒤가 이어져있는 구조이고, rear 변수가 가리키는 위치는 삽입할 위치이기 때문에 rear의 이전 위치를 반환해줘야한다.
            //그렇기 때문에 현재 rear가 가리키는 위치가 배열의 맨 앞이라면, 배열의 마지막 요소를 반환해주어야한다.
            if (rear <= 0) {
                return arr[arr.length-1];
            }

            return arr[rear-1];
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Deque deque = new Deque(n);

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            String command = st.nextToken();

            if (command.equals("push_front")) {
                int x = Integer.parseInt(st.nextToken());
                deque.pushFront(x);
            } else if (command.equals("push_back")) {
                int x = Integer.parseInt(st.nextToken());
                deque.pushBack(x);
            } else if (command.equals("pop_front")) {
                sb.append(deque.popFront()).append("\n");
            } else if (command.equals("pop_back")) {
                sb.append(deque.popBack()).append("\n");
            } else if (command.equals("size")) {
                sb.append(deque.size()).append("\n");
            } else if (command.equals("empty")) {
                sb.append(deque.empty()).append("\n");
            } else if (command.equals("front")) {
                sb.append(deque.front()).append("\n");
            } else if (command.equals("back")) {
                sb.append(deque.back()).append("\n");
            }
        }

        System.out.println(sb);
    }
}