[바킹독의 실전 알고리즘] 0x07강 - 덱

정의와 성질

덱은 양쪽 끝에서 삽입과 삭제가 가능

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

덱은 양쪽에서 삽입이 가능하다. 그래서 시작 지점을 가운데로 둬야하고
시작지점은 2*MX+1
head, tail의 초기값은 MX 이다

class Node {
  constructor(item) {
    this.item = item;
    this.prev = null;
    this.next = null;
  }
}

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push_front(item) {
    const node = new Node(item);
    if (this.size() == 0) {
      this.head = node;
      this.tail = node;
    } else {
      this.head.prev = node;
      node.next = this.head;
      this.head = node;
    }
    this.length += 1;
  }

  push_back(item) {
    const node = new Node(item);
    if (this.size() == 0) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.length += 1;
  }

  pop_front() {
    if (this.size() == 0) return -1;
    const popItem = this.head;
    this.head = this.head.next;
    if (this.size() == 1) {
      this.head = null;
    } else {
      this.head.prev = null;
    }
    this.length -= 1;
    return popItem.item;
  }

  pop_back() {
    if (this.size() == 0) return -1;
    const popItem = this.tail;
    this.tail = this.tail.prev;
    if (this.size() == 1) {
      this.tail = null;
    } else {
      this.tail.next = null;
    }
    this.length -= 1;
    return popItem.item;
  }

  size() {
    return this.length;
  }

  empty() {
    if (this.length == 0) {
      return 1;
    } else {
      return 0;
    }
  }

  front() {
    if (this.empty() == 1) return -1;
    return this.head.item;
  }

  back() {
    if (this.empty() == 1) return -1;
    return this.tail.item;
  }
}

js로 구현하면 위 처럼 하면 된다. 근데 사실상 이렇게 까지 구현 할일은 없을거다. 시간초과만 안나면..