Recently, Google revealed that they have asked applicants to construct a queue using only a single stack.
This might seem impossible, but it’s doable, using some trickery. Feel free to try it yourself.
Hints
This won’t have nice time complexities.
Think about how you might be able to store information without using an array or an object.
class Queue {
constructor() {
this._storage = [];
// Your code here
enqueue(Item) (
// Your code here
}
dequeue() (
// Your code here
}
get size() (
// Your code here
}
}
Solution
class Queue {
constructor() {
this._storage = [];
}
enqueue(...items) {
this._storage.push(...items);
}
dequeue() {
if(this._storage.length > 1) {
const lastltem = this._storage.pop();
const firstItem = this.dequeue();
this.enqueue(lastltem);
return firstItem;
} else if(this._storage.length === 1) {
return this._storage.pop();
} else {
console.warn('Attempt1ng to dequeue from an empty queue');
}
}
}
Note that in the constructor, we create only a single array. This Will be our stack.
The enqueue() function passes the items it receives into storage.
How dequeue() Works
This recursive method is the fun part. We’ll start by discussing the base cases. Lines 16 onward state that if the queue is empty, print a warning and do nothing. If there’s a single item, pop it off and return it.
For the cases where there is more than one item present in storage, we can look at lines 11 - 15.
Assume that our storage stack has values 1, 2, 3, in that order, present inside.
In the First Call
Once we hit line 12, lastItem is equal to 3 and our queue has had 3
removed:
[1, 2]
Since we know more items are present (since this is the case in which there were multiple items in storage), we recursively call the dequeue() method.
Entering the Second Call
We enter the function again. Length is now 2, so we enter the same case, lines 11 - 15. Again, we dequeue. In this Call, lastItem is equal to 2 . Our queue loses another value:
[1]
We again call the function.
Entering the Third Call
This time, there is only one item, 1 . We pop it off and return it, ending up back in the second call. Our queue is empty.
[]
Back to the Second Call
We go back to the 2nd call, now on line 14. lastItem is 2 and firstItem is 1.
On line 14, we enqueue lastItem, or 2.
[2]
We return 1 and go back to the first call.
Back to the First Call
We’re back at the beginning. 1astItem is 3 and firstItem İs 1. We enqueue 3:
[2, 3]
and return 1.
Dequeue Time
The time complexity of dequeue() is:
O(n)
because we need to pop and re-insert every item except one.
Dequeue Space
The space complexity of dequeue() is:
0(n)
because we need to call the func
tion one more time for every item.
Top comments (1)
There are still technically two stacks in this solution, the recursive call is just implicitly using the program stack as temporary storage. Not that there is anything wrong with the solution itself, but I'm not a fan of "trick" interview questions like this that have no practical value.