Data-Structure/priority-queue.js at master · saeed-vayghan/Data-Structure · 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
87
88
89
90
91
92
93
94
95
96
97
98
99
/* Queues */

function Queue () {
  const storage = [];

  this.enqueue = function(member) {
    storage.push(member);
  };

  this.dequeue = function() {
    return storage.shift();
  };

  this.size = function() {
    return storage.length;
  };

  this.isEmpty = function() {
    return this.size() === 0;
  };

  this.print = function() {
    console.log(storage);
  };
};

function PriorityQueue () {
  const storage = [];

  this.enqueue = function(member) {
    // member[0] = message
    // member[1] = priority

    if (this.isEmpty()) {
      storage.push(member);

    } else {

      /*
      * We can user Heap data structure here for better efficiency (O(log n)).
      */

      let added = false;

      for (let i = 0; i < storage.length; i ++) {

         if (member[1] < storage[i][1]) {
          storage.splice(i,0,member);
          added = true;

          break;
        }
      }

      if (!added) {
        storage.push(member);
      }
    }
  };

  this.dequeue = function() {
    return storage.shift();
  };

  this.size = function() {
    return storage.length;
  };

  this.isEmpty = function() {
    return this.size() === 0;
  };

  this.print = function() {
    console.log(storage);
  };
}


const q = new Queue();

q.enqueue('a');
q.enqueue('b');
q.enqueue('c');
q.print();
q.dequeue();
q.print();
console.log( q.isEmpty() );


const pq = new PriorityQueue();

pq.enqueue(['a', 2]);
pq.enqueue(['b', 3]);
pq.enqueue(['c', 7]);
pq.enqueue(['e', 0]);
pq.enqueue(['d', 2]);
pq.print();
pq.dequeue();
pq.print();