Queue
Queue एक linear data structure है, जिसमें elements का insertion (add करना) एक end पर होता है, जिसे Rear कहा जाता है, और deletion (remove करना) दूसरे end से होता है, जिसे Front कहा जाता है।
यह FIFO (First In First Out) principle को follow करता है, FIFO का अर्थ है, जो element सबसे पहले insert किया गया है, वही सबसे पहले delete होगा।
Queues as ADT (ADT के रूप में Queue)
ADT का मतलब है, Abstract Data Type। यह एक mathematical model होता है, जो यह define करता है, कि data को कैसे store किया जाएगा और उस पर कौन-कौन से operations perform किए जा सकते हैं। Queue ADT हमें यह बताता है, कि एक queue में कौन-कौन से basic operations होंगे, जैसे कि enqueue, dequeue, peek (or front), और isEmpty।
- Enqueue : Queue में एक नया element insert करना।
- Dequeue : Queue से सबसे पहले element को delete करना।
- Front/Peek : Queue में सबसे पहले element को देखना (लेकिन remove नहीं करना)।
- isEmpty : Check करना कि क्या queue खाली है।
Types of Queue (प्रकार)
Queue के मुख्यतः चार प्रकार होते हैं :
- Simple Queue (Linear Queue)
- Circular Queue
- Priority Queue
- Double Ended Queue (Dequeue)
1. Simple Queue / Linear Queue
यह Simple Queue का सबसे basic प्रकार है, जो FIFO (First-In, First-Out) principle पर काम करता है।
- परिभाषा : इसमें insertion (enqueue) केवल rear end से होता है, और deletion (dequeue) केवल front end से किया जाता है।
- उदाहरण : जैसे cinema hall में टिकट लेने के लिए लगी हुई लाइन — जो व्यक्ति सबसे पहले आया, उसे सबसे पहले टिकट मिलेगी।
2. Circular Queue
Simple Queue की एक बड़ी limitation यह थी कि जब हम किसी element को dequeue (delete) करते हैं, तो queue के आगे का स्थान खाली हो जाता है, लेकिन उसे दोबारा उपयोग नहीं किया जा सकता।
इस limitation को दूर करने के लिए Circular Queue का उपयोग किया जाता है।
परिभाषा : Circular Queue वह queue है जिसमें last position फिर से first position से जुड़ जाती है, जिससे यह एक वृत्त (circle) की तरह कार्य करती है।
उदाहरण : Music Player Buffer, जहाँ songs लगातार load और play होते रहते हैं।
3. Priority Queue
यह एक विशेष प्रकार की Queue है, जहाँ FIFO principle का पालन हमेशा नहीं होता।
- परिभाषा : Priority Queue एक ऐसी Queue है, जिसमें हर element के साथ एक priority value जुड़ी होती है, और सबसे ज्यादा priority वाला element सबसे पहले process होता है।
- उदाहरण : CPU Scheduling जिस process की priority सबसे अधिक होती है, वह सबसे पहले execute होता है।
4. Dequeue / Double-Ended Queue (डबल-एंडेड क्यू)
Deque को “डेक” (Deck) भी कहते हैं। यह एक बहुत ही flexible Queue है।
- परिभाषा : यह एक ऐसी Queue है, जिसमें insertion (enqueue) और deletion (dequeue) दोनों ही operations दोनों तरफ से (front और rear) किए जा सकते हैं।
- उदाहरण : Web browser की “back” और “forward” history। आप पिछले पेज पर वापस जा सकते हैं (dequeue from front) या आगे जा सकते हैं (dequeue from rear)।
Queues Implementation
Queue को मुख्यतः दो तरीकों से implement किया जा सकता है —
- Array-based Implementation
- Linked List-based Implementation
1. Array-based Implementation
Array-based implementation में Queue को fixed size array के रूप में बनाया जाता है।
इसमें दो pointers (या indices) होते हैं :
- Front → जहाँ से element delete किया जाता है
- Rear → जहाँ element insert किया जाता है
1. Enqueue Operation : जब किसी नए element को Queue में डाला जाता है, तो उसे rear pointer की सहायता से insert किया जाता है। हर बार insertion के बाद, rear pointer को एक position आगे बढ़ा दिया जाता है।
2. Dequeue Operation : जब किसी element को Queue से हटाया जाता है, तो यह कार्य front pointer की सहायता से किया जाता है। हर deletion के बाद, front pointer को एक position आगे बढ़ा दिया जाता है।
लाभ :
- Implementation simple है।
- Memory usage contiguous (लगातार) होता है।
हानि :
- Fixed Size : Array का size पहले से ही तय होता है। अगर queue full हो जाए, तो हम और elements add नहीं कर सकते (Overflow)।
- Space Inefficiency : अगर हम elements को dequeue करते जाएँ, तो array की शुरुआत में space खाली हो जाती है, लेकिन हम उसे reuse नहीं कर पाते। इसे space wastage कहते हैं।
2. Linked List-based Implementation
इस implementation में, हम nodes का इस्तेमाल करते हैं। हर node में data और next node का address होता है।
- Enqueue Operation : नया node हमेशा rear node के बाद insert किया जाता है।
- Dequeue Operation : Node हमेशा front node से delete किया जाता है।
लाभ :
- Dynamic Size : Linked list का size fixed नहीं होता। हम जब चाहे तब नए elements add कर सकते हैं, जब तक memory उपलब्ध है।
- Efficient Space Usage : इसमें space waste नहीं होता, क्योंकि हम memory को जरूरत के हिसाब से allocate और deallocate करते हैं।
हानि :
- Implementation थोड़ी complex है।
- हर node के लिए extra memory का इस्तेमाल होता है (pointer के लिए)।
Applications of Queues
- Operating System (OS)
- Job Scheduling : OS में, CPU को बहुत सारे jobs handle करने होते हैं। इन jobs को एक queue में रखा जाता है, और CPU FIFO order में उन्हें execute करता है।
- Printer Spooling : जब आप print command देते हैं, तो आपका document सीधे printer को नहीं जाता, बल्कि एक queue में चला जाता है। Printer एक-एक करके documents को print करता है।
- Network and Data Communication
- Packet transmission : Internet पर data packets queue में store होते हैं, और routers उन्हें FIFO order में आगे भेजते हैं।
- Email Queue : जब आप कोई email भेजते हैं, तो वह एक queue में चला जाता है और mail server एक-एक करके उन्हें send करता है।
- Banking and Reservation Systems
- Online Ticket Booking (IRCTC, BookMyShow) : जब आप कोई ticket book करते हैं, तो आपकी request एक queue में जाती है और server एक-एक करके requests को process करता है।
- Payment Gateways : Online transactions भी queues में process होती हैं ताकि concurrency issues को avoid किया जा सके।
- Other Applications
- Breadth-First Search (BFS) : Graph traversal algorithm में nodes को visit करने के लिए Queue का इस्तेमाल होता है।
- Call Centers : Call centers में incoming calls को एक queue में रखा जाता है, और agents एक-एक करके calls attend करते हैं।
- Keyboard Buffer : जब आप keyboard पर बहुत तेजी से type करते हैं, तो characters एक queue में store होते हैं और फिर एक-एक करके display होते हैं।
Advantages of Queue
- Orderly Processing : Queue data को उसी क्रम में process करती है, जिस क्रम में वह enter किया गया हो। इससे fairness बनी रहती है और कोई भी element skip नहीं होता।
- Easy Task Scheduling : Queue का उपयोग CPU scheduling, printer management और network packet processing जैसे tasks में किया जाता है। यह सुनिश्चित करती है कि सभी tasks अपने turn के अनुसार process हों।
- Efficient Resource Utilization : Queue यह सुनिश्चित करती है कि कोई भी system resource idle न रहे। जैसे ही एक task पूरा होता है, अगला task तुरंत शुरू हो जाता है।
- Useful in Asynchronous Data Transfer : Queue producer-consumer systems में data transfer को manage करने के लिए उपयोग होती है।
- Dynamic Implementation Possible : अगर Queue को Linked List से implement किया जाए, तो उसका size जरूरत के अनुसार बढ़ या घट सकता है। इससे memory का अनावश्यक उपयोग नहीं होता।
- Real-Life Modeling : Queue का व्यवहार हमारे daily life systems जैसा होता है — जैसे IRCTC booking, Toll booth या Hospital tokens। इसलिए यह real-life simulations और system modeling में बहुत काम आती है।
Disadvantages of Queue
- Limited Access : Queue में data को केवल दो सिरों से ही handle किया जा सकता है —
- Insertion : Rear से
- Deletion : Front से
आप बीच के किसी element को direct access नहीं कर सकते।
- Overflow Condition : Array-based Queue में size fixed होता है। जब Queue भर जाती है और rear end तक पहुँच जाती है, तो नया element insert नहीं किया जा सकता — इसे Overflow कहते हैं।
- Underflow Condition : अगर Queue खाली है और user deletion करने की कोशिश करता है, तो Underflow error होती है।
- Memory Inefficiency : जब कुछ elements delete हो जाते हैं, तो front के खाली स्थान को reuse नहीं किया जा सकता, क्योंकि array का size fixed होता है। इस समस्या को हल करने के लिए Circular Queue का उपयोग किया जाता है।
- Complex Implementation : कुछ special queues जैसे Priority Queue, Circular Queue, और Deque (Double Ended Queue) का logic थोड़ा complex होता है, जिससे implementation कठिन हो जाता है।
- Traversal is Slow : Queue में किसी बीच के element तक पहुँचने के लिए पूरा structure traverse करना पड़ता है, जिससे searching या updating में ज़्यादा समय लगता है (O(n) time complexity)।
