Implement Stack using Queues
Easy · Stack & Strings · Stack · Design · Queue
Problem
Build a last-in, first-out (LIFO) stack using only queues internally. Implement the class MyStack:
- MyStack() creates an empty stack.
- push(x) puts x on top of the stack.
- pop() removes the top element and returns it.
- top() returns the top element without removing it.
- empty() returns True if the stack has no elements, and False otherwise.
Your queues may only use the standard queue operations: add to the back, look at or remove from the front, check the size, and check whether it is empty. The calls are given as ops (method names, the first being the constructor) and args (each call’s arguments); return every call’s result in order (None for calls that return nothing).
Examples
Input: ops = ["MyStack","push","push","push","top","pop","empty"], args = [[],[4],[8],[1],[],[],[]] Output: [None, None, None, None, 1, 1, False]
1 was pushed last, so it is on top and is the first to be popped; 4 and 8 remain.
Input: ops = ["MyStack","push","pop","empty"], args = [[],[3],[],[]] Output: [None, None, 3, True]
After popping its only element the stack is empty.
Input: ops = ["MyStack","push","push","pop","push","top","pop","pop","empty"], args = [[],[1],[2],[],[3],[],[],[],[]] Output: [None, None, None, 2, None, 3, 3, 1, True]
2 leaves first, then 3 (pushed later) is on top, then 1.
Constraints
- 1 <= x <= 9
- At most 100 calls are made to push, pop, top and empty
- Every call to pop and top is made on a non-empty stack
Approaches
- Two queues, move all but the last on pop — time push O(1), pop/top O(n), space O(n)
Follow-up
Can each operation be O(1) on average with queues only? No: a single queue gives no access to its back, so making the newest element reachable always costs moving the others. The rotation trick puts all of that cost on push and keeps pop and top O(1), which pays off when reads outnumber writes.
Related problems
Start free on Cariara · Coding problems · System design studio
