3.2.6
Intuition Har stack application ke peeche ek hi ideaStack ek Last-In-First-Out (LIFO) memory hai. Yeh tab best kaam karta hai jab problem mein nested / matched structure ho: jo cheez sabse baad mein open hui, wahi sabse pehle close honi chahiye. Parentheses, operators jo apne operands ka wait kar rahe hain, aur function calls jo return ka wait kar rahi hain — yeh sab "open... open... ulte order mein close" wale patterns hain. WHY a stack? Kyunki LIFO hi nesting hai.
Brackets ki ek string balanced hoti hai agar har opening bracket ka ek matching closing bracket ho same type ka, aur woh sahi tarah se nested hon (koi crossing nahi jaise ([)]).
Intuition WHY stack se solve hota haiJab aap ( padhte ho, toh ek promise karte ho ki ise baad mein close karoge. Jo promise sabse baad ki gayi, woh sabse pehle poori karni padegi — yahi LIFO hai. Toh: openers ko push karo, aur jab closer dikhe, toh top par jo cheez hai woh uska matching opener zaroor honi chahiye.
HOW (algorithm):
Har character ke liye:
Agar woh opener hai ( [ { → push karo.
Agar woh closer hai → agar stack empty ho → fail ; warna pop karo aur check karo ki match karta hai ya nahi.
End mein, stack empty honi chahiye (koi unfulfilled promises nahi).
([)] — NOT balanced
( push karo, [ push karo. ) dikha → top hai [, mismatch → fail .
Yeh crossing kyun pakad leta hai: ) chahta hai ( ko close karna, lekin [ (baad mein open hua) abhi bhi open hai, toh nesting violate ho gayi.
( aur ) ki count equal hai, bas itna kaafi hai."
Kyun sahi lagta hai: balanced strings mein counts equal hote hi hain. Kyun galat hai: )( ki count 2=2 hai lekin unbalanced hai; ([)] mein har type ki matched counts hain phir bhi crossing hai. Fix: aapko order chahiye (ek stack), sirf counts nahi. Yeh bhi yaad rakho ki end mein stack empty hai ya nahi check karo — ((( mein openers bacha hua hoga.
Infix: operator operands ke beech mein: a + b.Postfix (RPN): operator operands ke baad : a b +. Parentheses ki zaroorat nahi.
Intuition WHY convert karte hain?Infix ko evaluate karne ke liye precedence aur parentheses ke rules chahiye. Postfix order ko directly encode karta hai, toh ek machine ise left-to-right ek stack se evaluate kar sakti hai — koi backtracking nahi. Stack ek low-precedence operator ko wait karne deta hai jab tak higher wale pehle execute ho jaate hain.
HOW (algorithm): left→right scan karo, ek operator stack rakho, output banao:
Operand → output mein append karo.()( tak output mein pop karo; ( ko discard karo.Operator o → jab tak stack top ek operator hai higher precedence ke saath, ya equal precedence aur o left-associative hai → use output mein pop karo. Phir o push karo.End → sab kuch output mein pop karo.
a + b * c → a b c * +
tok
action
stack
output
aoutput
a
+push
+a
boutput
+a b
**>+, toh pop mat karo; push karo+ *a b
coutput
+ *a b c
end
sab pop karo
a b c * +
Jab * aaya toh + pop kyun nahi hua? * ki precedence zyada hai, toh b*c pehle hona chahiye; + wait karta raha.
(a + b) * c → a b + c *
tok
action
stack
output
(push
(
aoutput
(a
+push (neeche ( hai, kuch higher nahi)
( +a
boutput
( +a b
)( tak pop karoa b +
*push
*a b +
coutput
*a b + c
end
sab pop karo
a b + c *
Parentheses + ko pehle kyun force karte hain? ) sab kuch apne ( tak flush kar deta hai, inner group ko * se pehle execute kara deta hai.
Common mistake Equal-precedence operators ko galat tarah pop karna.Kyun sahi lagta hai: "+ aur - same level par hain, toh purane wale ko chhod do." Kyun galat hai: a - b + c ka matlab (a-b)+c hona chahiye, yani left-to-right. Kyunki -/+ left-associative hain, jab + aata hai toh aap waiting - ko zaroor pop karte ho. Result: a b - c +. Right-associative ^ ke liye, aap equal ^ ko pop nahi karte.
Intuition WHY functions stack use karti hainJab f, g ko call karta hai, f pause ho jaata hai aur g ke return hone ke baad exactly wahan se resume karna hoga jahan chhoda tha. Jo function sabse baad call hua, woh sabse pehle return karta hai — pure LIFO. Toh system ek stack of stack frames rakhta hai.
Definition Stack frame (activation record)Har call ke liye, ek frame store karta hai: return address (kahan continue karna hai), parameters , local variables , aur saved registers. Calling se frame push hota hai; returning se pop hota hai.
fact(3)
fact(n): if n==0 return 1; else return n*fact(n-1)
Push order (top = abhi running):
fact(0) ← top, pehle return karta hai
fact(1)
fact(2)
fact(3) ← bottom, sabse baad return karta hai
Yeh order kyun? Har call deeper call ka wait karta hai. fact(0) pehle resolve hota hai, phir unwind hota hai: 1·1·2·3 = 6.
Common mistake "Deep recursion free hai."Kyun sahi lagta hai: code chhota lagta hai. Kyun galat hai: har call ek frame push karta hai; zyada ho gaye toh → stack overflow . Fix: base case add karo, depth limit lagao, ya iteration / tail recursion mein convert karo.
Recall Feynman: ek 12-saal ke bacche ko samjhaoSocho plates ka ek stack. Sirf upar se add ya liya ja sakta hai. Brackets boxes kholne jaisi hain: jo box sabse baad khola, wahi sabse pehle band karna padega — toh har khule box ko stack karo aur close karne par pop karo. Sums ke liye, stack ek "weak" plus-sign ko wait karne deta hai jab ek "strong" times-sign pehle jump karta hai. Aur jab ek task koi helper task call kare, toh pehla task stack par wait karta hai jab tak helper finish nahi ho jaata — last started, first finished.
L.I.F.O. = "Last In, First Out"
"Party mein jo mehman sabse baad aaya, woh sabse pehle jaata hai." Brackets, operators, aur function calls sab party se aane ke ulte order mein jaate hain.
Stack ki kaunsi property use nested structures ke liye perfect banati hai? LIFO — sabse recently open item ko pehle close/resolve karna hota hai.
Balanced-parentheses mein success ke liye kaunsi do conditions zaroori hain? Har closer ne popped opener se match kiya HO AUR end mein stack empty ho.
( aur ) count karna kyun fail karta hai?Yeh order/nesting ignore karta hai, jaise )( aur ([)] count pass karte hain lekin unbalanced hain.
Infix→postfix mein operand par kya karte ho? Use directly output mein append karo.
Infix→postfix mein ) par kya karte ho? ( tak operators ko output mein pop karo, phir ( discard karo.
Jab operator o aata hai, toh stack top ko kab pop karte ho? Jab tak top ek operator ho higher precedence ka, ya equal precedence ka jab o left-associative ho.
a + b * c ko postfix mein convert karo.a b c * +
(a + b) * c ko postfix mein convert karo.a b + c *
^ ko specially kyun treat kiya jaata hai?Yeh right-associative hai, toh equal-precedence ^ ko pop nahi karte.
Function stack frame kya store karta hai? Return address, parameters, local variables, saved registers.
Jo call sabse baad start hui, woh pehle kyun return karti hai? Ek caller apne callee ke return hone tak pause rehta hai — pure LIFO unwinding.
Recursion mein stack overflow kyun hota hai? Bahut zyada un-returned frames (jaise missing/late base case) stack memory khatam kar dete hain.
Stack — ADT and Implementation (yahan use ki gayi LIFO operations)Recursion and the Call Stack Expression Trees and Evaluation Postfix Evaluation Algorithm Queues (contrast: FIFO vs LIFO)Operator Precedence and Associativity
LIFO stack
