2/17/26, 8:55 PM Google Gemini
DSA Study Guide: Stacks & Applications
A Stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. Think of it
like a stack of plates: you add to the top and take from the top.
1. Core Operations (Theory)
Every stack must support these operations (O(1) time complexity):
Push: Add an element to the top. (Check for Overflow if the array is full).
Pop: Remove the top element. (Check for Underflow if the stack is empty).
Peek/Top: Look at the top element without removing it.
isEmpty: Check if the stack is empty.
2. Expressions: Infix, Prefix, and Postfix (Beginner Friendly)
When we write math, we use "Infix," but computers prefer "Postfix." Here is why:
A. Infix (The "Human" Way)
Format: Operand 1 -> Operator -> Operand 2 (e.g., A + B )
The Problem: It requires Parentheses and Rules (BODMAS). For example, in 2 + 3 ∗ 4,
we must know to do the multiplication first. Computers find these rules hard to scan
quickly.
B. Postfix (The "Computer" Way - Reverse Polish Notation)
Format: Operand 1 -> Operand 2 -> Operator (e.g., AB+)
The Benefit: No parentheses needed! The computer just reads from left to right and
calculates as soon as it sees an operator. This is what Stacks are used for.
C. Prefix (The "Polish" Way)
Format: Operator -> Operand 1 -> Operand 2 (e.g., +AB )
Note: Similar to Postfix, but the operator comes first.
Type Example Placement of Operator
Infix A+B In-between operands
Postfix AB+ Post (After) operands
[Link] 1/3
2/17/26, 8:55 PM Google Gemini
Prefix +AB Pre (Before) operands
3. How to Convert: The "Stack Rule"
When converting from Infix to Postfix, the Stack is only used for Operators. Operands
(letters/numbers) go straight to the answer.
The Golden Rule of the Stack:
Think of operators as having "weight" (Precedence).
High Weight: ^ (Power)
Medium Weight: * and /
Low Weight: + and -
The Rule: A "Heavy" operator can sit on a "Light" one, but a "Light" operator cannot sit on a
"Heavy" one. If a "Light" operator tries to get on the stack, the "Heavy" one must jump off (pop)
to the answer first.
Step-by-Step Conversion Example: A + B * C
1. See A : It's an operand. Add to result. -> Result: A
2. See + : Stack is empty. Push it. -> Stack: [+]
3. See B : Operand. Add to result. -> Result: AB
4. See * : * is "heavier" than + . It is allowed to sit on top. -> Stack: [+, *]
5. See C : Operand. Add to result. -> Result: ABC
6. End of string: Pop everything. -> Final Result: ABC*+
4. Postfix Evaluation (The "Calculator" Logic)
This is how a computer actually solves 5 3 + .
1. Scan 5 : Push to stack.
2. Scan 3 : Push to stack.
3. Scan + :
Pop the top number (3).
Pop the next number (5).
Add them (5 + 3 = 8).
Push 8 back to the stack.
[Link] 2/3
2/17/26, 8:55 PM Google Gemini
5. Recursion & Stacks
Recursion is internally implemented using a System Stack.
Tail Recursion: The recursive call is the very last action.
Fibonacci Logic: F ib(n) = F ib(n − 1) + F ib(n − 2).
For F ib(4), the stack stores calls for F ib(3) and F ib(2) until they reach the base
cases (F ib(1) = 1, F ib(0) = 0).
6. Implementation (Pseudocode)
Check for Balanced Parentheses
IS_BALANCED(expression):
Create an empty stack S
for each character char in expression:
if char is '(', '{', or '[':
[Link](char)
else if char is ')', '}', or ']':
if [Link](): return False
top = [Link]()
if not MATCH(top, char): return False
return [Link]()
Quick Revision Tips:
1. Overflow: Adding to a full stack.
2. Underflow: Removing from an empty stack.
3. Peeking: Looking at the top without removing it.
[Link] 3/3