[백준] 덱 #10866

설명

자료구조 Deque 구현 문제.
JS에서는 Deque 자료구조를 제공하지 않아 직접 double-linked-list로 구현.
구현 자체는 이전에 구현했던 자료구조 Queue와 유사하다.[참고]

c++에서는 역시 Deque 자료구조를 제공하고 있기 때문에 해당 자료구조 사용법을 익히는 용도의 문제였다.

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const commands = input.slice(1);

class Node {
  prev = null;
  next = null;
  constructor(value) {
    this.value = value;
  }
}
class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push_front(value) {
    const newNode = new Node(value);
    if (this.empty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.length += 1;
  }
  push_back(value) {
    const newNode = new Node(value);
    if (this.empty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length += 1;
  }
  pop_front() {
    if (this.empty()) return -1;
    const front = this.front();
    this.head = this.head.next;
    this.length -= 1;
    return front;
  }
  pop_back() {
    if (this.empty()) return -1;
    const back = this.back();
    this.tail = this.tail.prev;
    this.length -= 1;
    return back;
  }
  size() {
    return this.length;
  }
  empty() {
    return this.length === 0 ? 1 : 0;
  }
  front() {
    if (this.empty()) return -1;
    return this.head.value;
  }
  back() {
    if (this.empty()) return -1;
    return this.tail.value;
  }
}

const solution = (N, commands) => {
  const deque = new Deque();
  let answer = '';
  commands.forEach((c) => {
    const [command, value] = c.split(' ');
    if (command.includes('push')) deque[command](value);
    else answer += deque[command]() + '\n';
  });

  return answer;
};

console.log(solution(N, commands));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    deque<int> DQ;
    int N; 
    cin >> N;
    while(N--) {
        string cmd; cin >> cmd;
        if (cmd == "push_front") {
            int x; cin >> x;
            DQ.push_front(x);
        }
        else if (cmd == "push_back") {
            int x; cin >> x;
            DQ.push_back(x);
        }
        else if (cmd == "pop_front") {
            if (DQ.empty()) cout << -1 << '\n';
            else {
                cout << DQ.front() << '\n';
                DQ.pop_front();
            }
        }
        else if (cmd == "pop_back") {
            if (DQ.empty()) cout << -1 << '\n';
            else {
                cout << DQ.back() << '\n';
                DQ.pop_back();
            }
        }
        else if (cmd == "size") {
            cout << (int)DQ.size() << '\n';
        }
        else if (cmd == "empty") {
            cout << DQ.empty() << '\n';
        }
        else if (cmd == "front") {
            if (DQ.empty()) cout << -1 << '\n';
            else cout << DQ.front() << '\n';
        }
        else if (cmd == "back") {
            if (DQ.empty()) cout << -1 << '\n';
            else cout << DQ.back() << '\n';
        }
    }
    return 0;
}