Chapter 13

Stacks in Java
Java Data Structures & Algorithms Series

A Stack is a Last-In-First-Out (LIFO) data structure — the last element pushed is the first one popped. It
is the underlying mechanism behind function call management, expression evaluation, undo
operations, and monotonic sequences.

1 Stack in Java — Three Ways

// Way 1: [Link] (legacy, synchronized — avoid in interviews)

Stack<Integer> stack = new Stack<>();
[Link](1); // add to top
[Link](); // remove & return top
[Link](); // view top without removing
[Link](); // check if empty
[Link](); // number of elements

// Way 2: Deque as Stack (PREFERRED — faster, more flexible)

Deque<Integer> stack = new ArrayDeque<>();
[Link](1); // addFirst — O(1)
[Link](); // removeFirst — O(1)
[Link](); // peekFirst — O(1)

// Way 3: LinkedList as Stack

Deque<Integer> stack = new LinkedList<>();
// Same API as ArrayDeque

// In interviews: always use ArrayDeque for stacks

2 Pattern 1 — Valid Parentheses

Check if brackets are balanced — ()[]{}.

"()[]{}" → true
"([)]" → false
"{[]}" → true
 public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = [Link](')', '(', ']', '[', '}', '{');

for (char c : [Link]()) {

if () {
[Link](c); // opening bracket → push
} else {
// Closing bracket — check if matches top
if ([Link]() || [Link]() != [Link](c))
return false;
[Link]();
}
}
return [Link](); // stack must be empty at end
}

Time: O(n) | Space: O(n)

// Trace: "{[]}"
// '{' → push → stack: ['{']
// '[' → push → stack: ['{','[']
// ']' → pairs[']']='[', top='[' ✓ → pop → stack: ['{']
// '}' → pairs['}']='{', top='{' ✓ → pop → stack: []
// return true ✅

3 Pattern 2 — Monotonic Stack

A stack that maintains elements in sorted order (increasing or decreasing). Used for “next greater/smaller
element” problems.

⭐ Core Idea: Maintain a decreasing stack. When a new element is larger than the top, that
new element IS the “next greater” for the top. Pop and record it.

🔑 Next Greater Element I

public static int[] nextGreaterElement(int[] nums1, int[] nums2) {

// Precompute next greater for every element in nums2
Map<Integer, Integer> nextGreater = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>(); // monotonic decreasing stack

for (int num : nums2) {

 // Current num is greater than stack top → it's the next greater!
while (![Link]() && [Link]() < num)
[Link]([Link](), num);
[Link](num);
}

// Remaining elements in stack have no next greater

while (![Link]()) [Link]([Link](), -1);

// Answer queries for nums1

int[] result = new int[[Link]];
for (int i = 0; i < [Link]; i++)
result[i] = [Link](nums1[i], -1);

return result;
}
// Time: O(m+n) | Space: O(n)

🔑 Next Greater Element II (Circular Array)

public static int[] nextGreaterII(int[] nums) {

int n = [Link];
int[] result = new int[n];
[Link](result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // stores indices

// Traverse twice to simulate circular array

for (int i = 0; i < 2 * n; i++) {
int num = nums[i % n];
while (![Link]() && nums[[Link]()] < num)
result[[Link]()] = num;
if (i < n) [Link](i); // only push in first traversal
}
return result;
}
// Time: O(n) | Space: O(n)

4 Pattern 3 — Largest Rectangle in Histogram

public static int largestRectangleArea(int[] heights) {

Deque<Integer> stack = new ArrayDeque<>(); // stores indices
int maxArea = 0;
int n = [Link];
 for (int i = 0; i <= n; i++) {
int currHeight = (i == n) ? 0 : heights[i]; // sentinel 0 at end

while (![Link]() && heights[[Link]()] > currHeight) {

int height = heights[[Link]()];
int width = [Link]() ? i : i - [Link]() - 1;
maxArea = [Link](maxArea, height * width);
}
[Link](i);
}
return maxArea;
}
// Time: O(n) | Space: O(n)

// Trace: [2,1,5,6,2,3]
// i=0: push 0 → stack:[0]
// i=1: h=1 < h[0]=2 → pop 0: area=2×1=2, push 1 → stack:[1]
// i=2: push 2 → stack:[1,2]
// i=3: push 3 → stack:[1,2,3]
// i=4: h=2 < h[3]=6 → pop 3: area=6×1=6
// h=2 < h[2]=5 → pop 2: area=5×2=10 ← max!
// push 4 → stack:[1,4]
// i=5: push 5 → stack:[1,4,5]
// i=6: h=0 → pop 5: area=3×1=3, pop 4: area=2×3=6, pop 1: area=1×6=6
// Answer: 10 ✅

5 Pattern 4 — Min Stack (O(1) Minimum)

Design a stack that retrieves minimum in O(1).

Approach 1: Auxiliary Min Stack

class MinStack {
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> minStack = new ArrayDeque<>(); // tracks minimums

public void push(int val) {

[Link](val);
// Push to minStack if empty or val ≤ current minimum
if ([Link]() || val <= [Link]())
[Link](val);
}
 public void pop() {
int val = [Link]();
if (val == [Link]()) [Link](); // remove from minStack
too
}

public int top() { return [Link](); }

public int getMin() { return [Link](); } // O(1)!
}
// All operations: O(1) | Space: O(n)

Approach 2: Store (value, currentMin) pairs

class MinStack2 {
Deque<int[]> stack = new ArrayDeque<>(); // [value, minSoFar]

public void push(int val) {

int min = [Link]() ? val : [Link](val, [Link]()[1]);
[Link](new int[]{val, min});
}
public void pop() { [Link](); }
public int top() { return [Link]()[0]; }
public int getMin() { return [Link]()[1]; }
}

6 Pattern 5 — Daily Temperatures

Find how many days until a warmer temperature.

temps = [73, 74, 75, 71, 69, 72, 76, 73]

Answer = [ 1, 1, 4, 2, 1, 1, 0, 0]

public static int[] dailyTemperatures(int[] temps) {

int n = [Link];
int[] result = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // stores indices

for (int i = 0; i < n; i++) {

// Current temp is warmer than stack top
while (![Link]() && temps[[Link]()] < temps[i]) {
int idx = [Link]();
 result[idx] = i - idx; // days to wait
}
[Link](i);
}
return result; // remaining indices stay 0 (no warmer day)
}

Time: O(n) | Space: O(n)

7 Pattern 6 — Expression Evaluation

🔑 Basic Calculator (+ and − only, with parentheses)

public static int calculate(String s) {

Deque<Integer> stack = new ArrayDeque<>();
int result = 0, num = 0, sign = 1;

for (int i = 0; i < [Link](); i++) {

char c = [Link](i);

if ([Link](c)) {
num = num * 10 + (c - '0'); // build multi-digit number

} else if (c == '+') {
result += sign * num;
num = 0; sign = 1;

} else if (c == '-') {
result += sign * num;
num = 0; sign = -1;

} else if (c == '(') {
// Push current result and sign onto stack
[Link](result);
[Link](sign);
result = 0; sign = 1; // reset for sub-expression

} else if (c == ')') {
result += sign * num;
num = 0;
result *= [Link](); // multiply by sign before '('
result += [Link](); // add result before '('
}
}
 return result + sign * num;
}
// Time: O(n) | Space: O(n)
// "1 + (2 - (3 + 4))" → 1+(2-7) → 1+(-5) → -4

🔑 Evaluate Reverse Polish Notation

public static int evalRPN(String[] tokens) {

Deque<Integer> stack = new ArrayDeque<>();

for (String token : tokens) {

switch (token) {
case "+" -> { int b = [Link](); [Link]([Link]() + b); }
case "-" -> { int b = [Link](); [Link]([Link]() - b); }
case "*" -> { int b = [Link](); [Link]([Link]() * b); }
case "/" -> { int b = [Link](); [Link]([Link]() / b); }
default -> [Link]([Link](token));
}
}
return [Link]();
}
// ["2","1","+","3","*"] → (2+1)*3 = 9
// Time: O(n) | Space: O(n)

8 Pattern 7 — Decode String

Decode encoded string k[encoded_string].

"3[a]2[bc]" → "aaabcbc"
"3[a2[c]]" → "accaccacc"
"2[abc]3[cd]ef" → "abcabccdcdcdef"

public static String decodeString(String s) {

Deque<Integer> countStack = new ArrayDeque<>();
Deque<StringBuilder> strStack = new ArrayDeque<>();
StringBuilder current = new StringBuilder();
int k = 0;

for (char c : [Link]()) {

if ([Link](c)) {
k = k * 10 + (c - '0'); // build multi-digit number
 } else if (c == '[') {
[Link](k); // save repeat count
[Link](current); // save current string
current = new StringBuilder(); // start fresh
k = 0;

} else if (c == ']') {
int repeat = [Link]();
StringBuilder decoded = [Link]();
for (int i = 0; i < repeat; i++) [Link](current);
current = decoded; // restore with repetition added

} else {
[Link](c);
}
}
return [Link]();
}
// Time: O(max_k × n) | Space: O(n)

9 Pattern 8 — Remove K Digits (Monotonic Stack)

Remove K digits to make the smallest possible number.

// num="1432219", k=3
// Remove 4,3,2 → "1219"

Clean Version using StringBuilder as Stack

public static String removeKdigitsClean(String num, int k) {

StringBuilder sb = new StringBuilder();
for (char c : [Link]()) {
while (k > 0 && [Link]() > 0 && [Link]([Link]()-1) > c) {
[Link]([Link]()-1);
k--;
}
[Link](c);
}
// Remove remaining k digits from end
[Link]([Link]()-k, [Link]());
// Remove leading zeros
int start = 0;
while (start < [Link]()-1 && [Link](start)=='0') start++;
 return [Link](start);
}
// Time: O(n) | Space: O(n)

10 Pattern 9 — Stack-Based DFS Simulation

public static void dfsIterative(int[][] adj, int start, int V) {

boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
[Link](start);

while (![Link]()) {
int node = [Link]();
if (visited[node]) continue;
visited[node] = true;
[Link](node + " ");

// Push neighbors (reverse order for left-to-right DFS)

for (int i = adj[node].length - 1; i >= 0; i--)
if (!visited[adj[node][i]]) [Link](adj[node][i]);
}
}

11 Design — Implement Queue Using Two Stacks

💡 Amortized O(1): Each element is pushed to inbox once and moved to outbox once. Total
work per element = O(1) amortized, even though individual operations may be O(n).

class MyQueue {
Deque<Integer> inbox = new ArrayDeque<>(); // for push
Deque<Integer> outbox = new ArrayDeque<>(); // for pop/peek

public void push(int x) {

[Link](x);
}

public int pop() {

move();
return [Link]();
}

public int peek() {

 move();
return [Link]();
}

public boolean empty() {

return [Link]() && [Link]();
}

private void move() {

// Only transfer when outbox is empty — amortized O(1)
if ([Link]())
while (![Link]()) [Link]([Link]());
}
}
// push: O(1), pop/peek: O(1) amortized | Space: O(n)

12 Stack Patterns Quick Reference

Problem Type Stack Type Key Idea

Balanced brackets Regular stack Push open, match close

Next greater element Monotonic decreasing Pop when current > top

Next smaller element Monotonic increasing Pop when current < top

Histogram rectangle Monotonic increasing Pop when shorter bar found

Min stack Auxiliary min stack Track min alongside values

Expression eval Regular stack Numbers + operators

Decode string Two stacks Count stack + string stack

13 Full Runnable Java Program

import [Link].*;

public class Chapter13Stacks {

public static void main(String[] args) {

// Valid Parentheses
[Link]("Valid '()[]{}':"+isValid("()[]{}")); // true
[Link]("Valid '([)]': " +isValid("([)]")); // false

// Next Greater Element

[Link]("Next Greater: " + [Link](
 nextGreaterElement(new int[]{4,1,2}, new int[]{1,3,4,2}))); // [-
1,3,-1]

// Largest Rectangle
[Link]("Largest Rect: " +
largestRectangleArea(new int[]{2,1,5,6,2,3})); // 10

// Daily Temperatures
[Link]("Daily Temps: " + [Link](
dailyTemperatures(new int[]{73,74,75,71,69,72,76,73})));

// Min Stack
MinStack2 ms = new MinStack2();
[Link](-2); [Link](0); [Link](-3);
[Link]("Min: " + [Link]()); // -3
[Link]();
[Link]("Top: " + [Link]()); // 0
[Link]("Min: " + [Link]()); // -2

// Calculate
[Link]("Calc '1+(4+5+2)-3': " + calculate("1+(4+5+2)-3"));
// 9

// Eval RPN
[Link]("RPN [2,1,+,3,*]: " +
evalRPN(new String[]{"2","1","+","3","*"})); // 9

// Decode String
[Link]("Decode '3[a2[c]]': " +
decodeString("3[a2[c]]")); // accaccacc

// Remove K Digits
[Link]("Remove 3 from '1432219': " +
removeKdigitsClean("1432219", 3)); // 1219

// Queue using 2 stacks

MyQueue q = new MyQueue();
[Link](1); [Link](2);
[Link]("Queue peek: " + [Link]()); // 1
[Link]("Queue pop: " + [Link]()); // 1
}

static boolean isValid(String s) {

Deque<Character> st = new ArrayDeque<>();
Map<Character,Character> p = [Link](')', '(', ']','[','}','{');
for (char c : [Link]()) {
if () [Link](c);
else { if ([Link]()||[Link]()!=[Link](c)) return false;
[Link](); }
}
return [Link]();
}

static int[] nextGreaterElement(int[] nums1, int[] nums2) {

Map<Integer,Integer> map = new HashMap<>();
Deque<Integer> st = new ArrayDeque<>();
for (int n : nums2) {
while (![Link]()&&[Link]()<n) [Link]([Link](),n);
[Link](n);
}
while (![Link]()) [Link]([Link](),-1);
int[] res = new int[[Link]];
for (int i = 0; i < [Link]; i++) res[i] =
[Link](nums1[i],-1);
return res;
}

static int largestRectangleArea(int[] h) {

Deque<Integer> st = new ArrayDeque<>(); int max = 0, n = [Link];
for (int i = 0; i <= n; i++) {
int ch = i == n ? 0 : h[i];
while (![Link]()&&h[[Link]()]>ch) {
int ht = h[[Link]()];
int w = [Link]() ? i : i - [Link]() - 1;
max = [Link](max, ht*w);
}
[Link](i);
}
return max;
}

static int[] dailyTemperatures(int[] t) {

int n = [Link]; int[] res = new int[n];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (![Link]()&&t[[Link]()]<t[i]) { int idx=[Link]();
res[idx]=i-idx; }
[Link](i);
}
return res;
}

static int calculate(String s) {

Deque<Integer> st = new ArrayDeque<>(); int res=0,num=0,sign=1;
for (char c : [Link]()) {
if ([Link](c)) num=num*10+(c-'0');
 else if (c=='+'){res+=sign*num;num=0;sign=1;}
else if (c=='-'){res+=sign*num;num=0;sign=-1;}
else if (c=='('){[Link](res);[Link](sign);res=0;sign=1;}
else if (c==')'){res+=sign*num;num=0;res*=[Link]();res+=[Link]();}
}
return res+sign*num;
}

static int evalRPN(String[] tokens) {

Deque<Integer> st = new ArrayDeque<>();
for (String t : tokens) {
if ([Link]("+")){int b=[Link]();[Link]([Link]()+b);}
else if([Link]("-")){int b=[Link]();[Link]([Link]()-b);}
else if([Link]("*")){int b=[Link]();[Link]([Link]()*b);}
else if([Link]("/")){int b=[Link]();[Link]([Link]()/b);}
else [Link]([Link](t));
}
return [Link]();
}

static String decodeString(String s) {

Deque<Integer> cs = new ArrayDeque<>();
Deque<StringBuilder> ss = new ArrayDeque<>();
StringBuilder cur = new StringBuilder(); int k = 0;
for (char c : [Link]()) {
if ([Link](c)) k=k*10+(c-'0');
else if (c=='['){[Link](k);[Link](cur);cur=new
StringBuilder();k=0;}
else if (c==']'){int r=[Link]();StringBuilder d=[Link]();for(int
i=0;i<r;i++)[Link](cur);cur=d;}
else [Link](c);
}
return [Link]();
}

static String removeKdigitsClean(String num, int k) {

StringBuilder sb = new StringBuilder();
for (char c : [Link]()) {
while (k>0&&[Link]()>0&&[Link]([Link]()-1)>c) {
[Link]([Link]()-1); k--;
}
[Link](c);
}
[Link]([Link]()-k, [Link]());
int start = 0;
while (start < [Link]()-1 && [Link](start)=='0') start++;
return [Link](start);
}
 }

class MinStack2 {
Deque<int[]> st = new ArrayDeque<>();
public void push(int v) {
int m = [Link]() ? v : [Link](v, [Link]()[1]);
[Link](new int[]{v, m});
}
public void pop() { [Link](); }
public int top() { return [Link]()[0]; }
public int getMin() { return [Link]()[1]; }
}

class MyQueue {
Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
public void push(int x) { [Link](x); }
public int pop() { move(); return [Link](); }
public int peek() { move(); return [Link](); }
public boolean empty() { return [Link]()&&[Link](); }
private void move() { if([Link]()) while(![Link]())
[Link]([Link]()); }
}

14 Practice Problems for Chapter 13

Solve in this order:

Easy Valid parentheses (LeetCode #20)

Easy Min stack (LeetCode #155)
Easy Implement queue using stacks (LeetCode #232)
Medium Daily temperatures (LeetCode #739)
Medium Next greater element I (LeetCode #496)
Medium Next greater element II (LeetCode #503)
Medium Decode string (LeetCode #394)
Medium Evaluate reverse polish notation (LeetCode #150)
Medium Remove K digits (LeetCode #402)
Hard Largest rectangle in histogram (LeetCode #84)
Hard Basic calculator (LeetCode #224)
Hard Trapping rain water (LeetCode #42)
💡 Key Insight: The monotonic stack is the single most powerful stack pattern — it solves Next
Greater, Daily Temperatures, Largest Rectangle, Trapping Rain Water, and Remove K Digits all
with the same underlying idea: maintain a stack where each new element evicts elements it
“dominates”. When you see “next greater/smaller” or “histogram rectangle”, immediately think
monotonic stack. Next up is Chapter 14 — Queues! 🚀

Prepared using Claude Sonnet 4.6 Thinking • Java Data Structures & Algorithms Series