백준 10866 덱 | JavaScript 덱

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

---

이 문제를 풀기 전에 10845번 큐를 먼저 푸는 것을 추천한다🙌

덱(Deque)란?

Double Ended Queue 의 줄임말로, 양방향 큐를 뜻한다.

일반 큐의 경우

이렇게 단방향으로만 삽입/삭제가 가능하다. (선입선출 형태)

double ended queue를 직역해보면 양 끝이 모두 큐이다.

단방향으로만 삽입/삭제가 가능한 큐가 양쪽 끝으로 붙어있으니, 양방향으로 삽입/삭제가 모두 가능하게 된다 !!

구현하기

카드2 문제와 같이 클래스로 구현했다. 배열의 형태로도 구현할 수 있겠지만 덱의 앞쪽에 삽입/삭제하는 경우에 시간 효율이 좋지 않을 것이다.

push_front X: 정수 X를 덱의 앞에 넣는다.

  push_front(x) {
    this.start--;
    this.deque[this.start] = x;
  }

start는 현재 첫번째 요소의 key값이므로, 값을 먼저 감소시킨 후 삽입해야한다.

push_back X: 정수 X를 덱의 뒤에 넣는다.

  push_back(x) {
    this.deque[this.end++] = x;
  }

pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

  pop_front() {
    if (this.end - this.start <= 0) {
      answer.push(-1);
      return;
    }
    const value = this.deque[this.start.toString()];
    delete this.deque[this.start.toString()];
    this.start++;
    answer.push(value);
  }

큐가 비어있는 경우는 start와 end의 값이 같을 것이다. 그리고 혹시나 이전에 연산이 잘못되어 start값이 end값보다 커진 경우도 포함하여 결과값을 저장하는 배열에 -1을 추가하도록 했다.

큐에 값이 있는 경우에는 첫번째 값에 접근하여 값을 삭제하고, 결과값 배열에 추가한다. 이 때 덱은 객체로 구현했으므로 인덱스를 꼭 문자열로 변환하여 접근해야한다 !!

pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

  pop_back() {
    if (this.end - this.start <= 0) {
      answer.push(-1);
      return;
    }
    const value = this.deque[this.end - 1];
    delete this.deque[this.end - 1];
    this.end--;
    return answer.push(value);
  }

큐가 비어있는 경우는 pop_front와 동일하게 처리한다.
end 값은 다음에 값을 추가할 위치이므로, -1을 해야 현재 가장 뒤에 있는 값의 인덱스가 된다.

size: 덱에 들어있는 정수의 개수를 출력한다.

  size() {
    answer.push(this.end - this.start);
  }

empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.

  empty() {
    return answer.push(this.end - this.start == 0 ? 1 : 0);
  }

front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

  front() {
    if (this.start === this.end) {
      answer.push(-1);
    } else {
      answer.push(this.deque[this.start]);
    }
  }

back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

  back() {
    if (this.start === this.end) {
      answer.push(-1);
    } else {
      answer.push(this.deque[this.end - 1]);
    }
  }

이후에는 입력값에 따라 해당 함수들을 호출하면 된다!

---

전체 코드

let answer = [];

class Queue {
  constructor() {
    this.deque = {};
    this.start = 0;
    this.end = 0;
  }

  push_front(x) {
    this.start--;
    this.deque[this.start] = x;
  }

  push_back(x) {
    this.deque[this.end++] = x;
  }

  pop_front() {
    if (this.end - this.start <= 0) {
      answer.push(-1);
      return;
    }
    const value = this.deque[this.start.toString()];
    delete this.deque[this.start.toString()];
    this.start++;
    answer.push(value);
  }

  pop_back() {
    if (this.end - this.start <= 0) {
      answer.push(-1);
      return;
    }
    const value = this.deque[this.end - 1];
    delete this.deque[this.end - 1];
    this.end--;
    return answer.push(value);
  }

  size() {
    answer.push(this.end - this.start);
  }

  empty() {
    return answer.push(this.end - this.start == 0 ? 1 : 0);
  }

  front() {
    if (this.start === this.end) {
      answer.push(-1);
    } else {
      answer.push(this.deque[this.start]);
    }
  }

  back() {
    if (this.start === this.end) {
      answer.push(-1);
    } else {
      answer.push(this.deque[this.end - 1]);
    }
  }
}

function solution(array) {
  let q = new Queue();

  for (let i in array) {
    if (array[i].startsWith("push_front")) {
      q.push_front(array[i].split(" ")[1]);
    } else if (array[i].startsWith("push_back")) {
      q.push_back(array[i].split(" ")[1]);
    } else if (array[i] === "pop_front") {
      q.pop_front();
    } else if (array[i] === "pop_back") {
      q.pop_back();
    } else if (array[i] === "size") {
      q.size();
    } else if (array[i] === "empty") {
      q.empty();
    } else if (array[i] === "front") {
      q.front();
    } else if (array[i] === "back") {
      q.back();
    }
  }
  return answer;
}

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", (line) => {
  input.push(line);

  if (input.length === parseInt(input[0]) + 1) {
    rl.close();
  }
}).on("close", () => {
  const count = parseInt(input[0]);
  const array = input.slice(1, count + 1);

  console.log(solution(array).join("\n"));
});