Theory
બે દરવાજાવાળી હરોળ
Canteen એક parcel નું counter ઉમેરે છે. Parcels બીજા બધાની જેમ પાછળથી હરોળમાં જોડાય છે, પણ બે નવી પરિસ્થિતિ ઊભી થાય છે:
- પૈસા ભરેલી ચિઠ્ઠીવાળા delivery ના સવારને આગળથી અંદર બોલાવાય છે.
- પાછળનો ગ્રાહક રદ કરીને પોતાનું parcel લઈને ચાલ્યો જાય છે.
સાદો queue બંનેની મનાઈ કરે છે: પાછળ એક અંદરનો દરવાજો, આગળ એક બહારનો. Counter ને જોઈએ છે દરેક છેડે એક દરવાજા વાળી હરોળ.
Theory
ટ્રેનનો પરસાળ, બંને છેડા ખુલ્લા
દરેક છેડે દરવાજાવાળા ટ્રેનના પરસાળ ને વિચારો. મુસાફરો કોઈ પણ દરવાજેથી, આગળ કે પાછળ, ચડી કે ઊતરી શકે છે.
ચડવા માટે એક દરવાજો બંધ કરો અને તમને વધુ કડક પરસાળ મળે છે; સાચી જોડ બંધ કરો અને પરસાળ બરાબર સાદા queue જેવો વર્તે છે, કે stack જેવો સુધ્ધાં. Deque એ સામાન્ય પરસાળ છે; તમને પહેલેથી આવડતી રચનાઓ એ જ પરસાળ છે જેના દરવાજા બંધ કરેલા છે.
Theory
Deque, ઔપચારિક રીતે
Deque (double-ended queue) એ એવી linear રચના છે જે બંને છેડે insert અને delete ની છૂટ આપે છે. Queue ની બે ક્રિયાઓની જગ્યાએ ચાર ક્રિયાઓ આવે છે:
insertFront(x)અનેinsertRear(x)deleteFront()અનેdeleteRear()
એ સામાન્ય રીતે circular array (ગયા પાઠની વીંટી) પર બંધાય છે, કારણ કે front એ પાછળ ડગલું ભરીને વળી શકવો જોઈએ:
- rear વધે છે:
rear = (rear + 1) % SIZE - front પાછો ખસે છે:
front = (front - 1 + SIZE) % SIZE
એ + SIZE front શૂન્ય હોય ત્યારે ઋણ index સામે રક્ષણ આપે છે.
At a glance
Deque નું કુટુંબ
| પ્રકાર | Insert ની છૂટ | Delete ની છૂટ |
|---|---|---|
| Deque (બંધન વગરનું) | બંને છેડે | બંને છેડે |
| Input-restricted | ફક્ત પાછળ | બંને છેડે |
| Output-restricted | બંને છેડે | ફક્ત આગળ |
| સાદો queue (સરખામણી) | ફક્ત પાછળ | ફક્ત આગળ |
Quiz
Parcel ના counter પર, રદ થયેલાં parcels પાછળથી નીકળવાં જોઈએ, સવારો આગળથી દાખલ થઈ શકે છે, **પણ** સંચાલન નિયમ કરે છે કે parcels હંમેશા ફક્ત આગળથી જ અપાશે. આ કઈ રચના છે?
- Output-restricted deque: બંને છેડે insert, ફક્ત આગળ delete
- Input-restricted deque: ફક્ત પાછળ insert
- સાદો circular queue
- Stack, કારણ કે પાછળનો છેડો top જેવો વર્તે છે
Show the answer
Output-restricted deque: બંને છેડે insert, ફક્ત આગળ delete
Insert બંને છેડે થાય છે (સામાન્ય જોડાણ પાછળ, સવારો આગળ) જ્યારે delete ફક્ત આગળ પૂરતું મર્યાદિત છે: એ જ output-restricted deque ની વ્યાખ્યા છે. Input-restricted એનું અરીસાનું પ્રતિબિંબ છે (બંને છેડે delete, ફક્ત પાછળ insert). કયો છેડો મર્યાદિત છે, અને કઈ ક્રિયા માટે, એનું નામ આપવું એ જ આ પરીક્ષાનો પ્રશ્ન ચકાસે છે: બંધનને ક્રિયા સાથે મેળવો, શબ્દોના ક્રમ સાથે નહીં.
Think first
Front પાછળ ડગલું ભરે છે: વળી જવાનું ગણો
SIZE 5, અને deque માં અત્યારે front = 0, rear = 2 છે. એક સવારને આગળ insert કરાય છે. front = (front - 1 + SIZE) % SIZE વાપરીને, નવો front શું છે, અને ફક્ત (front - 1) % SIZE કેમ જોખમી હોત?
Show the answer
front = (0 - 1 + 5) % 5 = 4 % 5 = 4: front વળીને array ના છેલ્લા ખાના પર જાય છે, વીંટી ઊલટી દિશામાં કામ કરે છે.
+ SIZE વગર તમે (-1) % 5 ગણો છો, અને C++ માં ઋણ સંખ્યા પર modulo નું પરિણામ અમલ પ્રમાણે માથાનો દુખાવો છે (સામાન્ય રીતે -1): અમાન્ય index. + SIZE વળી જતાં પહેલાં ગણિતને ધન રાખે છે. પરીક્ષાઓ સૂત્ર માટે marks આપે છે; interviews શા માટે એ જાણવા માટે.
Watch out
Deque એ ઓજારપેટી છે, શિસ્ત નહીં
Queue એ FIFO નું વચન આપે છે; stack એ LIFO નું. Deque એકેયનું વચન આપતું નથી: સેવાનો ક્રમ સાવ એના પર આધારિત છે કે તમારો code ચારમાંથી કઈ ક્રિયાઓ બોલાવે છે.
ફક્ત insertRear વત્તા deleteFront વાપરો, અને એ queue જ છે. ફક્ત insertRear વત્તા deleteRear વાપરો, અને એ stack તરીકે વર્તે છે. Deque બંનેને કેવી રીતે સામાન્ય બનાવે છે એ પુછાય ત્યારે પરીક્ષામાં આ બે વાક્ય લખો, એ સહેલા marks છે.
Theory
બંને દરવાજા પોતાની કિંમત ક્યાં વસૂલે છે
મર્યાદાવાળો undo નો ઇતિહાસ: નવી ક્રિયાઓ એક છેડે push થાય છે; ઇતિહાસ ભરાય ત્યારે સૌથી જૂની બીજા છેડેથી ખરી પડે છે. Palindrome ની ચકાસણી: શબ્દ ભરો, deleteFront() ને deleteRear() સામે સરખાવો જ્યાં સુધી એ મળે નહીં. Coding ના તબક્કામાં sliding-window ની સમસ્યાઓ પણ એ જ કારણે deques પર ટેકે છે: તાજો data એક દરવાજેથી અંદર, વાસી data બીજેથી બહાર.
Summary
Key takeaways
- Deque: બંને છેડે insert અને delete; queue ની બે ક્રિયાઓની જગ્યાએ ચાર.
- Circular array પર બંધાય છે; ઋણ index ટાળવા front (front - 1 + SIZE) % SIZE થી પાછો ખસે છે.
- Input-restricted: ફક્ત પાછળ insert. Output-restricted: ફક્ત આગળ delete.
- ક્રિયાઓની જોડ પસંદ કરવાથી deque એ queue કે stack તરીકે વર્તે છે: એ બંનેને સામાન્ય બનાવે છે.
- ઉપયોગ: મર્યાદાવાળો undo નો ઇતિહાસ, palindrome ની ચકાસણી, sliding windows.
- Memory hook: બંને દરવાજા ખુલ્લા હોય એવો ટ્રેનનો પરસાળ.