3.2.8
Intuition Ek-sentence mein pictureEk deque aisa queue hai jise bhool gaya ki kaunsa end front tha . Tum dono ends se O ( 1 ) aur queue ki tarah behave karta hai.
Deque (pronounced "deck", short for D ouble-E nded QUE ue) ek linear data structure hai jo insertion aur deletion ko dono ends pe support karta hai — front aur rear — har ek O ( 1 )
Chaar core operations:
Operation
Matlab
push_front(x)x ko front pe add karo
push_back(x)x ko rear pe add karo
pop_front()front element ko remove karke return karo
pop_back()rear element ko remove karke return karo
front() / back()bina remove kiye peek karo
Intuition Yeh stack aur queue ko generalize kyun karta hai
Agar sirf push_back + pop_back use karo → tumhe stack milta hai (LIFO).
Agar sirf push_back + pop_front use karo → tumhe queue milta hai (FIFO).
Toh deque superset hai: har stack aur har queue ek restricted deque hai.
Tum O ( 1 ) dekhna hoga ki har implementation usse kyun deta hai.
Doubly linked list kyun?
Back se O ( 1 ) O ( n ) prev pointer yeh fix karta hai — har node dono neighbours ko jaanta hai.
HEAD <-> [a] <-> [b] <-> [c] <-> TAIL
push_front: node banao, HEAD sentinel ke baad splice karo → O ( 1 ) pop_back: TAIL.prev directly last node deta hai → O ( 1 )
Yeh kyun kaam karta hai: har end-operation sirf 2–3 pointers ko touch karta hai, size n
Ek normal array back pe great hai lekin front pe terrible (push_front sab kuch shift karta hai = O ( n ) ek pointer move karo iske bajaye . Array ko ek ring ki tarah treat karo taaki front left mein "edge ke bahar" ja sake aur doosri side se wrap ho jaye.
front index, size, capacity C rakho. Indices modular arithmetic se wrap hote hain:
Jab size == C, capacity double karo aur copy karo — amortized O ( 1 ) n O ( n )
Common mistake Steel-man: "Bas ek plain array use karo aur shift karo."Kyun sahi lagta hai: arrays simple hain, indexing O ( 1 ) theek lagte hain .
Kyun galat hai: push_front tab har element ko right shift karta hai → O ( n ) n O ( n 2 ) point hi O ( 1 ) Fix: circular buffer use karo (pointers move karo, data nahi) ya doubly linked list.
Worked example Killer application: Sliding Window MaximumEk array mein size k O ( nk ) indices store karta hai, isse O ( n )
Deque kyun? Naye elements back se enter karte hain; window se bahar ho chuke purane elements front se nikalte hain; chhote useless elements back se pop hote hain. Teen alag ends/operations → sirf deque hi sab kuch O ( 1 )
Doosre 20%-jo-80%-cover-karte-hain uses:
Ek hi structure mein stack aur queue dono ka behavior (undo + redo).
Palindrome check : pop_front() vs pop_back() compare karo jab tak cross na ho jaayein.0–1 BFS : weight 0 wale edges → push_front, weight 1 wale → push_back (deque priority queue ko replace karta hai).Steal-work scheduling (parallel runtimes mein work-stealing deques).
Worked example Example 1 — Operations trace karoKhaali shuru karo. Apply karo: push_back(5), push_front(3), push_back(8), pop_front(), pop_back().
Step
Action
Deque (front→back)
Returns
1
push_back(5)
[5]
—
2
push_front(3)
[3, 5]
—
3
push_back(8)
[3, 5, 8]
—
4
pop_front()
[5, 8]
3
5
pop_back()
[5]
8
Step 2 kyun? push_front sab kuch se pehle insert karta hai, toh 3 5 ke left mein aata hai.
Step 4 mein 3 kyun return hota hai? Front sabse leftmost element hota hai.
Worked example Example 2 — Circular array mechanics,C = 5 front=2, size=2, slots: index2=A, index3=B.
Ab push_front(X):
naya front = ( 2 − 1 + 5 ) mod 5 = 6 mod 5 = 1
X ko index 1 pe store karo, size→3.
Array ab (_=empty): [_ , X, A, B, _], logical order = X, A, B.
+ 5 2 − 1 = 1 front 0 − 1 4 + C
Worked example Example 3 — Palindrome checkWord R A C E C A R ek deque mein. Loop jab tak size > 1:
pop_front() ko pop_back() se compare karo. R=R, A=A, C=C → middle E bachi → palindrome.
Deque kyun? Tumhe dono ends se simultaneously peel karna hai — exactly iska strength hai.
Recall Feynman: ek 12-saal ke bacche ko explain karoEk line of kids imagine karo jo haath pakde khade hain. Normally ek naya bachcha end mein aata hai aur front wala bachcha pehle jaata hai — yeh queue hai. Deque ek magic line hai jahan ek bachcha front YA back mein aa sakta hai, aur front YA back se ja sakta hai, instantly. Beech mein kisi ko bhi shuffle nahi karna padta. Bas itna hi hai — ek line jise tum dono taraf se poke kar sakte ho.
DECK of cards : tum top aur bottom dono se deal karte ho — dono ends, super fast. "Deque = ek DECK jise tum kisi bhi side se pakad sakte ho."
Deque kaunse dono ends pe operate karta hai, aur kitne time mein?
Linked-list version doubly linked kyun hona chahiye?
Circular buffer mein front ko left move karne ka formula likhо.
Deque ke saath sliding-window-max O ( n )
"Deque" ka full form kya hai aur ise kaise pronounce karte hain? Double-Ended Queue; pronounced "deck".
Chaar core deque operations kaunse hain? push_front, push_back, pop_front, pop_back (har ek O(1)).
Deque stack aur queue dono ko generalize kaise karta hai? push_back+pop_back tak restrict karo → stack (LIFO); push_back+pop_front → queue (FIFO).
O(1) deque ke liye doubly linked list kyun chahiye? pop_back ko last node se pehle wala node instantly chahiye; prev pointer bina head se chale deta hai.
Capacity C ke circular array mein push_front ke liye front ko left move karne ka formula kya hai? front = (front - 1 + C) mod C; +C negative indices ko rokta hai.
Circular deque mein front se k-wein element ka index? (front + k) mod C.
Plain array + shifting se deque implement kyun nahi karna chahiye? push_front shifting ki wajah se O(n) ban jaata hai; O(1) goal ko defeat karta hai. Circular buffer use karo iske bajaye.
Deque ka killer use case aur uski complexity? Sliding window maximum O(n) mein, useful indices ko decreasing order mein rakho.
Deque 0-1 BFS kaise solve karta hai? weight-0 edges push_front, weight-1 edges push_back; deque priority queue ko replace karta hai.
Dynamic-array deque mein push ka amortized cost kya hai aur kyun? O(1); kabhi kabhi doubling+copy O(n) cost karta hai lekin n pushes mein spread hoke average O(1) deta hai.
push/pop front and back O 1
