Theory
આ શું કામ મહત્વનું છે
તમે હમણાં જ stack પર એક unit પૂરી કરી, જ્યાં સૌથી નવો item સૌથી પહેલો બહાર આવે છે. હવે રેશનની દુકાન, રેલવેનું ticket counter, કે એક જ printer પર ઊભેલાં પાંચ print jobs વિચારો. એમાંથી કોઈ પણ જો સૌથી નવા માણસને પહેલો પતાવવા માંડે, તો એક મિનિટમાં ઝઘડો થાય.
મોટા ભાગની સાચી systems ને ઊંધો નિયમ જોઈએ છે, અને એ નિયમનું પોતાનું data structure છે: queue.
Theory
Counter ની token line
તમે bank માં જાઓ છો, token 47 લો છો, અને line ની પાછળ ઊભા રહો છો. Clerk line ના front ને બોલાવે છે. વચ્ચેથી નહીં, પાછળથી નહીં.
નવા લોકો rear પર જોડાય છે, પતી ગયેલા લોકો front પરથી નીકળે છે. બે જુદા છેડા, દરેકનું બરાબર એક કામ. જે પહેલો આવ્યો એ જ પહેલો પતે: FIFO, First In, First Out.
Theory
મૂળ વિચાર
Queue એ linear list છે જેના પર બે બંધન છે:
- Insertion ફક્ત એક છેડે, જેને rear કહે છે.
- Deletion ફક્ત બીજા છેડે, જેને front કહે છે.
આ એક જ ભેદ એને stack થી જુદી પાડે છે. Stack એક છેડે કામ કરે છે, એટલે એ LIFO છે. Queue બે છેડે કામ કરે છે, એટલે એ FIFO છે.
Theory
એને જુઓ
Size 5 ની queue જેમાં ત્રણ tokens છે, array તરીકે દોરેલી:
front rear
↓ ↓
[ 10 ][ 20 ][ 30 ][ ][ ]
0 1 2 3 4
એક delete કરો એટલે front ખસીને index 1 પર આવે, હવે 20 front પર. એક insert કરો એટલે rear ખસીને index 3 પર આવે. બંને છેડા પોતપોતાની ચાલે ચાલે છે, અને બંને ફક્ત જમણી બાજુ જ આગળ વધે છે.
Theory
પાયાનાં operations
તમારો syllabus ત્રણનાં નામ આપે છે, અને પરીક્ષા એમના પર્યાય પણ પૂછે છે.
- Insert, જેને enqueue પણ કહે છે: rear પર item ઉમેરવો.
- Delete, જેને dequeue પણ કહે છે: front નો item કાઢવો.
- Display, જેને traverse પણ કહે છે: front થી rear સુધી કશું કાઢ્યા વગર વાંચવું.
ત્રણ મદદગાર સાથે ચાલે છે: peek front નો item કાઢ્યા વગર વાંચે છે, isEmpty પૂછે છે કે પતાવવા જેવું કશું બચ્યું છે કે નહીં, અને isFull પૂછે છે કે rear પર જગ્યા બચી છે કે નહીં.
At a glance
Stack સામે Queue, લગભગ પાકો આવતો સવાલ
| પાસું | Stack | Queue |
|---|---|---|
| ક્રમ | LIFO, last in first out | FIFO, first in first out |
| કેટલા છેડા | એક, top | બે, front અને rear |
| Insert | push, top પર | insert કે enqueue, rear પર |
| Delete | pop, top પરથી | delete કે dequeue, front પરથી |
| રોજિંદો દાખલો | Undo, browser back | Ticket counter, printer |
Think first
Line ને trace કરો
ખાલી queue થી શરૂ કરો. Insert 10, insert 20, insert 30. હવે બે વાર delete કરો, પછી insert 40. પાંચ સેકન્ડ લો: હવે front પર શું છે અને rear પર શું?
Show the answer
બંને deletions એ 10 અને પછી 20 કાઢ્યા, એટલે કે બે સૌથી જૂના items, કારણ કે delete હંમેશા front પરથી થાય છે.
બાકી રહ્યા 30 અને 40, એટલે front પર 30 અને rear પર 40. જો તમે કહ્યું હોય કે 30 અને 20 નીકળ્યા, તો તમે એને stack ની જેમ trace કરી: stack જે છેડે ઉમેરે એ જ છેડેથી કાઢે છે, queue ક્યારેય નહીં.
Watch out
Overflow અને underflow
Overflow એટલે એવી queue માં insert જેના rear પર જગ્યા જ બચી નથી. Underflow એટલે ખાલી queue માંથી delete, અને આ જ તપાસ students ભૂલી જાય છે.
દરેક delete પહેલાં પૂછો કે queue ખાલી તો નથી ને. દરેક insert પહેલાં પૂછો કે ભરેલી તો નથી ને. Code માં આ isEmpty() અને isFull() ની તપાસ બને છે, અને એને છોડી દેવાથી ગુણ અને program બંને પડે છે.
Quiz
એક queue માં front થી rear સુધી 10, 20, 30 છે. તમે એક delete કરો છો, પછી 40 નો એક insert. હવે front થી rear સુધી queue માં શું છે?
- 20, 30, 40
- 10, 20, 40
- 40, 20, 30
- 10, 20, 30, 40
Show the answer
20, 30, 40
Delete front પરથી થાય છે, એટલે 10 નીકળી જાય. Insert rear પર થાય છે, એટલે 40 આવીને 30 પછી ગોઠવાય. Front થી rear સુધી એ થયું 20, 30, 40. "10, 20, 40" ત્યારે મળે જ્યારે તમે rear પરથી delete કરો, જે stack ની ટેવ છે. "40, 20, 30" ખોટા છેડે insert કરે છે. "10, 20, 30, 40" તો delete થયો જ નથી એમ માની લે છે.
Formula
Queue ક્યાં ક્યાં દેખાય છે
એક printer પર ઊભેલાં print jobs, round robin scheduling માં CPU ની રાહ જોતી processes, keyboard buffer માં રોકાયેલી keystrokes, web server પર ઊભેલી requests, અને graphs માં breadth first search. પરીક્ષા માટે એમાંથી ઓછામાં ઓછા ત્રણ યાદ રાખો.
હવે પછી તમે એને array અને બે indexes થી બનાવશો, અને એની ખામી પણ મળશે: rear છેલ્લા slot પર પહોંચે કે તરત queue પોતાને full કહી દે છે, જ્યારે front બાજુ delete થઈ ગયેલા slots ખાલી પડ્યા હોય છે. Circular queue આ જ ખામી સુધારવા માટે છે.
Summary
Key takeaways
- Queue એ બે છેડાવાળી linear list છે: insert rear પર, delete front પરથી.
- એનાથી FIFO ક્રમ બને છે, first in first out, stack ના LIFO થી ઊંધો.
- પાયાનાં operations: insert (enqueue), delete (dequeue) અને display (traverse), સાથે peek, isEmpty અને isFull.
- Overflow એટલે ભરેલી queue માં insert; underflow એટલે ખાલી queue માંથી delete.
- વપરાશ: printer spooling, CPU scheduling, keyboard buffer, web server requests, breadth first search.
- યાદ રાખવાની રીત: rear પર જોડાઓ, front પરથી નીકળો.