can someone explain to me how to implement multiple queues in a stack
// implement stacks using plain arrays with push and pop functions
var Stack1 = [];
var Stack2 = [];
// implement enqueue method by using only stacks
// and the push and pop functions
function Enqueue(element) {
Stack1.push(element);
}
// implement dequeue method by pushing all elements
// from stack 1 into stack 2, which reverses the order
// and then popping from stack 2
function Dequeue() {
if (Stack2.length === 0) {
if (Stack1.length === 0) { return 'Cannot dequeue because queue is empty'; }
while (Stack1.length > 0) {
var p = Stack1.pop();
Stack2.push(p);
}
}
return Stack2.pop();
}
Enqueue('a');
Enqueue('b');
Enqueue('c');
Dequeue();
You use two stacks, one for the front of the queue and one for the back of the queue. The front stack is ordered such that the first element to be dequeued is at the top, the second after that, and so on. The back stack is ordered such that the last element you queued is at the top, the previous one next, and so on.
When you need to enqueue an element, you just push it to the back stack.
When you need to dequeue an element, and the front stack is not empty, pop the first element.
The problem arises when you need to dequeue an element and the front stack is empty. Then you have to move all the elements from the back to the front. You pop them from the back and push them to the front, one at a time.
This procedure reverses the order of the elements in the back queue. An element you pop from back is pushed on top of the elements in front. So, after this, the front stack is ordered the way the invariant requires.
The first two cases are obviously constant time (with any reasonable implementation of a stack). The third is more expensive, because it potentially involves a lot of copying. However, we can argue for an amortised constant time. Each element is moved from the back to the front only once, so put a coin in the amortisation bank every time you enqueue an element, then it can pay for moving the element to the front.