2. Queue Using Two Stacks

[Problem]

Create a queue using two stacks.


[Algorithms]

  1. Create a stack.
  2. Create a queue with two instances of Stack( ).
  3. For dequeue of Queue, Move elements from stack1(inbox) to stack2(outbox), and return the highest element in outbox.


[Solution]

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
// STACK
function Stack() {
var items = [];

this.push = function() {
items.push.apply(items, arguments);
};
this.pop = function() {
return items.pop.apply(items, arguments);
};
this.size = function() {
return items.length;
};
this.peek = function() {
return items;
};
this.isEmpty = function() {
return items.length === 0;
};
}

// STACK TESTS
var stack = new Stack();
stack.push(1, 2, 3, 4, 5);
console.log(stack.peek()); // [ 1, 2, 3, 4, 5 ]
stack.pop();
console.log(stack.peek()); // [ 1, 2, 3, 4 ]


// QUEUE
function Queue() {
var inbox = new Stack();
var outbox = new Stack();

this.eneque = function() {
inbox.push.apply(inbox, arguments);
};
this.dequeue = function() {
if (outbox.size() === 0) {
while (inbox.size())
outbox.push(inbox.pop());
}
return outbox.pop();
};
this.size = function(){
return inbox.size() + outbox.size();
};
this.peek = function() {
return outbox.peek();
};
this.isEmpty = function() {
return inbox.length + outbox.length === 0;
};
this.front = function() {
if (outbox.size() === 0) {
while (inbox.size())
outbox.push(inbox.pop());
}
return outbox.peek()[0];
};
}

// QUEUE TESTS
var queue = new Queue();
console.log(queue.size()); // 0
queue.eneque(10, 20, 30, 40, 50, 60);
console.log(queue.size()); // 6
console.log(queue.peek()); // [] Not move to outbox yet
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20
console.log(queue.peek()); // [ 60, 50, 40, 30 ]
console.log(queue.front()); // 60
console.log(queue.size()); // 4
console.log(queue.dequeue()); // 30
console.log(queue.dequeue()); // 40
console.log(queue.peek()); // [ 60, 50 ]


[What I learned]

Use the value of array.pop() as parameter of other array.push()

1
2
3
4
5
6
7
this.dequeue = function() {
if (outbox.size() === 0) {
while (inbox.size())
outbox.push(inbox.pop());
}
return outbox.pop();
};