Baekjoon 문제 풀기 (10866번 : 덱) Java

10866번 : 덱

1. 문제읽기

---

덱 구현 문제

2. 제출 코드

---

큐처럼 구현하면 되겠지 하고 시도하다가 push부터 막혔다..
처음에 넣을 때 인덱스가 0일때보다 작을 때 어떻게 넣어야하지?? 했는데 링버퍼(=원형큐 : 처음과 끝이 논리적으로 연결된 큐를 구현한 자료구조)를 사용하여 구현해야한다.
큐와 마찬가지로 LinkedList로 구현하는 것이 더 효율적이지만 배열로 시작했다.
왜 다들 변수 이름으로 rear를 쓸까 궁금했는데 큐에서 데이터를 넣는 쪽을 rear라고 한다고 한다. 몰랐다^^

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

public class BOJ10845 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        Queue queue = new Queue(n);
        StringBuilder sb = new StringBuilder();
        while(n --> 0) {
            String[] cmds = bf.readLine().split(" ");
            if(cmds.length == 2) {
                queue.push(Integer.parseInt(cmds[1]));
            }
            switch(cmds[0]) {
                case "front":
                    sb.append(queue.front()).append("\n");
                    break;
                case "back":
                    sb.append(queue.back()).append("\n");
                    break;
                case "size":
                    sb.append(queue.size()).append("\n");
                    break;
                case "pop":
                    sb.append(queue.pop()).append("\n");
                    break;
                case "empty":
                    if(queue.isEmpty()){
                        sb.append(1).append("\n");
                        break;
                    }
                    sb.append(0).append("\n");
                    break;
            }
        }
        System.out.println(sb);
    }
}

class Queue {
    private int[] queue;
    private int frontIndex = 0;
    private int backIndex = 0;

    Queue() {}

    Queue(int num) {
        queue = new int[num];
    }
    public void push(int num) {
        queue[backIndex++] = num;
    }
    public int size() {
        return backIndex - frontIndex;
    }
    public boolean isEmpty() {
        if(size()==0) {
            return true;
        } else {
            return false;
        }
    }
    public int pop() {
        if(isEmpty()) {
            return -1;
        }
        return queue[frontIndex++];
    }
    public int front() {
        if(isEmpty()) {
            return -1;
        }
        return queue[frontIndex];
    }

    public int back() {
        if(isEmpty()){
            return -1;
        }
        return queue[backIndex-1];
    }
}

3. 공부할 것

---

큐와 대체적으로 비슷한 로직인데, 앞에 값을 넣을 때 -를 해주는 것과 0 이하일 경우 가장 끝 인덱스로 돌리는 것, 끝에 값을 넣을 때는 반대인 것만 달랐던 것 같다.

원형큐를 사용하는 이유는, 그냥 큐는 데이터를 꺼내게 되면 앞으로 값을 한칸씩 땡겨줘야하기 때문에 O(N)의 복잡도가 되는데, 원형큐를 사용하게 되면 복잡도를 N(1)로 줄일 수 있어서라고 한다.
또한 선형큐의 경우 front와 rear의 값이 계속 증가만 하기 때문에 비효율 적인데, 이러한 메모리 낭비를 줄일 수 있다는 장점도 있다.