자바스크립트로 알고리즘 정리하기 #3 Deque 구현 및 문제풀이

자바스크립트로 알고리즘 정리하기 #3 Deque 구현 및 문제풀이

Deque(덱)이란?

사실상 스택과 큐의 연산을 합쳐놓은 것이다.

• 양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 구조
• Double-ended Queue 의 약자이다.
• push_front() : 덱의 앞에 자료를 넣는 연산
• push_back() : 덱의 뒤에 자료를 넣는 연산
• pop_front() : 덱의 앞에서 자료를 빼는 연산
• pop_back() : 덱의 뒤에서 자료를 빼는 연산
• front() : 덱의 가장 앞에 있는 자료를 보는 연산
• back() : 덱의 가장 뒤에 있는 자료를 보는 연산

자바스크립트 덱(Deque) 구현

배열 내장 함수인 shift와 unshift를 이용해서 구현하였다.

class Deque {
  constructor() {
    this.data = [];
    this.rear = 0;
  }

  push_front(element) {
    this.data.unshift(element);
    this.rear = this.rear + 1;
  }

  push_back(element) {
    this.data[this.rear] = element;
    this.rear = this.rear + 1;
  }

  pop_front() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.shift();
    }

    return false;
  }

  pop_back() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.pop();
    }

    return false;
  }

  length() {
    return this.rear;
  }

  isEmpty() {
    return this.rear === 0;
  }

  getFront() {
    if (this.isEmpty() === false) {
      return this.data[0];
    }

    return false;
  }

  getLast() {
    if (this.isEmpty() === false) {
      return this.data[this.rear - 1];
    }

    return false;
  }

  print() {
    for (let i = 0; i < this.rear; i++) {
      console.log(this.data[i]);
    }
  }
}

boj 10866

문제 링크

딱히 무언가 해줘야하는 것 없이 그냥 CLI만 구현하면 된다.

class Deque {
  constructor() {
    this.data = [];
    this.rear = 0;
  }

  push_front(element) {
    this.data.unshift(element);
    this.rear = this.rear + 1;
  }

  push_back(element) {
    this.data[this.rear] = element;
    this.rear = this.rear + 1;
  }

  pop_front() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.shift();
    }

    return -1;
  }

  pop_back() {
    if (this.isEmpty() === false) {
      this.rear = this.rear - 1;
      return this.data.pop();
    }

    return -1;
  }

  length() {
    return this.rear;
  }

  isEmpty() {
    return this.rear === 0;
  }

  getFront() {
    if (this.isEmpty() === false) {
      return this.data[0];
    }

    return -1;
  }

  getLast() {
    if (this.isEmpty() === false) {
      return this.data[this.rear - 1];
    }

    return -1;
  }

  print() {
    for (let i = 0; i < this.rear; i++) {
      console.log(this.data[i]);
    }
  }
}

let solution = (inputLines) => {
  let deque = new Deque();
  let n = inputLines.shift();
  let answer = "";

  for (let i = 0; i < n; i++) {
    let [command, arg] = inputLines[i].split(" ");

    if (command === "push_front") {
      deque.push_front(arg);
    }

    if (command === "push_back") {
      deque.push_back(arg);
    }

    if (command === "pop_front") {
      answer += deque.pop_front() + "\n";
    }

    if (command === "pop_back") {
      answer += deque.pop_back() + "\n";
    }

    if (command === "size") {
      answer += deque.length() + "\n";
    }

    if (command === "empty") {
      answer += (deque.isEmpty() ? 1 : 0) + "\n";
    }

    if (command === "front") {
      answer += deque.getFront() + "\n";
    }

    if (command === "back") {
      answer += deque.getLast() + "\n";
    }
  }

  return answer;
};

(function () {
  let inputLines = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .split("\n");

  console.log(solution(inputLines));
})();