Theory
दो doors वाली line
Canteen एक parcel counter जोड़ता है। Parcels सबकी तरह rear पर line में जुड़ते हैं, पर दो नई situations दिखती हैं:
- एक paid slip वाला delivery rider front पर अंदर बुलाया जाता है।
- rear पर एक customer cancel करके अपना parcel लेकर चला जाता है।
Simple queue दोनों मना करता है: rear पर एक door अंदर के लिए, front पर एक door बाहर के लिए। Counter को हर end पर एक door वाली line चाहिए।
Theory
एक train corridor, दोनों ends खुले
एक train corridor की कल्पना कीजिए जिसके हर end पर एक door है। Passengers किसी भी door से board या alight कर सकते हैं, front या rear।
Boarding के लिए एक door lock कीजिए और आपको एक stricter corridor मिलता है; सही pair lock कीजिए और corridor बिल्कुल plain queue की तरह व्यवहार करता है, या यहाँ तक कि एक stack की तरह। Deque general corridor है; जो structures आप पहले से जानते हैं वे बस इसी corridor के bolted doors हैं।
Theory
Deque, formally
एक deque (double-ended queue) एक linear structure है जो दोनों ends पर insertion और deletion allow करता है। चार operations queue के दो की जगह लेते हैं:
insertFront(x)औरinsertRear(x)deleteFront()औरdeleteRear()
यह आमतौर पर एक circular array पर बनाया जाता है (पिछले lesson की ring), क्योंकि front को पीछे step करके wrap करने में सक्षम होना चाहिए:
- rear बढ़ता है:
rear = (rear + 1) % SIZE - front पीछे हटता है:
front = (front - 1 + SIZE) % SIZE
वह + SIZE front के 0 होने पर एक negative index से बचाता है।
At a glance
Deque family
| Variant | Insert allowed | Delete allowed |
|---|---|---|
| Deque (unrestricted) | दोनों ends | दोनों ends |
| Input-restricted | सिर्फ़ rear | दोनों ends |
| Output-restricted | दोनों ends | सिर्फ़ front |
| Plain queue (compare) | सिर्फ़ rear | सिर्फ़ front |
Quiz
Parcel counter पर, cancellations rear से जानी चाहिए, riders front पर enter कर सकते हैं, पर management rule है कि parcels सिर्फ़ front पर ही दिए जा सकते हैं। यह कौन सी structure है?
- Output-restricted deque: दोनों ends पर insertion, सिर्फ़ front पर deletion
- Input-restricted deque: सिर्फ़ rear पर insertion
- एक plain circular queue
- एक stack, क्योंकि rear एक top की तरह काम करता है
Show the answer
Output-restricted deque: दोनों ends पर insertion, सिर्फ़ front पर deletion
Insertions दोनों ends पर होते हैं (regular joins rear पर, riders front पर) जबकि deletion front तक restricted है: एक output-restricted deque की definition। Input-restricted इसका mirror है (both-end deletes, rear-only inserts)। कौन सा END restricted है, और किस operation के लिए, नाम देना बिल्कुल वह है जो यह exam सवाल test करता है: restriction को operation से match कीजिए, word order से नहीं।
Think first
Front पीछे step करता है: wrap compute कीजिए
SIZE 5, और deque के पास अभी front = 0, rear = 2 है। एक rider FRONT पर insert होता है। front = (front - 1 + SIZE) % SIZE इस्तेमाल करते हुए, नया front क्या है, और सिर्फ़ (front - 1) % SIZE क्यों ख़तरनाक होता?
Show the answer
front = (0 - 1 + 5) % 5 = 4 % 5 = 4: front array के last cell पर wrap करता है, ring reverse में काम करते हुए।
+ SIZE के बिना, आप (-1) % 5 compute करते हैं, और C++ में एक negative number पर modulo का result implementation-headachy है (आमतौर पर -1): एक invalid index। + SIZE wrap से पहले arithmetic को positive रखता है। Exams formula के marks देते हैं; interviews यह जानने के marks देते हैं क्यों।
Watch out
Deque एक toolbox है, एक discipline नहीं
एक queue FIFO promise करता है; एक stack LIFO promise करता है। एक deque किसी का भी promise नहीं करता: service का order पूरी तरह इस पर depend करता है कि आपका code चार operations में से कौन से call करता है।
सिर्फ़ insertRear + deleteFront इस्तेमाल कीजिए, और यह एक queue IS है। सिर्फ़ insertRear + deleteRear इस्तेमाल कीजिए, और यह एक stack की तरह व्यवहार करता है। पूछे जाने पर कि deque दोनों को कैसे generalize करता है, exam में वह pair of sentences लिखिए, यह easy marks के लायक़ है।
Theory
जहाँ दोनों doors अपना काम कमाते हैं
एक limit वाली undo history: नए actions एक end पर push होते हैं; जब history full होती है, सबसे पुराना दूसरे end से गिर जाता है। Palindrome checking: word load कीजिए, जब तक वे मिलें deleteFront() को deleteRear() से compare कीजिए। Coding rounds में sliding-window problems इसी कारण deques पर टिकते हैं: एक door से fresh data, दूसरे door से expired data बाहर।
Summary
Key takeaways
- Deque: दोनों ends पर insertion AND deletion; चार operations queue के दो की जगह लेते हैं।
- एक circular array पर built; negative indexes से बचने के लिए front (front - 1 + SIZE) % SIZE से पीछे हटता है।
- Input-restricted: सिर्फ़ rear पर insert। Output-restricted: सिर्फ़ front पर delete।
- Operation pairs चुनना एक deque को queue या stack की तरह act करवाता है: यह दोनों को generalize करता है।
- Applications: capped undo history, palindrome checks, sliding windows।
- Memory hook: दोनों doors खुले वाला एक train corridor।