In the previous chapter you learned what a stack is: a LIFO structure with push, pop and peek, all in O(1). You also saw one classic use, checking balanced brackets.
Now let's look at two families of problems where stacks really shine, and which appear again and again in university exams and placement interviews:
Expression conversion and evaluation: turning
A + B * Cinto postfix (A B C * +) or prefix (+ A * B C), and calculating the value of such expressions.Monotonic stacks: a pattern that answers questions like "what is the next greater element?" for every element of an array in
O(n)instead ofO(n²).
All code in this chapter uses ArrayDeque as the stack, as recommended in the Stack chapter.
Infix, Prefix and Postfix
The way we normally write expressions is called infix, because the operator sits in between its two operands:
A + BThere are two other notations:
Notation | Operator position |
|
|
|---|---|---|---|
Infix | Between operands |
|
|
Prefix (Polish notation) | Before operands |
|
|
Postfix (Reverse Polish notation) | After operands |
|
|
Why bother? Infix is easy for humans but hard for computers. To evaluate A + B * C, you must know that * happens before +, and parentheses can change everything.
Prefix and postfix need no parentheses and no precedence rules. The order of the symbols alone decides the order of the operations. That's why many calculators and expression evaluators first convert infix to postfix and then evaluate the postfix form. A stack does the work in both steps.
Precedence and Associativity
Before converting, we need two rules.
Precedence decides which operator binds tighter:
Operator | Precedence | Associativity |
|---|---|---|
| 3 (highest) | Right to left |
| 2 | Left to right |
| 1 (lowest) | Left to right |
Associativity decides the order when two operators have the same precedence:
A - B - C means (A - B) - C left to right
A ^ B ^ C means A ^ (B ^ C) right to leftFor example, 8 - 4 - 2 is (8 - 4) - 2 = 2, not 8 - (4 - 2) = 6. And 2 ^ 3 ^ 2 is 2 ^ 9 = 512, not 8 ^ 2 = 64. Getting associativity wrong is a very common way to lose marks in conversion questions.
Converting Infix to Postfix
The idea: operands go straight to the output. Operators wait on a stack until we know it's their turn.
The Rules
Scan the infix expression from left to right:
Operand (letter or digit): append it to the output.
(: push it.): pop operators to the output until you reach(. Pop and discard the(.Operator
op: while the top of the stack is an operator (not() and eitherit has higher precedence than
op, orit has equal precedence and
opis left-associative,
pop it to the output. Then push
op.End of input: pop all remaining operators to the output.
Rule 4 in plain words: before an operator goes on the stack, every operator already there that should be done first gets written out.
Step-by-Step Trace
Convert A + B * C - D / E:
Symbol | Action | Stack (bottom → top) | Output |
|---|---|---|---|
| Operand → output | empty |
|
| Stack empty → push |
|
|
| Operand → output |
|
|
|
|
|
|
| Operand → output |
|
|
| Pop |
|
|
| Operand → output |
|
|
|
|
|
|
| Operand → output |
|
|
end | Pop everything | empty |
|
Result: A B C * + D E / -
A Trace with Parentheses and Power
Convert (A + B) * C ^ D ^ E:
Symbol Stack Output
( (
A ( A
+ ( + A
B ( + A B
) (empty) A B + pop until '(' and discard it
* * A B +
C * A B + C
^ * ^ A B + C * is lower than ^, push
D * ^ A B + C D
^ * ^ ^ A B + C D equal precedence, but ^ is right-assoc: do NOT pop
E * ^ ^ A B + C D E
end (empty) A B + C D E ^ ^ *Because ^ is right-associative, the second ^ does not pop the first one. That's how C ^ D ^ E correctly becomes C D E ^ ^, meaning C ^ (D ^ E).
The Quick Exam Method: Full Parenthesization
For short written answers, you can check your result without a stack:
Add brackets around every operation, following precedence and associativity.
For postfix, move each operator to replace its closing bracket. For prefix, move it to replace its opening bracket.
Remove all brackets.
A + B * C - D / E
= ((A + (B * C)) - (D / E))
Postfix: A B C * + D E / -
Prefix: - + A * B C / D EIn exams, the stack trace table above is usually what earns the marks, so use this method only to double-check.
Converting Infix to Prefix
The standard trick reuses the postfix algorithm:
Reverse the infix expression, and swap every
(with).Run the postfix conversion on it, with one change to rule 4: for equal precedence, pop only if the incoming operator is right-associative (
^). For+ - * /, equal precedence does not pop.Reverse the result.
Why the change in step 2? Reversing the expression flips the direction of associativity. If we used the normal rule, A - B - C would come out as - A - B C, which means A - (B - C), a different value. With the modified rule we correctly get - - A B C, meaning (A - B) - C.
Trace for A + B * C - D / E. Reversed: E / D - C * B + A.
Symbol Stack Output
E E
/ / E
D / E D
- - E D / / is higher: pop it, then push -
C - E D / C
* - * E D / C
B - * E D / C B
+ - + E D / C B * * is higher: pop it; - is equal, + is left-assoc: keep it
A - + E D / C B * A
end E D / C B * A + -
Reverse: - + A * B C / D EThis matches the answer from full parenthesization.
Evaluating a Postfix Expression
Evaluation is where postfix pays off. The rule is very short. Scan from left to right:
Number: push it.
Operator: pop two values. The first popped is the right operand, the second popped is the left operand. Compute and push the result.
At the end, the stack holds exactly one value: the answer.
Evaluate 6 2 3 + - 3 8 2 / + *:
Token Action Stack (bottom → top)
6 push 6
2 push 6 2
3 push 6 2 3
+ 2 + 3 = 5 6 5
- 6 - 5 = 1 1
3 push 1 3
8 push 1 3 8
2 push 1 3 8 2
/ 8 / 2 = 4 1 3 4
+ 3 + 4 = 7 1 7
* 1 * 7 = 7 7
Answer: 7Look at the - step: the stack was 6 5, we popped 5 first (right operand) and 6 second (left operand), so we computed 6 - 5, not 5 - 6. For + and * the order doesn't matter, but for -, / and ^ it does.
In infix, this expression is (6 - (2 + 3)) * (3 + 8 / 2) = 1 * 7 = 7.
Evaluating a Prefix Expression
Prefix evaluation is the mirror image. Scan from right to left, push numbers, and when you see an operator, pop two values. This time the first popped is the left operand.
Evaluate - + 10 * 2 8 3:
Token Action Stack (bottom → top)
3 push 3
8 push 3 8
2 push 3 8 2
* 2 * 8 = 16 3 16
10 push 3 16 10
+ 10 + 16 = 26 3 26
- 26 - 3 = 23 23
Answer: 23In infix, this is (10 + 2 * 8) - 3 = 23.
Postfix evaluation | Prefix evaluation | |
|---|---|---|
Scan direction | Left to right | Right to left |
First value popped | Right operand | Left operand |
Second value popped | Left operand | Right operand |
Time / space |
|
|
Expression Conversion and Evaluation in Java
For conversion, operands are single letters or digits and spaces are not needed. For evaluation, tokens are separated by spaces so that numbers like 10 can have several digits.
import java.util.ArrayDeque;
import java.util.Deque;
class Main {
static int precedence(char op) {
switch (op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
default: return -1; // not an operator
}
}
static boolean isOperator(char c) {
return precedence(c) > 0;
}
static boolean isRightAssociative(char op) {
return op == '^';
}
static String infixToPostfix(String infix) {
StringBuilder out = new StringBuilder();
Deque<Character> stack = new ArrayDeque<>();
for (char c : infix.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
out.append(c); // operand: output directly
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (stack.peek() != '(') {
out.append(stack.pop()); // pop until '('
}
stack.pop(); // discard '('
} else if (isOperator(c)) {
while (!stack.isEmpty() && stack.peek() != '('
&& (precedence(stack.peek()) > precedence(c)
|| (precedence(stack.peek()) == precedence(c)
&& !isRightAssociative(c)))) {
out.append(stack.pop());
}
stack.push(c);
}
// spaces are ignored
}
while (!stack.isEmpty()) {
out.append(stack.pop());
}
return out.toString();
}
static String infixToPrefix(String infix) {
// 1. Reverse the expression and swap '(' with ')'
StringBuilder reversed = new StringBuilder();
for (int i = infix.length() - 1; i >= 0; i--) {
char c = infix.charAt(i);
if (c == '(') {
reversed.append(')');
} else if (c == ')') {
reversed.append('(');
} else {
reversed.append(c);
}
}
// 2. Convert to "postfix", popping equal precedence only for '^'
StringBuilder out = new StringBuilder();
Deque<Character> stack = new ArrayDeque<>();
for (char c : reversed.toString().toCharArray()) {
if (Character.isLetterOrDigit(c)) {
out.append(c);
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (stack.peek() != '(') {
out.append(stack.pop());
}
stack.pop();
} else if (isOperator(c)) {
while (!stack.isEmpty() && stack.peek() != '('
&& (precedence(stack.peek()) > precedence(c)
|| (precedence(stack.peek()) == precedence(c)
&& isRightAssociative(c)))) {
out.append(stack.pop());
}
stack.push(c);
}
}
while (!stack.isEmpty()) {
out.append(stack.pop());
}
// 3. Reverse the result
return out.reverse().toString();
}
static int apply(char op, int a, int b) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
case '^': return (int) Math.pow(a, b);
default: throw new IllegalArgumentException("Unknown operator " + op);
}
}
// Tokens are separated by spaces, so numbers can have many digits
static int evaluatePostfix(String postfix) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : postfix.trim().split("\\s+")) {
if (token.length() == 1 && isOperator(token.charAt(0))) {
int b = stack.pop(); // right operand comes out FIRST
int a = stack.pop(); // left operand
stack.push(apply(token.charAt(0), a, b));
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
static int evaluatePrefix(String prefix) {
Deque<Integer> stack = new ArrayDeque<>();
String[] tokens = prefix.trim().split("\\s+");
for (int i = tokens.length - 1; i >= 0; i--) { // scan right to left
String token = tokens[i];
if (token.length() == 1 && isOperator(token.charAt(0))) {
int a = stack.pop(); // left operand comes out FIRST
int b = stack.pop(); // right operand
stack.push(apply(token.charAt(0), a, b));
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
public static void main(String[] args) {
String[] expressions = {
"A+B*C",
"A+B*C-D/E",
"(A+B)*(C-D)",
"A-B-C",
"A^B^C",
"(A+B)*C^D^E",
"A*(B+C*D)+E"
};
for (String e : expressions) {
System.out.printf("%-14s postfix: %-12s prefix: %s%n",
e, infixToPostfix(e), infixToPrefix(e));
}
System.out.println(evaluatePostfix("6 2 3 + - 3 8 2 / + *"));
System.out.println(evaluatePostfix("10 2 8 * + 3 -"));
System.out.println(evaluatePrefix("- + 10 * 2 8 3"));
System.out.println(evaluatePrefix("* - 6 2 + 3 / 8 2"));
}
}Output:
A+B*C postfix: ABC*+ prefix: +A*BC
A+B*C-D/E postfix: ABC*+DE/- prefix: -+A*BC/DE
(A+B)*(C-D) postfix: AB+CD-* prefix: *+AB-CD
A-B-C postfix: AB-C- prefix: --ABC
A^B^C postfix: ABC^^ prefix: ^A^BC
(A+B)*C^D^E postfix: AB+CDE^^* prefix: *+AB^C^DE
A*(B+C*D)+E postfix: ABCD*+*E+ prefix: +*A+B*CDE
7
23
23
28Notes on this code:
The program assumes the input is a valid expression. A production version would check for things like an empty stack before
pop()and a missing(./is integer division in Java, so7 / 2gives3(it rounds towards zero).Every symbol is pushed and popped at most once, so conversion and evaluation both run in
O(n)time withO(n)space for the stack.
Monotonic Stack
Now for a very different use of stacks, one of the most valuable patterns for coding interviews.
Consider this problem:
For every element in an array, find the next greater element: the first element to its right that is larger. If there is none, use
-1.
arr = [4, 5, 2, 10, 8]
answer = [5, 10, 10, -1, -1]The brute-force solution checks every element to the right of each element, which is O(n²). A monotonic stack solves it in O(n).
A monotonic stack is a stack whose elements are always kept in sorted order (always increasing or always decreasing from bottom to top). Before pushing a new element, we pop every element that would break the order, and those pops are exactly where we find our answers.
The Key Insight
Think of people standing in a line, all looking to the right. A short person's view is blocked by the first taller person. Once someone taller arrives, every shorter person waiting behind them has found their answer, and they will never matter again.
So we keep a stack of elements that are still waiting for a greater element. When a new element arrives, it is the answer for every waiting element smaller than it. We pop those, record the answer, and push the new element.
The waiting elements always form a decreasing stack (from bottom to top), because any smaller element below a bigger one would already have been popped.
Step-by-Step Trace
arr = [4, 5, 2, 10, 8] (the stack stores indexes, shown here by their values):
i=0, value 4: stack empty, push stack: [4]
i=1, value 5: 4 < 5 → answer for 4 is 5, pop
push 5 stack: [5]
i=2, value 2: 5 < 2? no. push 2 stack: [5, 2]
i=3, value 10: 2 < 10 → answer for 2 is 10, pop
5 < 10 → answer for 5 is 10, pop
push 10 stack: [10]
i=4, value 8: 10 < 8? no. push 8 stack: [10, 8]
End: 10 and 8 never found a greater element → -1
Result: [5, 10, 10, -1, -1]We store indexes in the stack rather than values, so that we know which position in the result array to fill. Indexes also let us compute distances, as in the daily temperatures problem below.
Why Is It O(n)?
There is a while loop inside a for loop, so it looks like O(n²). But each index is pushed exactly once and popped at most once. Over the whole run, the inner loop can pop at most n times in total. So the total work is at most 2n stack operations:
Time: O(n) (amortized O(1) per element)
Space: O(n) (the stack, in the worst case, e.g. a decreasing array)This "count the total pushes and pops" argument is the standard way to explain monotonic stack complexity in an interview.
The Four Variations
By changing the comparison and the scan direction, the same pattern answers four related questions:
Question | Stack order (bottom → top) | Pop while | Answer is found |
|---|---|---|---|
Next greater element | Decreasing |
| For each popped element: current |
Next smaller element | Increasing |
| For each popped element: current |
Previous greater element | Decreasing |
| For current: the top after popping |
Previous smaller element | Increasing |
| For current: the top after popping |
A simple way to remember it: for a "next" question, answers are written when elements are popped. For a "previous" question, the answer is whatever is left on top after popping. Whether you use < or <= decides how equal values are treated, so read the problem statement carefully ("greater" vs "greater or equal").
For example, previous smaller element of [4, 5, 2, 10, 8]:
4: nothing on the left → -1 stack: [4]
5: top 4 < 5, keep it → 4 stack: [4, 5]
2: pop 5, pop 4, stack empty → -1 stack: [2]
10: top 2 < 10 → 2 stack: [2, 10]
8: pop 10, top 2 < 8 → 2 stack: [2, 8]
Result: [-1, 4, -1, 2, 2]Classic Monotonic Stack Problems
Daily Temperatures
Problem: Given daily temperatures, for each day find how many days you must wait for a warmer day (0 if never).
temps = [73, 74, 75, 71, 69, 72, 76, 73]
answer = [ 1, 1, 4, 2, 1, 1, 0, 0]This is "next greater element", except the answer is the distance i - day instead of the value. For day 2 (75), the next warmer day is day 6 (76), so the answer is 6 - 2 = 4.
Stock Span
Problem: The span of a stock's price today is the number of consecutive days, ending today, on which the price was less than or equal to today's price.
prices = [100, 80, 60, 70, 60, 75, 85]
span = [ 1, 1, 1, 2, 1, 4, 6]For day 5 (price 75), going back: 60, 70, 60 are all ≤ 75, then 80 is bigger. So the span is 4 (days 2, 3, 4 and 5).
This is a previous greater element problem: the span is i - (index of previous greater price), or i + 1 if there is no greater price before it.
Largest Rectangle in a Histogram
Problem: Bars of width 1 have the given heights. Find the area of the largest rectangle that fits inside the histogram.
heights = [2, 1, 5, 6, 2, 3]
6 | ###
5 | @@@ @@@
4 | @@@ @@@
3 | @@@ @@@ ###
2 | ### @@@ @@@ ### ###
1 | ### ### @@@ @@@ ### ###
+-------------------------
2 1 5 6 2 3
@ = largest rectangle: height 5, width 2 (bars 5 and 6) → area 10For each bar, the biggest rectangle that uses that bar as its shortest bar extends left until the previous smaller bar and right until the next smaller bar. A monotonic increasing stack finds both boundaries at once: when a bar is popped, the current index is its right boundary and the new top of the stack is its left boundary.
width = right - left - 1
area = height × widthWe add an extra height of 0 at the end so that every remaining bar gets popped and measured. Trace of the important pops:
i=4 (height 2) pops height 6: left = index 2, width = 4 - 2 - 1 = 1, area = 6
pops height 5: left = index 1, width = 4 - 1 - 1 = 2, area = 10 ← best
i=6 (height 0) pops height 3: area 3, height 2: width 4, area 8, height 1: width 6, area 6Monotonic Stack in Java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
class Main {
// For each element, the first greater element to its right (-1 if none)
static int[] nextGreater(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // indexes, values decreasing
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
result[stack.pop()] = arr[i]; // arr[i] is the answer for the popped index
}
stack.push(i);
}
return result;
}
// For each element, the nearest smaller element to its left (-1 if none)
static int[] previousSmaller(int[] arr) {
int n = arr.length;
int[] result = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // values increasing
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && stack.peek() >= arr[i]) {
stack.pop();
}
result[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(arr[i]);
}
return result;
}
// Days to wait for a warmer temperature (0 if never)
static int[] dailyTemperatures(int[] temps) {
int n = temps.length;
int[] wait = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // indexes of days still waiting
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
int day = stack.pop();
wait[day] = i - day;
}
stack.push(i);
}
return wait;
}
// Stock span: consecutive days up to today with price <= today's price
static int[] stockSpan(int[] prices) {
int n = prices.length;
int[] span = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // indexes, prices decreasing
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
stack.pop();
}
span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
return span;
}
// Largest rectangle in a histogram
static int largestRectangle(int[] heights) {
int n = heights.length;
int best = 0;
Deque<Integer> stack = new ArrayDeque<>(); // indexes, heights increasing
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i]; // height 0 at the end flushes the stack
while (!stack.isEmpty() && heights[stack.peek()] > h) {
int height = heights[stack.pop()];
int left = stack.isEmpty() ? -1 : stack.peek();
int width = i - left - 1;
best = Math.max(best, height * width);
}
stack.push(i);
}
return best;
}
public static void main(String[] args) {
int[] arr = {4, 5, 2, 10, 8};
System.out.println("Next greater: " + Arrays.toString(nextGreater(arr)));
System.out.println("Previous smaller: " + Arrays.toString(previousSmaller(arr)));
int[] temps = {73, 74, 75, 71, 69, 72, 76, 73};
System.out.println("Daily temps wait: " + Arrays.toString(dailyTemperatures(temps)));
int[] prices = {100, 80, 60, 70, 60, 75, 85};
System.out.println("Stock span: " + Arrays.toString(stockSpan(prices)));
int[] heights = {2, 1, 5, 6, 2, 3};
System.out.println("Largest rectangle: " + largestRectangle(heights));
}
}Output:
Next greater: [5, 10, 10, -1, -1]
Previous smaller: [-1, 4, -1, 2, 2]
Daily temps wait: [1, 1, 4, 2, 1, 1, 0, 0]
Stock span: [1, 1, 1, 2, 1, 4, 6]
Largest rectangle: 10All five functions run in O(n) time and O(n) space. In largestRectangle, the loop pushes the extra index n at the end; it is never read, so heights[n] is never accessed.
Complexity Summary
Problem | Brute force | With a stack | Extra space |
|---|---|---|---|
Infix to postfix / prefix | - |
|
|
Evaluate postfix / prefix | - |
|
|
Next / previous greater or smaller |
|
|
|
Daily temperatures |
|
|
|
Stock span |
|
|
|
Largest rectangle in histogram |
|
|
|
Common Mistakes
1. Popping operands in the wrong order
In postfix evaluation, the first value popped is the right operand. Writing a = pop(); b = pop(); push(a - b) computes 5 - 6 instead of 6 - 5. In prefix evaluation it is the other way round.
2. Treating ^ as left-associative
A ^ B ^ C is A B C ^ ^ in postfix, not A B ^ C ^. When the incoming operator is ^ and the top is also ^, do not pop.
3. Pushing ) onto the stack, or forgetting to discard (
Closing brackets are never pushed, and brackets never appear in postfix or prefix output.
4. Forgetting to empty the stack at the end
After the scan, operators may still be waiting on the stack. Pop all of them to the output.
5. Simply reversing the postfix to get prefix
Reversing A B C * + gives + * C B A, which is wrong (the operands are reversed too). Use the reverse, convert, reverse method, or full parenthesization.
6. Storing values when you need indexes
In monotonic stack problems that ask for distances or positions (daily temperatures, histogram), push indexes. You can always get the value with arr[index], but not the other way round.
7. Mixing up < and <= with duplicates
"Next greater" uses top < current to pop; using <= would treat an equal value as "greater". Test your code with an array that has repeated values, like [2, 2, 3].
Interview Tips
Recognise the monotonic stack pattern from words like "next greater", "next smaller", "previous", "nearest", "span", "how many days until", "how far can it see", or "largest rectangle".
Explain the O(n) argument clearly: every index is pushed once and popped at most once.
State what the stack contains before coding: "a decreasing stack of indexes still waiting for a greater element". Saying this out loud makes the comparisons obvious.
For circular arrays (Next Greater Element II), loop
ifrom0to2n - 1and usei % n, pushing indexes only during the first pass.For calculator problems (evaluate a string like
"3 + 2 * 2"), you can either convert to postfix and evaluate, or use two stacks at once, one for numbers and one for operators, applying the same precedence rules.In exam conversion questions, always draw the full table with columns for symbol, stack and output, and write the final answer separately.
Practice Problems
Evaluate Reverse Polish Notation
Basic Calculator II
Next Greater Element I
Next Greater Element II (circular array)
Daily Temperatures
Online Stock Span
Remove K Digits
Largest Rectangle in Histogram (hard)
Trapping Rain Water (hard, can be solved with a monotonic stack)
The Main Idea
Stacks are the natural tool whenever the most recent unfinished item must be handled first.
Infix → Postfix: operands to output, operators wait on a stack
pop higher (or equal, if left-assoc) before pushing
Evaluate postfix: push numbers; on an operator pop right, then left, push result
Evaluate prefix: scan right to left; pop left, then right
Monotonic stack: keep the stack sorted; every pop answers a question
each element pushed once, popped once → O(n)For expressions, a stack holds operators until their turn comes. For "next greater" style questions, a monotonic stack holds elements until their answer arrives. In both cases, each element enters and leaves the stack once, which is why these solutions are linear.