What this topic covers
15 subtopics- Monotonic stack7
- Queue operations5
- Applications4
- Design4
- Stack simulation4
- Balanced brackets3
- Deque3
- Stack operations3
- Basics2
- Circular queues2
- Expression conversion2
- Expression evaluation2
Show all 15 subtopics
- Stack permutations2
- Library stacks1
- Priority queues1
- Beginner 15
- Intermediate 15
- Advanced 15
About this topic
A stack is last-in-first-out: push and pop happen at the top. A queue is first-in-first-out: enqueue at the rear, dequeue at the front. Both are O(1) per operation, and both hide inside many algorithms – the call stack in recursion, the queue in breadth-first search. The pattern interviewers love most is the monotonic stack: keep the stack sorted, and every "next greater / previous smaller" question becomes a single O(n) pass.
Free preview
Sample questions
Try each one first, then open the answer for the explanation and why the other options are wrong.
Starting with an empty stack: push 1, push 2, push 3, pop, push 4, pop, push 5. What is in the stack, bottom to top?
- 1
- 2
- 3
- 4
- 5
- 1
- 5
- 5
- 2
- 1
- 1
- 2
- 5
Show answer and explanation
Explanation
Each pop removes the most recent push: 3 is popped, then 4. What remains is 1, 2 with 5 on top.
Why the other options are wrong
- ATwo elements were popped.
- BOnly 3 and 4 were popped.
- CThat is top to bottom.
What does this print?
def balanced(s):
pairs = {')': '(', ']': '[', '}': '{'}
st = []
for ch in s:
if ch in '([{':
st.append(ch)
elif not st or st.pop() != pairs[ch]:
return False
return not st
print(balanced("{[()()]}"), balanced("([)]"), balanced("(("))Show answer and explanation
Explanation
Each closing bracket must match the most recent unmatched opener – exactly what the stack top holds. In "([)]" the ) meets [ on top. "((" leaves unmatched openers, so the final not st is False.
Why the other options are wrong
- BIn "([)]" the brackets cross.
- CUnclosed openers remain in "((".
- D"{[()()]}" is properly nested.
Convert the infix expression a + b * c - d to postfix (usual precedence, left-to-right for equal precedence).
Show answer and explanation
Explanation
* binds tighter, so b c * is formed first and added to a; then d is subtracted from the result: ((a + (b * c)) − d). The shunting-yard algorithm pops operators of higher or equal precedence before pushing a new one.
Why the other options are wrong
- BThat is a + (b * (c − d)).
- CThat is prefix-like, not postfix.
- DThat is ((a + b) * c) − d.
The array gives bar heights of a histogram (each bar has width 1). What is the area of the largest rectangle?
- 02
- 11
- 25
- 36
- 42
- 53
The answer is a number – work it out, then open the solution.
Show answer and explanation
Explanation
Bars 5 and 6 together give height 5 × width 2 = 10. With an increasing stack, each bar learns where it stops extending on the left and right when it is popped: O(n).