Stack interview questions with worked solutions
Last updated 2026-11-19
A stack gives you last-in, first-out access: the most recent unresolved thing is always on top. That makes it the natural tool for anything nested or reversible, such as matching brackets, evaluating expressions, undoing operations and collapsing adjacent items that cancel out.
The problems below run from simple matching to expression parsing. Look for a stack whenever the answer to the current element depends on the most recent unmatched earlier one. When the question is "next greater" or "nearest smaller", the stack stays sorted and the technique has its own page: monotonic stack questions. Test-day tactics are in the DSA coding round guide.
| Questions | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Core idea | Last in, first out for nested or cancelling structure |
Signals that point to a stack
Phrases such as "matching", "balanced", "nested", "undo", "evaluate", "most recent" or "collapse adjacent" almost always mean a stack. If you find yourself scanning backwards for the last open item, you are describing a stack.
In Python a list is a fine stack (append and pop). In Java prefer ArrayDeque over the legacy Stack class: it is faster and has the same push, pop and peek operations.
- Matching pairs: push openers, pop on closers.
- Expression evaluation: one stack for operands, sometimes one for operators.
- Cancelling neighbours: compare with the top before pushing.
- Storing state: push the previous result when entering a bracket.
What goes wrong
Popping from an empty stack is the usual bug, so test inputs such as a lone closing bracket. At the end, a non-empty stack usually means an unmatched opener and should change the answer. Integer division in calculators must truncate toward zero, which differs between Python and Java for negatives.
Stack interview questions with worked solutions: questions with worked answers
1 Valid parentheses: are brackets of three kinds correctly nested?
easyPush each opening bracket. On a closing bracket, the stack must be non-empty and the top must be its matching opener; pop it. At the end the stack must be empty, otherwise some opener never closed. Time O(n), space O(n).. Edge cases: empty string (valid), a lone closer, an opener left over, interleaved types such as "([)]".
pythondef is_valid(s): st = [] pair = {')': '(', ']': '[', '}': '{'} for ch in s: if ch in pair: if not st or st.pop() != pair[ch]: return False else: st.append(ch) return not stjavaimport java.util.*; class Solution { static boolean isValid(String s) { Deque<Character> st = new ArrayDeque<>(); for (char ch : s.toCharArray()) { if (ch == '(' || ch == '[' || ch == '{') st.push(ch); else { if (st.isEmpty()) return false; char open = st.pop(); if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) return false; } } return st.isEmpty(); } }2 Remove all adjacent duplicate characters repeatedly, such as "abbaca" to "ca".
easyScan once with a stack of kept characters. If the new character equals the top, pop the top (the pair cancels); otherwise push it. Cancellations can chain, for example "abba", and the stack handles that without restarting. Time O(n), space O(n).. Edge cases: empty string, all characters cancelling, no adjacent equal pair.
pythondef remove_duplicates(s): st = [] for ch in s: if st and st[-1] == ch: st.pop() else: st.append(ch) return "".join(st)javaimport java.util.*; class Solution { static String removeDuplicates(String s) { StringBuilder st = new StringBuilder(); for (char ch : s.toCharArray()) { int n = st.length(); if (n > 0 && st.charAt(n - 1) == ch) st.deleteCharAt(n - 1); else st.append(ch); } return st.toString(); } }3 Implement a queue using two stacks.
easyPush onto an input stack. For pop or peek, if the output stack is empty, move every element from input to output, which reverses their order so the oldest is on top. Each element moves at most once, so operations are amortised O(1). Time amortised O(1) per operation, space O(n).. Edge cases: pop on an empty queue, interleaving pushes and pops, peek after a transfer.
pythonclass MyQueue: def __init__(self): self.inp, self.out = [], [] def push(self, x): self.inp.append(x) def _move(self): if not self.out: while self.inp: self.out.append(self.inp.pop()) def pop(self): self._move() return self.out.pop() def peek(self): self._move() return self.out[-1] def empty(self): return not self.inp and not self.outjavaimport java.util.*; class MyQueue { private final Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>(); void push(int x) { in.push(x); } private void move() { if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); } int pop() { move(); return out.pop(); } int peek() { move(); return out.peek(); } boolean empty() { return in.isEmpty() && out.isEmpty(); } }4 Min stack: push, pop, top and getMin all in O(1).
mediumStore each value together with the minimum so far. On push, the new minimum is the smaller of the value and the previous top's minimum. Pop discards both together, so the minimum is always correct for the current contents without any search. Time O(1) per operation, space O(n).. Edge cases: getMin right after a pop, duplicates of the minimum, negative numbers.
pythonclass MinStack: def __init__(self): self.st = [] def push(self, x): m = min(x, self.st[-1][1]) if self.st else x self.st.append((x, m)) def pop(self): self.st.pop() def top(self): return self.st[-1][0] def get_min(self): return self.st[-1][1]javaimport java.util.*; class MinStack { private final Deque<int[]> st = new ArrayDeque<>(); void push(int x) { int m = st.isEmpty() ? x : Math.min(x, st.peek()[1]); st.push(new int[]{x, m}); } void pop() { st.pop(); } int top() { return st.peek()[0]; } int getMin() { return st.peek()[1]; } }5 Evaluate a Reverse Polish Notation expression.
mediumScan the tokens. Numbers are pushed. For an operator, pop the right operand first, then the left, apply the operator and push the result. Division truncates toward zero, so in Python avoid floor division on negatives. The answer is the single value left on the stack. Time O(n), space O(n).. Edge cases: negative numbers (a token like "-3" is a number, not an operator), division of a negative value, single token.
pythondef eval_rpn(tokens): st = [] for t in tokens: if t in ("+", "-", "*", "/"): b, a = st.pop(), st.pop() if t == "+": st.append(a + b) elif t == "-": st.append(a - b) elif t == "*": st.append(a * b) else: st.append(int(a / b)) else: st.append(int(t)) return st[0]javaimport java.util.*; class Solution { static int evalRPN(String[] tokens) { Deque<Integer> st = new ArrayDeque<>(); for (String t : tokens) { switch (t) { case "+": st.push(st.pop() + st.pop()); break; case "*": st.push(st.pop() * st.pop()); break; case "-": { int b = st.pop(), a = st.pop(); st.push(a - b); break; } case "/": { int b = st.pop(), a = st.pop(); st.push(a / b); break; } default: st.push(Integer.parseInt(t)); } } return st.pop(); } }6 Simplify a Unix file path (handle ".", ".." and repeated slashes).
mediumSplit on "/". Ignore empty parts and ".". For "..", pop the stack if it is not empty (going above the root stays at the root). Otherwise push the name. Join the stack with "/" and prefix a leading "/". Time O(n), space O(n).. Edge cases: "/../" gives "/", "//a///b/", a trailing slash, names that merely contain dots such as "...".
pythondef simplify_path(path): st = [] for p in path.split("/"): if p in ("", "."): continue if p == "..": if st: st.pop() else: st.append(p) return "/" + "/".join(st)javaimport java.util.*; class Solution { static String simplifyPath(String path) { Deque<String> st = new ArrayDeque<>(); for (String p : path.split("/")) { if (p.isEmpty() || p.equals(".")) continue; if (p.equals("..")) { if (!st.isEmpty()) st.pop(); } else st.push(p); } if (st.isEmpty()) return "/"; StringBuilder sb = new StringBuilder(); Iterator<String> it = st.descendingIterator(); while (it.hasNext()) sb.append('/').append(it.next()); return sb.toString(); } }7 Asteroid collision: positive moves right, negative moves left; the smaller explodes.
mediumKeep a stack of survivors. A new negative asteroid collides only while the top is positive. If the top is smaller, pop it and continue; if equal, pop it and the new one dies too; if larger, the new one dies. Anything that survives is pushed. Negatives pushed on an empty stack or atop negatives never collide. Time O(n), space O(n).. Edge cases: equal sizes destroying each other, all moving the same way, a big negative clearing many positives.
pythondef asteroid_collision(a): st = [] for x in a: alive = True while alive and x < 0 and st and st[-1] > 0: if st[-1] < -x: st.pop() elif st[-1] == -x: st.pop() alive = False else: alive = False if alive: st.append(x) return stjavaimport java.util.*; class Solution { static int[] asteroidCollision(int[] a) { int[] st = new int[a.length]; int top = 0; for (int x : a) { boolean alive = true; while (alive && x < 0 && top > 0 && st[top - 1] > 0) { if (st[top - 1] < -x) top--; else if (st[top - 1] == -x) { top--; alive = false; } else alive = false; } if (alive) st[top++] = x; } return Arrays.copyOf(st, top); } }8 Basic calculator II: evaluate + - * / on non-negative integers, no brackets.
mediumRead numbers and remember the operator that came before each number. When the number ends, apply that operator: plus pushes the number, minus pushes its negative, times and divide combine with the stack top immediately because they bind tighter. The answer is the sum of the stack. For "3+2*2" the stack is 3, then 4, sum 7. Time O(n), space O(n).. Edge cases: spaces, a trailing number with no operator after it, division truncating toward zero.
pythondef calculate_ii(s): st, num, op = [], 0, '+' for i, ch in enumerate(s): if ch.isdigit(): num = num * 10 + int(ch) if (not ch.isdigit() and ch != ' ') or i == len(s) - 1: if op == '+': st.append(num) elif op == '-': st.append(-num) elif op == '*': st.append(st.pop() * num) else: st.append(int(st.pop() / num)) op, num = ch, 0 return sum(st)javaimport java.util.*; class Solution { static int calculateII(String s) { Deque<Integer> st = new ArrayDeque<>(); int num = 0; char op = '+'; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (Character.isDigit(c)) num = num * 10 + (c - '0'); if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) { if (op == '+') st.push(num); else if (op == '-') st.push(-num); else if (op == '*') st.push(st.pop() * num); else st.push(st.pop() / num); op = c; num = 0; } } int sum = 0; for (int v : st) sum += v; return sum; } }9 Longest valid parentheses substring.
hardKeep a stack of indices, seeded with -1 as a base. For "(", push its index. For ")", pop; if the stack is now empty, push this index as the new base, otherwise the valid length ending here is i minus the new top. The base index marks where the last unmatched ")" was. Time O(n), space O(n).. Edge cases: empty string (0), all closers, nested and adjacent valid groups such as "(()())".
pythondef longest_valid_parentheses(s): st, best = [-1], 0 for i, ch in enumerate(s): if ch == '(': st.append(i) else: st.pop() if not st: st.append(i) else: best = max(best, i - st[-1]) return bestjavaimport java.util.*; class Solution { static int longestValidParentheses(String s) { Deque<Integer> st = new ArrayDeque<>(); st.push(-1); int best = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') st.push(i); else { st.pop(); if (st.isEmpty()) st.push(i); else best = Math.max(best, i - st.peek()); } } return best; } }10 Basic calculator: evaluate + and - with nested brackets and unary minus.
hardTrack the running result and the current sign. On "(", push the result and sign onto the stack, then reset. On ")", finish the number, multiply the bracket result by the popped sign and add the popped result. For "1-(2+3)" you get 1 - 5 = -4. Keeping sign as 1 or -1 handles subtraction without a second stack of operators. Time O(n), space O(depth of brackets).. Edge cases: spaces, a number directly after "(", nested brackets, a leading unary minus such as "-(2+3)".
pythondef calculate_parens(s): st, res, sign, num = [], 0, 1, 0 for ch in s: if ch.isdigit(): num = num * 10 + int(ch) elif ch in '+-': res += sign * num num = 0 sign = 1 if ch == '+' else -1 elif ch == '(': st.append(res) st.append(sign) res, sign = 0, 1 elif ch == ')': res += sign * num num = 0 res *= st.pop() res += st.pop() return res + sign * numjavaimport java.util.*; class Solution { static int calculateParens(String s) { Deque<Integer> st = new ArrayDeque<>(); int res = 0, sign = 1, num = 0; for (char ch : s.toCharArray()) { if (Character.isDigit(ch)) num = num * 10 + (ch - '0'); else if (ch == '+' || ch == '-') { res += sign * num; num = 0; sign = ch == '+' ? 1 : -1; } else if (ch == '(') { st.push(res); st.push(sign); res = 0; sign = 1; } else if (ch == ')') { res += sign * num; num = 0; res *= st.pop(); res += st.pop(); } } return res + sign * num; } }11 How would you report where brackets go wrong, instead of only returning false?
hardInstead of storing characters, store indices of openers. At the end any indices left on the stack are exactly the unmatched openers, and a failed pop on a closer gives the position of an unmatched closer. This turns a yes or no answer into an error report, which is how editors highlight bracket errors.
Frequently asked questions
When should I use a stack versus recursion?
They are equivalent: recursion uses the call stack implicitly. Use an explicit stack when depth could overflow the call stack, or when you need to control the order of processing.
Should I use Stack or ArrayDeque in Java?
Use ArrayDeque. The legacy Stack class extends Vector, so every call is synchronised and it exposes list methods that break stack discipline.
What is the stack version of "undo"?
Push each operation, pop to undo. Editors do exactly this, often with a second stack for redo.
How is a monotonic stack different?
It keeps its elements in sorted order by popping smaller or larger ones before each push, which answers next-greater and nearest-smaller questions in linear time. See monotonic stack questions.
What other topics reuse the stack?
Depth-first search, backtracking and expression parsing. See recursion questions and queue and deque questions.
Related guides
- Monotonic stack interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- String interview questions with worked solutions
- Linked list interview questions with worked solutions
- Backtracking interview questions with worked solutions
More in DSA Interview Questions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions