Interview Bootcamp
Vote

0% completed

​

Problem 2: Implement Stack using Queues

Problem Statement

Implement a stack using two queues. The stack should support standard operations like push (add an element to the top of the stack) and pop (remove an element from the top of the stack). Examples:

  1. Input: Push operations: [1, 2, 3], Pop operations: 2
    Output: [1]
    Explanation: After pushing 1, 2, 3 the stack looks like [1, 2, 3]. Then we perform 2 pop operations, removing 3 and 2, so the output is [1].

  2. Input: Push operations: [9, 8], Pop operations: 1
    Output: [9]

.....

.....

.....

Like the course? Get enrolled and start learning!
P

phuongvu089

· a year ago

The problem starter code made it seems like you can only use queue operations: put(), get(0, empty(), qsize().

Naman Jindal

Naman Jindal

· 2 years ago

The solution says that the time comp for the pop() operation is O(1). but Javascript implementation uses shift() which is O(n) in itself. Is there any way to handle this? or do we have no other choice?

J

Jimmy

· 3 years ago

In the pop() method, the solution should check to see if the queue is empty before popping to prevent queue underflow.

Show 1 reply
Rishi Jatia

Rishi Jatia

· 2 years ago

Why is it even necessary to swap queues? Won't the main queue always be empty? i just did a


main = aux;

aux = new LinkedList<Integer>();

and solution was accepted

Show 1 reply
Stan Solovyov

Stan Solovyov

· 5 months ago

To be honest, the answers is a bit confusing as in the original problem's code we have: from queue import Queue

Therefore it implies we should use Queue class rather than deque. In that case top() operation will be completely different as Queue class does not support access by index and top() implemetation is totally different. Please correct the initial problem description.