Lesson 1 � Beginner

Stack: LIFO ka Master

Stack sabse simple aur powerful data structure hai. Jaise tum plates rakhte ho � jo sabse upar rakhi hai wo sabse pehle nikalti hai. Ye LIFO (Last In, First Out) principle pe kaam karta hai. Interview mein stack se bahut saare problems solve hote hain � from valid parentheses to next greater element.

? 20 min✓ Beginner✓ Python basics

Stack kya hai?

WHAT

Stack ek linear data structure hai jisme sirf ek end se hi insertion aur deletion hota hai. Jise "top" bolte hain. Jo element sabse last mein aaya hai (push hua hai), wo sabse pehle nikalta hai (pop hota hai). Isko LIFO � Last In, First Out kehte hain.

WHEN

Jab tumhe elements ko reverse order mein process karna ho, jab function calls manage karni hon, jab undo/redo implement karna ho, jab expression evaluation karni ho, ya jab parentheses matching karni ho � tab stack use karo.

WHERE

Function call stack (recursion), browser back button, text editor undo, expression evaluation, parenthesis matching, DFS traversal, tower of Hanoi � ye sab stack pe based hain.

Mental Model: Imagine karo tumhari desk pe kitabein rakhi hain. Tum hamesha upar ki kitab se padhte ho aur upar hi rakhte ho. Neeche ki kitab tak pahunchne ke liye upar wali hatani padti hai. Stack bhi aise hi kaam karta hai � Last In, First Out.

# Stack ka visual representation
# push(10) ? [10]
# push(20) ? [10, 20]
# push(30) ? [10, 20, 30]
# pop() ? [10, 20] (30 nikla)
# pop() ? [10] (20 nikla)

# Top element hamesha last index hota hai
# stack[-1] ✓ current top

Stack ke Basic Operations

Stack mein char main operations hain � push, pop, peek, aur is_empty. Ye sab O(1) time mein hote hain Python list ke saath:

# Stack using Python list � sabse easy way
stack = []

# PUSH � element daalo stack mein
stack.append(10)
stack.append(20)
stack.append(30)
print(stack) # [10, 20, 30]

# POP � top element nikalo
top = stack.pop()
print(top) # 30 (jo sabse last mein tha)
print(stack) # [10, 20]

# PEEK � top element dekho bina nikale
top = stack[-1]
print(top) # 20

# IS_EMPTY � check karo stack khaali hai ya nahi
print(len(stack) == 0) # False

# SIZE � kitne elements hain
print(len(stack)) # 2

push() � O(1)

stack.append(x) � element ko stack ke top pe rakhta hai. Python list ka append O(1) amortized hota hai. Ye sabse common operation hai.

pop() � O(1)

stack.pop() � top element nikalta hai aur return karta hai. Agar stack empty hai toh error aata hai. Dhyan rakhlo � pop karne se pehle empty check karo.

peek() � O(1)

stack[-1] � top element bina nikale dekhta hai. Useful jab tumhe top value chahiye but remove nahi karni. Ye O(1) hai kyunki direct index access hai.

Why not list se front pe insert/delete? Python list se insert(0, x) ya pop(0) karo toh O(n) hota hai kyunki sab elements shift hote hain. Stack mein hamesha end pe operations karte hain isliye O(1) milta hai. Isliye list ko stack ki tarah use karo � sirf append aur pop se.

Real-World Stack Uses

Stack sirf interview mein nahi, real life mein bhi bahut kaam aata hai. Ye 3 examples samjho:

# USE CASE 1: Undo functionality (text editor)
history = []

# User ne type kiya
history.append("Hello")
history.append("Hello World")
history.append("Hello World!")

# User ne Ctrl+Z kiya � last action undo
last = history.pop() # "Hello World!" hata
print(f"Ab editor mein: {history[-1]}") # "Hello World"

# USE CASE 2: Browser back button
visited = ["google.com", "youtube.com", "github.com"]
back = visited.pop() # github.com se wapas aao
print(f"Ab hum hain: {visited[-1]}") # youtube.com

# USE CASE 3: Function call stack (recursion)
# Jab tum recursive function call karte ho, har call stack pe push hoti hai
# Jab function return hota hai, stack se pop hota hai

# USE CASE 4: Balanced Parentheses check
def is_balanced(expr):
 stack = []
 for ch in expr:
 if ch == '(':
 stack.append(ch)
 elif ch == ')':
 if not stack:
 return False
 stack.pop()
 return len(stack) == 0

print(is_balanced("(a+b)*(c-d)")) # True
print(is_balanced("(a+b*(c-d)")) # False � closing bracket zyada

Interview Pattern: Agar question mein "matching", "nested", "previous element", ya "reverse order" ka scene hai � stack try karo. Valid Parentheses, Min Stack, Next Greater Element � ye sab stack patterns hain.

Stack as a Class

Real interviews mein tumhe stack class banana pad sakta hai. Ye template yaad rakhlo:

class Stack:
 def __init__(self):
 self.items = []
 
 def push(self, item):
 self.items.append(item)
 
 def pop(self):
 if self.is_empty():
 raise IndexError("Stack is empty")
 return self.items.pop()
 
 def peek(self):
 if self.is_empty():
 raise IndexError("Stack is empty")
 return self.items[-1]
 
 def is_empty(self):
 return len(self.items) == 0
 
 def size(self):
 return len(self.items)
 
 def __str__(self):
 return str(self.items)

# Use karo
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(s) # [10, 20, 30]
print(s.pop()) # 30
print(s.peek()) # 20
print(s.size()) # 2

Try it: code khud likho

Exercise

Question: MinStack class implement karo jisme push, pop, top, aur get_min sab O(1) ho. Stack mein [5, 3, 7, 1] push karo aur get_min call karo. Answer mein minimum value likho.

Question: Stack [1, 2, 3, 4, 5] ko reverse karo bina extra space ke. Answer mein reversed stack likho (comma-separated, jaise "5,4,3,2,1").

Common mistakes

Empty stack se pop karna: Jab stack empty ho tab pop() karoge toh error aayega. Hamesha if not stack: check karo pehle.
pop() ka return value ignore karna: pop() wo value return karta hai jo nikali hai. Agar tumhe wo value chahiye toh store karo � x = stack.pop().
Front pe operations karna: Stack ka point hai end pe operations karna. Agar tum insert(0, x) kar rahe ho toh wo stack nahi, list hai. O(n) ho jayega.
Recursion mein stack overflow: Bahut deep recursion se stack overflow ho sakta hai. Python mein default limit ~1000 hai. Tail recursion optimization Python nahi karta.

Lesson complete?

Stack basics samajh aa gaye✓ Ab Queue seekhte hain � ye stack ka ulta hai, FIFO principle pe kaam karta hai.