AI solution for JavaScript Coding Question on BFE.dev
108. Implement a Stack by using Queue
One possible solution is using two queues. Let's call them queue1
and queue2
. The idea is to use queue1
to store the elements of the stack, and queue2
as a temporary storage for the elements when we need to pop or peek the stack.
Initially, both queues are empty. Here's how we implement each method of the Stack
class:
class Stack { constructor() { this.queue1 = new Queue(); this.queue2 = new Queue(); } push(element) { this.queue1.enqueue(element); } peek() { // Move all elements from queue1 to queue2, except the last one. // The last one is the top element of the stack. while (this.queue1.size() > 1) { this.queue2.enqueue(this.queue1.dequeue()); } const top = this.queue1.peek(); // Get the last element of queue1 // Move all elements back to queue1 while (this.queue2.size() > 0) { this.queue1.enqueue(this.queue2.dequeue()); } return top; } pop() { // Move all elements from queue1 to queue2, except the last one. while (this.queue1.size() > 1) { this.queue2.enqueue(this.queue1.dequeue()); } const top = this.queue1.dequeue(); // Remove the last element of queue1 // Move all elements back to queue1 while (this.queue2.size() > 0) { this.queue1.enqueue(this.queue2.dequeue()); } return top; } size() { return this.queue1.size(); }}
Let's explain how each method works:
push()
: It simply enqueues the element to thequeue1
, which means pushing the element to the top of the stack.peek()
: It extracts the last element ofqueue1
, which is the top element of the stack, and returns it. To do that, it first moves all elements fromqueue1
toqueue2
, except the last one, which is saved in a variable calledtop
. Then it moves all elements back toqueue1
, so that the stacks remains unchanged.pop()
: It extracts the last element ofqueue1
, which is the top element of the stack, and removes it fromqueue1
. To do that, it follows the same procedure aspeek()
, but it also removes the last element fromqueue1
.size()
: It returns the size ofqueue1
, which is the size of the stack.
Note that this solution uses two queues, but always keeps only one of them with at most one element. Therefore, the time complexity of each method is O(n) in the worst case, where n is the size of the stack. However, in the typical case, the time complexity is O(1) for push() and size(), and O(2n) for pop() and peek(), which is still linear but much faster than a solution that copies all elements to a new array every time pop() or peek() is called.