Stacks & Queues
LIFO vs FIFO, valid parentheses, monotonic stack, and the data structures behind DFS and BFS.
Questions in this quiz
10 questions on Stacks & Queues. Work through them here, then start the quiz to answer them and see your score.
1.What is the key difference between a stack and a queue?
- AStack is LIFO (last in, first out); Queue is FIFO (first in, first out)
- BStack is for numbers; Queue is for objects
- CBoth are FIFO — stack just processes from the opposite end
- DStack is FIFO; Queue is LIFO
2.DFS uses which data structure? BFS uses which?
- ABoth use a Stack
- BBoth use a Queue
- CDFS: Stack (or recursion call stack), BFS: Queue
- DDFS: Queue, BFS: Stack
3.What does this code return for s = "()[]{}"?
public boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') stack.push(c); else { if (stack.isEmpty()) return false; char top = stack.pop(); if (c == ')' && top != '(') return false; if (c == ']' && top != '[') return false; if (c == '}' && top != '{') return false; } } return stack.isEmpty(); }- Atrue
- Bfalse
- Cthrows NullPointerException
- Dnull
4.What is a monotonic stack and when is it used?
- AA stack limited to one data type
- BA stack maintained in increasing or decreasing order, used to find next/previous greater or smaller elements
- CA stack that automatically removes duplicates
- DA stack that can only hold values in ascending order, used for sorting
5.What is printed for nums = [2, 1, 2, 4, 3]?
int[] result = new int[nums.length]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) { result[stack.pop()] = nums[i]; } stack.push(i); } System.out.println(Arrays.toString(result));- A[4, 4, 4, 0, 0]
- B[4, 2, 4, 0, 0]
- C[0, 2, 4, 0, 0]
- D[2, 1, 4, 0, 3]
6.MinStack: support push(), pop(), top(), and getMin() all in O(1). What is the key insight?
- AStore the minimum at the bottom of the stack
- BMaintain a second "min stack" in parallel that always holds the current minimum at its top
- CUse a HashMap to store the minimum for each stack depth
- DSort the stack on every push
7.What is the amortised time complexity of dequeue when implementing a queue with two stacks?
- AO(1) always, never O(n)
- BO(1) amortised — each element moves from stack1 to stack2 at most once in its lifetime
- CO(log n)
- DO(n) worst case per dequeue
8.Level-order traversal visits a binary tree level by level. Which data structure makes this natural?
- AHashMap
- BPriorityQueue
- CStack
- DQueue
9.When would you use a Deque instead of a regular Queue?
- AOnly when you need FIFO ordering
- BWhen you need O(1) add/remove from BOTH ends — e.g., sliding window maximum
- CWhen you need sorted access to elements
- DWhen elements must be unique
10.Sliding window maximum across n elements with window size k using a monotonic deque — what is the time complexity?
- AO(k log n)
- BO(n × k)
- CO(n log n)
- DO(n)