📚 STACK — COMPLETE NOTES (Java + DSA Concepts)
📌 1️⃣ Stack Basics
● A stack is a linear data structure that follows the LIFO (Last In First Out) principle.
● Elements can be inserted and removed only from the top of the stack.
● Think of a stack of plates — you push a new plate on top, and pop the topmost plate.
👉 Real-life examples:
✅ Browser Back button
✅ Undo/Redo features
✅ Recursion call stack
✅ Expression evaluation
✅ Reversing elements
📌 2️⃣ Stack Declaration (Java)
Stack<Integer> stack = new Stack<>();
[Link](10); // insert on top
[Link](); // remove from top
[Link](); // view top
[Link](); // check if empty
[Link](); // number of elements
✅
Other options in Java:
Deque (as stack): faster than Stack class
✅ ArrayDeque<Integer> stack = new ArrayDeque<>();
📌 3️⃣ Stack Properties
● Follows LIFO
● Supports push/pop/peek in O(1) time
● Limited access: only the top element is accessible
● Can be implemented using arrays or linked lists
📌 4️⃣ Applications of Stack
✅ Parentheses checking (balanced brackets)
✅ Undo features in editors
✅ Function call management (call stack)
✅ Backtracking (Maze, Sudoku)
✅ Expression parsing and conversion (infix to postfix)
✅ Evaluation of postfix expressions
✅ Reversing strings
📌 5️⃣ Stack Operations
Operation Description Time Complexity
push insert an element on top O(1)
pop remove element from top O(1)
peek/top look at the top element O(1)
isEmpty check if stack is empty O(1)
size get number of elements O(1)
📌 6️⃣ Space Complexity
● A stack of size n uses O(n) space
● Auxiliary stacks (for Min Stack etc.) may use extra O(n)
🎯 7️⃣ Mock Interview Theory Questions
Q1. What is a stack?
A stack is a linear data structure that stores elements in a last-in, first-out manner.
Q2. Where is stack used in the real world?
In function call stack, browser history, undo-redo operations, expression parsing, and more.
Q3. How is a stack implemented in Java?
Using Stack<>, ArrayDeque<>, or custom linked list / array logic.
Q4. Difference between stack and queue?
● Stack → LIFO
● Queue → FIFO
Q5. What is stack overflow and underflow?
● Overflow: pushing to a full stack (fixed size).
● Underflow: popping from an empty stack.
Q6. Explain call stack in recursion.
Each function call is pushed on a stack; on return, it is popped, managing the program’s flow.
Q7. What is a monotonic stack?
A stack that maintains elements in increasing/decreasing order, used in range problems (like Next Greater Element).
Q8. How to implement a stack with getMin() in O(1)?
Use an auxiliary minStack that tracks the minimum value while pushing and popping.
Q9. Can you implement a stack using queues?
Yes — two queues can be used to simulate a stack by shuffling elements.
Q10. How is stack used in parsing expressions?
It helps store operators and operands while converting infix to postfix and evaluating postfix.
⚡ 8️⃣ Rapid-Fire One-Liners for Revision
✅ Stack = LIFO
✅ Supports push, pop, peek
✅ Used in parsing, backtracking, call stack
✅ Easy to implement with array/linked list
✅ Monotonic stacks = solve next greater/smaller
✅ Stack + recursion → important in DFS
✅ Parentheses matching → use a stack
✅ Balanced string = stack problem
✅ Evaluate postfix = stack
✅ Min/Max Stack → extra stack stores mins/maxs
🚀 9️⃣ Top 50 Stack Questions for Practice (LeetCode + Company Tags)
No Question LC # Difficulty Companies
1 Valid Parentheses 20 Easy Amazon, Microsoft
2 Min Stack 155 Easy Amazon, Adobe
3 Evaluate Reverse Polish Notation 150 Medium Amazon, Bloomberg
4 Daily Temperatures 739 Medium Facebook, Amazon
5 Largest Rectangle in Histogram 84 Hard Google, Adobe
6 Decode String 394 Medium Microsoft
7 Simplify Path 71 Medium Amazon
8 Implement Queue using Stacks 232 Easy Infosys, Amazon
9 Implement Stack using Queues 225 Easy Microsoft, Wipro
10 Asteroid Collision 735 Medium Adobe
11 Longest Valid Parentheses 32 Hard Google, Bloomberg
12 Backspace String Compare 844 Easy Amazon, TCS
13 Remove K Digits 402 Medium Amazon
14 Remove All Adjacent Duplicates 1047 Easy Wipro
15 Valid Stack Sequences 946 Medium Facebook
16 Final Prices With Special Discount 1475 Easy Walmart
17 Baseball Game 682 Easy -
18 Score of Parentheses 856 Medium -
19 Stock Span Problem - Medium -
20 Next Greater Element II 503 Medium -
21 Next Smaller Element - Medium -
22 Online Stock Span 901 Medium Amazon
23 Remove Outermost Parentheses 1021 Easy -
24 Maximal Rectangle 85 Hard Google
25 Exclusive Time of Functions 636 Medium Facebook
26 Minimum Add to Make Parentheses Valid 921 Medium -
27 132 Pattern 456 Medium -
28 Sum of Subarray Minimums 907 Medium -
29 Next Greater Element III 556 Medium -
30 Minimum Remove to Make Valid 1249 Medium -
Parentheses
31 Min Cost Tree From Leaf Values 1130 Medium -
32 Sum of Subarray Ranges 2104 Medium -
33 Validate Stack Sequences 946 Medium Facebook
34 Validate Parentheses String with Stars 678 Medium -
35 Valid Palindrome with Deletion 680 Medium -
36 Candy Crush Simulation - Medium -
37 Exclusive Time of Functions 636 Medium Facebook
38 Remove Duplicate Letters 316 Medium -
39 Remove K Digits 402 Medium Amazon
40 Decode Ways 91 Medium -
41 Asteroid Collision 735 Medium Adobe
42 Build Array with Stack Operations 1441 Medium -
43 Make The String Great 1544 Easy -
44 Minimum Insertions to Balance 1541 Medium -
Parentheses
45 Sum of Subarray Ranges 2104 Medium -
46 Final Prices With Special Discount 1475 Easy Walmart
47 Maximum Score After Splitting a String 1422 Easy -
48 Largest Rectangle in Histogram 84 Hard Google, Adobe
49 Maximal Rectangle 85 Hard Google
50 Remove K Digits 402 Medium Amazon
🧩 STACK Ultimate Tricks / Patterns Cheatsheet
Trick 1️⃣ — Valid Parentheses Matching
✅
Use Case:
✅
Validate balanced parentheses
Can extend to balanced tags
Where? LC 20 (Amazon, Microsoft)
Pattern
● Push opening bracket onto stack
● Pop and match on closing bracket
● If at the end the stack is empty → valid
Code Sketch
Stack<Character> stack = new Stack<>();
for (char c : [Link]()) {
if (c == '(' || c == '{' || c == '[') [Link](c);
else if ([Link]() ||
(c == ')' && [Link]() != '(') ||
(c == '}' && [Link]() != '{') ||
(c == ']' && [Link]() != '[')) return false;
return [Link]();
Trick 2️⃣ — Next Greater Element
✅
Use Case:
For each element, find the next greater to its right
Where? LC 496, LC 503 (Amazon, Flipkart)
Pattern
● Monotonic stack from right to left
● Pop smaller elements
● Stack top after popping → next greater
Code Sketch
Stack<Integer> stack = new Stack<>();
for (int i = [Link] - 1; i >= 0; i--) {
while (![Link]() && [Link]() <= arr[i]) [Link]();
res[i] = [Link]() ? -1 : [Link]();
[Link](arr[i]);
Trick 3️⃣ — Next Smaller Element
✅
Use Case:
Histogram area, stock span
Where? LC 84, LC 85 (Google, Adobe)
Pattern
● Monotonic increasing stack
● Pop elements greater than current
● Next smaller found after popping
Code Sketch
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < [Link]; i++) {
while (![Link]() && arr[[Link]()] >= arr[i]) [Link]();
// do something with [Link]() as next smaller
[Link](i);
Trick 4️⃣ — Monotonic Stack (Increasing/Decreasing)
✅
Use Case:
✅
Range queries
✅
Sliding window
Next/Prev greater/smaller
Where? LC 739, LC 901
Trick 5️⃣ — Min Stack
✅
Use Case:
Support push/pop/top/getMin in O(1)
Where? LC 155 (Amazon)
Pattern
● Use two stacks:
○ normal stack
○ minStack for minimum tracking
Trick 6️⃣ — Reverse Polish Notation
✅
Use Case:
Postfix evaluation
Where? LC 150 (Amazon, Bloomberg)
Pattern
● Traverse tokens
● Push numbers
● Pop two elements for operator
Trick 7️⃣ — Decode Nested String
✅
Use Case:
Decode “3[a2[c]]” type nested patterns
Where? LC 394
Pattern
● Use two stacks
○ counts
○ results so far
Trick 8️⃣ — Histogram Max Area
✅
Use Case:
Largest rectangle in histogram
Where? LC 84
Pattern
● Append a zero at end
● Use monotonic stack
● Track height * width area
Trick 9️⃣ — Daily Temperatures
✅
Use Case:
Next warmer day
Where? LC 739
Pattern
● Monotonic decreasing stack
● Store indices
Trick 🔟 — Implement Queue using Stack
✅
Use Case:
Stack simulating queue
Where? LC 232
Pattern
● 2 stacks
○ in
○ out
● lazy transfer
Trick 1️⃣1️⃣ — Longest Valid Parentheses
✅
Use Case:
Longest balanced substring of parentheses
Where? LC 32 (Google, Bloomberg)
Pattern
● Push index of (
● On ), pop and calculate length
● Use a base -1 marker in stack
Code Sketch
Stack<Integer> stack = new Stack<>();
[Link](-1);
int maxLen = 0;
for (int i = 0; i < [Link](); i++) {
if ([Link](i) == '(') [Link](i);
else {
[Link]();
if ([Link]()) [Link](i);
else maxLen = [Link](maxLen, i - [Link]());
Trick 1️⃣2️⃣ — Remove Adjacent Duplicates
✅
Use Case:
Remove consecutive duplicate letters
Where? LC 1047 (TCS, Wipro)
Pattern
● Push char onto stack
● Pop if top equals current
Code Sketch
Stack<Character> stack = new Stack<>();
for (char c : [Link]()) {
if (![Link]() && [Link]() == c) [Link]();
else [Link](c);
}
Trick 1️⃣3️⃣ — Backspace String Compare
✅
Use Case:
Simulate backspaces
Where? LC 844 (Amazon)
Pattern
● Push valid characters
● Pop on #
Trick 1️⃣4️⃣ — Simplify Unix Path
✅
Use Case:
Canonical path
Where? LC 71
Pattern
● Split by /
● Ignore ., pop ..
● Push folder names
Trick 1️⃣5️⃣ — Browser History Simulation
✅
Use Case:
Navigate forward and back
Where? LC 1472
Pattern
● 2 stacks
○ back
○ forward
● push/pop to go forward/back
Trick 1️⃣6️⃣ — Remove K Digits
✅
Use Case:
Make smallest number
Where? LC 402 (Amazon)
Pattern
● Monotonic increasing stack
● Pop big digits when k > 0
Trick 1️⃣7️⃣ — Asteroid Collision
✅
Use Case:
Simulate left/right collisions
Where? LC 735
Pattern
● Push positive asteroids
● For negative, check top positive
● Pop on collision
Trick 1️⃣8️⃣ — Baseball Game
✅
Use Case:
Sum with cancel + double + addition
Where? LC 682
Pattern
● Stack for valid scores
● On C remove top
● On D push 2×top
● On + push sum of top two
Trick 1️⃣9️⃣ — Exclusive Time of Functions
✅
Use Case:
Log-based nested function timing
Where? LC 636 (Facebook)
Pattern
● push function on start
● calculate diff on end
● update nested
Trick 2️⃣0️⃣ — Minimum Add to Make Parentheses Valid
✅
Use Case:
Balance minimum additions
Where? LC 921
Pattern
● push for (
● pop for )
● unmatched left → need to add
Trick 2️⃣1️⃣ — Validate Stack Sequences
✅
Use Case:
Check push/pop order
Where? LC 946
Pattern
● simulate push/pop with stack
● match popping sequence
Trick 2️⃣2️⃣ — Min Cost Tree from Leaf Values
✅
Use Case:
DP + monotonic stack
Where? LC 1130
Pattern
● maintain monotonic decreasing
● multiply min leaves
● sum cost
Trick 2️⃣3️⃣ — Stock Span Problem
✅
Use Case:
Previous greater element
Where? Standard stock question
Pattern
● monotonic decreasing stack
● previous greater index difference
Trick 2️⃣4️⃣ — Decode Ways with Stack
✅
Use Case:
Complex nested decoding
Where? LC 91 variation
Pattern
● store partial decode
● stack previous substrings
Trick 2️⃣5️⃣ — 132 Pattern
✅
Use Case:
Check for 132 pattern
Where? LC 456
Pattern
● stack for third number
● scan from end
● maintain min middle
Trick 2️⃣6️⃣ — Online Stock Span
✅
Use Case:
Online queries
Where? LC 901
Pattern
● monotonic stack
● store day+price
Trick 2️⃣7️⃣ — Maximum Area in Binary Matrix
✅
Use Case:
Extension of histogram
Where? LC 85
Pattern
● transform each row to histogram
● call largest area in histogram
Trick 2️⃣8️⃣ — Minimum Insertions to Balance Parentheses
✅
Use Case:
LC 1541
Where? Google, Amazon
Pattern
● same as Trick 20, but add two for ))
Trick 2️⃣9️⃣ — Validate Parentheses with Stars
✅
Use Case:
LC 678
Where? Flexible brackets
Pattern
● two stacks
○ one for (
○ one for *
Trick 3️⃣0️⃣ — Make String Great
✅
Use Case:
Cancel opposite cases (upper/lower)
Where? LC 1544
Pattern
● push character
● check current vs top for same letter, opposite case
● pop if matches
⭐️ How to Use This Cheatsheet?
✅ Use the pattern keyword (monotonic, balancing, simulation)
✅ When seeing LC question tags — immediately match to a trick
✅ Practice 3–5 times with variations
✅ Then add that pattern to your “mental muscle memory”
✅ Revisit in 15 days to keep it fresh