Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Implement Stack using Queues

Problem Statement

Implement a stack using only two queues. The stack should behave like a typical last-in-first-out (LIFO) stack, meaning that the last element added should be the first one to be removed.

Implement a Solution class that supports the following operations:

  • Solution(): A constructor to initialize the object.
  • push(int x): Adds an element x to the top of the stack.
  • pop(): Removes the element from the top of the stack and returns it.
  • top(): Retrieves the element on the top of the stack without removing it.
  • `empty()

.....

.....

.....

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

· 2 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

· 4 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.