DSA: STACK ■
Hinglish + Baby Style Notes for Beginners
Made for: Chhavi / Piku ■
Language: Simple Hinglish
Focus: Stack Basics → Operations → Array/Linked List → STL → Recursion → Applications
Stack ko samajhne ka easiest way: plates ka stack ■■. Jo plate sabse last mein rakhi, wahi sabse pehle
niklegi. Isko bolte hain LIFO — Last In, First Out ■
■ Baby Tip: Stack ko plates ke pile ki tarah imagine karo. Neeche wali plate directly nahi nikal sakte ■
Quick Roadmap
1 Stack Basics LIFO, Top, Operations
2 Implementation Array + Linked List
3 STL Stack C++ stack
4 Applications Parentheses, Undo, Recursion
5 Expressions Infix, Prefix, Postfix
6 Advanced Monotonic Stack + Problems
DSA Stack Notes • Page 1
1. Stack kya hota hai? ■
Stack ek linear data structure hai. Isme elements ek order mein store hote hain.
Stack ka main rule hai LIFO — Last In, First Out.
TOP
↓
[ 30 ] ← last inserted
[ 20 ]
[ 10 ] ← first inserted
Agar 30 sabse last mein aaya, to 30 sabse pehle bahar jayega.
Real-life Examples
• Plates ka stack ■■
• Books ka pile ■
• Browser back button ■
• Undo operation ■■
• Function calls in programming
■ Baby Tip: Stack = plate wali story. Last plate rakhi → first plate niklegi ■
DSA Stack Notes • Page 2
2. LIFO — Stack ka golden rule ■
LIFO = Last In, First Out
Iska matlab jo element sabse last mein insert hua, wahi sabse pehle remove hoga.
Push 10
Push 20
Push 30
Stack:
[30] ← first out
[20]
[10]
Agar pop karenge, output = 30.
FIFO vs LIFO
Structure Rule Example
Stack LIFO Plates
Queue FIFO Line/Queue
■ Baby Tip: Stack ko Queue se confuse mat karna ■. Stack = last wala first. Queue = first wala first.
DSA Stack Notes • Page 3
3. Stack ke basic operations ■■
1. Push
Stack mein element add karna = Push.
2. Pop
Top element remove karna = Pop.
3. Peek / Top
Top element ko dekhna, remove nahi karna.
4. isEmpty
Check karta hai stack empty hai ya nahi.
Stack:
[30] ← TOP
push(40) → 40 add
pop() → 40 remove
peek() → 30 show
Stack mein normally operations TOP se hi hote hain.
■ Baby Tip: Push = andar daalo ■, Pop = bahar nikalo ■, Peek = bas dekh lo ■.
DSA Stack Notes • Page 4
4. Stack using Array — concept ■
Array se stack banane ke liye ek array aur top variable use karte hain.
int stack[5];
int top = -1;
Initially top = -1 ka matlab stack empty hai.
Index: 0 1 2 3 4
[ ] [ ] [ ] [ ] [ ]
top = -1
Push ke time top ko increase karenge, phir value store karenge.
Pop ke time top wali value remove karenge, phir top decrease karenge.
Important
Array stack ki fixed size hoti hai. Agar array full ho gaya to Overflow.
■ Baby Tip: Top ko stack ka monitor samjho ■. Top batata hai latest element kahan hai.
DSA Stack Notes • Page 5
5. Push Operation using Array ■
Push ka matlab new element ko stack mein add karna.
void push(int value) {
if (top == 4) {
cout << "Stack Overflow";
return;
}
top++;
stack[top] = value;
}
Step-by-step
• Check: stack full hai?
• Agar full → Overflow.
• top ko 1 increase karo.
• New value stack[top] par store karo.
Initially: top = -1
push(10)
top = 0
push(20)
top = 1
Stack ab:
[20] ← TOP
[10]
■ Baby Tip: Push mein pehle top badhao, phir value rakho. Ye order yaad rakhna ■.
DSA Stack Notes • Page 6
6. Pop Operation using Array ■
Pop ka matlab top element ko remove karna.
void pop() {
if (top == -1) {
cout << "Stack Underflow";
return;
}
cout << stack[top];
top--;
}
Underflow kya hota hai? ■
Jab stack empty ho aur hum pop karne ki try karein, to Underflow.
Stack empty
top = -1
pop() ■
→ Stack Underflow
Push mein full check = Overflow. Pop mein empty check = Underflow.
■ Baby Tip: Overflow = jagah nahi ■. Underflow = element hi nahi ■.
DSA Stack Notes • Page 7
7. Peek, isEmpty aur Display ■
Peek
int peek() {
if (top == -1)
return -1;
return stack[top];
}
Peek sirf top value dikhata hai. Element remove nahi hota.
isEmpty
bool isEmpty() {
return top == -1;
}
Display
void display() {
for (int i = top; i >= 0; i--)
cout << stack[i] << " ";
}
Display generally top se bottom tak print kar sakte hain.
■ Baby Tip: Peek = dekhna ■. Pop = nikalna ■. Dono same nahi hain.
DSA Stack Notes • Page 8
8. Complete Stack using Array — C++ ■
#include <iostream>
using namespace std;
class Stack {
int arr[5];
int top;
public:
Stack() {
top = -1;
}
void push(int x) {
if (top == 4) {
cout << "Overflow\n";
return;
}
arr[++top] = x;
}
void pop() {
if (top == -1) {
cout << "Underflow\n";
return;
}
cout << arr[top--] << " removed\n";
}
void peek() {
if (top == -1)
cout << "Empty\n";
else
cout << arr[top] << "\n";
}
};
Ye code ek basic stack class banata hai.
■ Baby Tip: Piku, pehle code ko line-by-line samajhna. Direct copy karke run karna allowed hai ■■
DSA Stack Notes • Page 9
9. Stack using Linked List ■
Array stack ki size fixed hoti hai. Linked List se stack dynamically grow kar sakta hai.
struct Node {
int data;
Node* next;
};
Yahan top pointer linked list ke first node ko point karega.
TOP
↓
[30] → [20] → [10] → NULL
Push: beginning mein node add.
Pop: beginning se node remove.
Why beginning?
Kyuki beginning se insertion/deletion O(1) mein possible hai.
■ Baby Tip: Linked List Stack mein top = head samjho ■.
DSA Stack Notes • Page 10
10. Stack using Linked List — Push & Pop
Push
void push(int x) {
Node* newNode = new Node;
newNode->data = x;
newNode->next = top;
top = newNode;
}
New node ko top ke aage laga diya.
Pop
void pop() {
if (top == NULL) {
cout << "Underflow";
return;
}
Node* temp = top;
top = top->next;
delete temp;
}
Top ko next node par move kar diya aur old node delete.
■ Baby Tip: Push = new node ko top ke aage chipkao ■. Pop = top ko next par le jao.
DSA Stack Notes • Page 11
11. C++ STL Stack ■
C++ mein ready-made stack available hai.
#include <stack>
using namespace std;
stack<int> s;
Important Functions
[Link](10);
[Link](20);
[Link]();
[Link]();
[Link]();
[Link]();
STL stack internally stack operations ko easy bana deta hai.
Example
stack<int> s;
[Link](10);
[Link](20);
[Link](30);
cout << [Link](); // 30
[Link]();
cout << [Link](); // 20
■ Baby Tip: Competitive programming mein STL stack kaafi use hota hai ■.
DSA Stack Notes • Page 12
12. Stack ki Time Complexity ■■
Stack ke basic operations usually O(1) hote hain.
Operation Time Complexity
Push O(1)
Pop O(1)
Peek/Top O(1)
isEmpty O(1)
O(1) ka matlab: input size chahe 10 ho ya 10 lakh, operation ka time approximately constant.
■ Baby Tip: Stack ki speed ka main reason: hum sirf TOP par kaam karte hain ■.
DSA Stack Notes • Page 13
13. Stack Applications — real DSA power ■
Stack sirf plates ke liye nahi ■. Programming mein iska bahut use hota hai.
• Function Call Stack: Function calls manage karne ke liye.
• Recursion: Har recursive call stack mein store hoti hai.
• Undo/Redo: Previous actions store karne ke liye.
• Browser Back: Previous pages track karne ke liye.
• Parentheses Matching: Brackets balanced hain ya nahi.
• Expression Conversion: Infix, Prefix, Postfix.
• Next Greater Element: Monotonic Stack.
Important Exam Line
Stack is used when the most recently inserted element must be processed first.
■ Baby Tip: Jahan 'last wala pehle' wali feeling aaye, wahan Stack ka naam yaad karo ■.
DSA Stack Notes • Page 14
14. Balanced Parentheses — Stack ka famous question ■
Question: brackets balanced hain ya nahi?
Input: ({[]})
Output: Balanced
Input: ([)]
Output: Not Balanced
Logic
• Opening bracket aaye → stack mein push.
• Closing bracket aaye → top check.
• Matching pair hai → pop.
• Mismatch hai → Not Balanced.
• End mein stack empty → Balanced.
for(char ch : str) {
if (ch == '(' || ch == '[' || ch == '{')
[Link](ch);
else {
if ([Link]())
return false;
[Link]();
}
}
Real code mein matching bracket type bhi check karna hota hai.
■ Baby Tip: Opening = andar daalo. Closing = last opening ko match karo. Stack ka perfect use ■.
DSA Stack Notes • Page 15
15. Infix, Prefix aur Postfix Expressions ■
Expression likhne ke different ways hote hain.
Infix
Operator beech mein.
A + B
Prefix
Operator pehle.
+ A B
Postfix
Operator last mein.
A B +
Stack ka use expressions convert aur evaluate karne mein hota hai.
Example
Infix: A + B * C
Operator precedence ke according stack help karta hai.
■ Baby Tip: Prefix = operator pehle. Postfix = operator baad mein. Naam se hi clue milta hai ■.
DSA Stack Notes • Page 16
16. Monotonic Stack — advanced concept ■
Monotonic Stack ek aisa stack hota hai jisme elements ek particular order maintain karte hain.
Mostly Next Greater Element aur Next Smaller Element problems mein use hota hai.
Array: 2 1 5 3
Next Greater:
2 → 5
1 → 5
5 → -1
3 → -1
Normal brute force mein har element ke liye aage search karna pad sakta hai. Monotonic Stack se efficient
solution mil sakta hai.
Main Idea
Stack mein useless elements ko remove karte jao, taaki useful order maintain rahe.
■ Baby Tip: Monotonic Stack ko abhi bas conceptually samjho. Pehle normal Stack strong karna
compulsory hai ■.
DSA Stack Notes • Page 17
17. Stack Revision + Practice Questions ■
One-page Revision
• Stack = Linear Data Structure.
• Stack follows LIFO.
• Push = insert.
• Pop = remove top.
• Peek/Top = see top.
• Overflow = full stack mein push.
• Underflow = empty stack mein pop.
• Array Stack uses top.
• Linked List Stack uses top pointer.
• Stack operations generally O(1).
• Stack is used in recursion and function calls.
• Stack helps in balanced parentheses.
• Stack is used in expression conversion.
• Monotonic Stack solves many next greater/smaller problems.
Practice Questions ✍■
• 1. Stack define karo aur LIFO explain karo.
• 2. Stack ke four basic operations likho.
• 3. Overflow aur Underflow mein difference.
• 4. Array se Stack implement karo.
• 5. Linked List se Stack implement karo.
• 6. Stack aur Queue compare karo.
• 7. Balanced Parentheses using Stack explain karo.
• 8. Infix, Prefix, Postfix examples do.
• 9. Stack ki applications likho.
• 10. Stack ki time complexity likho.
Final Piku Tip ■: Stack ko plates ki tarah imagine karo. Jab bhi confusion ho, khud se pucho: 'Last mein
kaunsa element aaya tha? Kya wahi pehle niklega?' ■■
Next DSA topic bhi hum isi style mein tod denge ■■
DSA Stack Notes • Page 18