data-structure-algorithms/dataStructure/Deque/DequeArray.js at master · theashraf/data-structure-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Deque {
  constructor(capacity) {
    this._arr = Array(capacity || 100);
    this._size = this._first = 0;
  }
  // O(1)
  addFirst(data) {
    if (this._size === this._arr.length) throw new Error("Deque is Full");
    else if (this.isEmpty()) {
      this._arr[this._first] = data;
      ++this._size;
    } else {
      this._first = (this._first - 1 + this._arr.length) % this._arr.length;
      this._arr[this._first] = data;
      ++this._size;
    }
  }
  // O(1)
  addLast(data) {
    if (this._size === this._arr.length) throw new Error("Deque is Full");
    else if (this.isEmpty()) {
      this._arr[this._first] = data;
      ++this._size;
    } else {
      const last = (this._first + this.size()) % this._arr.length;
      this._arr[last] = data;
      ++this._size;
    }
  }
  // O(1)
  removeFirst() {
    if (this.isEmpty()) {
      return null;
    } else {
      let data = this._arr[this._first];
      this._first = (this._first + 1 + this._arr.length) % this._arr.length;
      --this._size;
      return data;
    }
  }
  // O(1)
  removeLast() {
    if (this.isEmpty()) {
      return null;
    } else {
      let data = this._arr[(this._first + this.size() - 1) % this._arr.length];
      --this._size;
      return data;
    }
  }
  // O(1)
  first() {
    return this.isEmpty() ? null : this._arr[this._first];
  }
  // O(1)
  last() {
    return this.isEmpty()
      ? null
      : this._arr[(this._first + this.size() - 1) % this._arr.length];
  }
  // O(1)
  isEmpty() {
    return this._size === 0;
  }
  // O(1)
  size() {
    return this._size;
  }
}

// main
// const q = new Deque(4);

// q.addFirst(3);
// q.addFirst(7);
// q.addFirst(11);
// q.addLast(5);

// console.log(q.first());
// console.log(q.size());
// console.log(q.first());
// console.log(q.last());
// console.log(q.removeLast());
// console.log(q.first());
// console.log(q.last());
// console.log(q.first());