Theory
यह क्यों ज़रूरी है
आपने अभी-अभी stack पर एक unit बिताई है, जहाँ सबसे नया item सबसे पहले बाहर आता है। अब राशन की दुकान, railway का 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 तीन के नाम लेता है, और exam उनके पर्यायवाची भी पूछता है।
- Insert, जिसे enqueue भी कहते हैं: rear पर item जोड़ना।
- Delete, जिसे dequeue भी कहते हैं: front का item हटाना।
- Display, जिसे traverse भी कहते हैं: front से rear तक बिना कुछ हटाए पढ़ना।
तीन सहायक साथ चलते हैं: peek front का item हटाए बिना पढ़ता है, isEmpty पूछता है कि निपटाने को कुछ बचा है या नहीं, और isFull पूछता है कि rear पर जगह बची है या नहीं।
At a glance
Stack बनाम Queue, वह सवाल जो लगभग पक्का आता है
| Aspect | 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। पाँच second लीजिए: अब 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() की जाँच बन जाती हैं, और इन्हें छोड़ देने पर marks और 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। इनमें से कम से कम तीन exam के लिए याद रखिए।
आगे आप इसे 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 से निकलिए।