3.2.5 · HinglishLinear Data Structures
Stack — LIFO semantics, push - pop - peek, array and linked list implementations
3.2.5· Coding › Linear Data Structures
Stack kyun exist karta hai?
Stack KYA hai? (precise definition)
HOW implement karein — Implementation 1: Array
Index logic scratch se derive karte hain.
Empty stack se shuru karo. Koi element nahi hai, isliye natural sentinel hai top = -1 (index 0 se ek neeche).
- push ke liye: naya element agla free index pe rehna chahiye, jo hai
top + 1. Toh: pehle increment karo, phir store karo. - pop ke liye: top element
arr[top]pe hai. Use padho, phirtopko neeche karo taaki woh slot "bhul jaaye". - isEmpty: exactly tab empty jab
top == -1. - isFull (size
nka fixed array): tab full jabtop == n-1.
class ArrayStack:
def __init__(self, capacity):
self.arr = [None] * capacity
self.cap = capacity
self.top = -1 # WHY -1: empty sentinel, one below index 0
def is_empty(self): return self.top == -1
def is_full(self): return self.top == self.cap - 1
def push(self, x):
if self.is_full(): raise OverflowError("stack full")
self.top += 1 # WHY first: next free slot is top+1
self.arr[self.top] = x
def pop(self):
if self.is_empty(): raise IndexError("pop from empty")
x = self.arr[self.top] # WHY read first: top still points to it
self.arr[self.top] = None # optional: help garbage collection
self.top -= 1 # WHY: forget that slot
return x
def peek(self):
if self.is_empty(): raise IndexError("peek from empty")
return self.arr[self.top] # WHY no decrement: peek must NOT removeHOW — Implementation 2: Linked List
Scratch se derive karte hain. Ek node (data, next) hold karta hai. Stack sirf ek pointer head store karta hai.
- push(x): ek node banao jiska
nextcurrent head ko point kare, phir use naya head banao. (WHY yeh order: agar pehleheadoverwrite karo toh purani list kho jaati hai.) - pop(): top hai
head.data. Use padho, phirheadkohead.nextpe le jao. - isEmpty:
head is None.
class Node:
def __init__(self, data, nxt=None):
self.data = data
self.next = nxt
class LinkedStack:
def __init__(self):
self.head = None # head == top
self.size = 0
def is_empty(self): return self.head is None
def push(self, x):
self.head = Node(x, self.head) # WHY: new node points to old top, becomes top
self.size += 1
def pop(self):
if self.is_empty(): raise IndexError("pop from empty")
x = self.head.data
self.head = self.head.next # WHY: old head is now unreferenced -> freed
self.size -= 1
return x
def peek(self):
if self.is_empty(): raise IndexError("peek from empty")
return self.head.dataWorked examples
Common mistakes (Steel-man + fix)
Recall Feynman: 12-saal ke bachche ko samjhao
Ek tube of Pringles imagine karo. Tum sirf upar wali chip le sakte ho, aur jab chip daalo toh woh bhi upar jaati hai. Jo chip tum ne abhi daali, wahi tum abhi khaoge. Yahi stack hai. "Push" = chip daalna, "pop" = upar wali chip khaana, "peek" = upar wali chip dekhna bina khaaye. Computer iske zariye yaad karta hai "main kya kar raha tha jab mujhe interrupt kiya gaya?" — woh sabse naya kaam pehle khatam karta hai, phir wapas jaata hai.
Active recall
LIFO ka matlab kya hai aur yeh kya hota hai?
Last-In First-Out: sabse recently push kiya gaya element sabse pehle pop hota hai.
Stack ke chaar core operations kya hain?
push (top pe add karo), pop (top remove+return karo), peek/top (top bina remove kiye padho), isEmpty.
Array stack mein top = -1 se initialize kyun karte hain?
Yeh empty sentinel hai — index 0 se ek position neeche, taaki pehla push index 0 pe jaaye.
Array push mein do steps ka correct order kya hai?
Pehle top increment karo (
top += 1), phir arr[top] = x store karo.Array pop mein decrement se pehle read kyun karna chahiye?
Kyunki top abhi bhi element ko point kar raha hai; pehle decrement karne se neeche wala element return ho jaata.
pop aur peek mein kya fark hai?
pop top ko remove karke return karta hai; peek top ko return karta hai lekin stack pe rehne deta hai.
Linked-list push mein safe operation order kya hai?
Pehle naye node ka next current head pe set karo, PHIR node ko naya head banao — warna list kho/loop ho jaati hai.
Linked list ka head stack top kyun use hota hai?
Head pe insert aur delete hai bina traversal ke — exactly wahi jo stack chahta hai.
Dono array aur linked-list stack ke liye push/pop/peek ki time complexity?
har ek.
Array stack ka ek advantage aur linked-list stack ka ek advantage?
Array: cache-friendly, per-node pointer overhead nahi. Linked list: fixed capacity nahi, kabhi overflow nahi hoga.
([)] jaisi nested brackets validate karne ke liye stack (counter nahi) kyun use karein?
Stack yaad rakhta hai kaun sa bracket kis order mein khula; counter sirf count karta hai aur galat nesting ko accept kar leta.
Stack se sequence reverse kaise karte hain?
Saare elements push karo, phir sab pop karo — LIFO unhe reverse insertion order mein output karta hai.
Connections
- Queue — FIFO semantics — opposite ordering (First-In-First-Out).
- Linked List — singly linked — linked-list stack ki backbone.
- Dynamic Array / Amortized Analysis — kyun Python
listpush amortized hai. - Recursion and the Call Stack — system function calls manage karne ke liye stack use karta hai.
- Expression Evaluation — infix to postfix — stacks operator-precedence parsing power karte hain.
- Depth-First Search — DFS = graph traversal jo stack se chalti hai (explicit ya recursive).