पाठ · #4 / 11

क़तार (Queues)

FIFO — हर बार न्यायसंगत क्रम

Queue · FIFO

head

tail

init

token

खुद आज़माएँ: बेल्ट पर enqueue/dequeue कीजिए। ring buffer पर स्विच करके देखिए कि कैसे सर्कुलर इंडेक्सिंग तय मेमोरी को दोबारा इस्तेमाल करती है — कभी कोई खिसकाव नहीं।

यह क्यों मायने रखता है

क़तारें प्रतीक्षा-पंक्तियों, कार्य-शेड्यूलिंग और breadth-first खोज को मॉडल करती हैं। जहाँ भी पहुँचने का क्रम मायने रखता हो, वहाँ आपको एक क़तार चाहिए। ये ऑपरेटिंग सिस्टम, नेटवर्किंग और ग्राफ़ एल्गोरिथ्म की बुनियाद हैं।

मूल विचार

किसी कॉफ़ी शॉप की पंक्ति को सोचिए। पंक्ति में सबसे पहले खड़े व्यक्ति को सबसे पहले सेवा मिलती है। नए ग्राहक पीछे से जुड़ते हैं।

सबसे पहले अंदर, सबसे पहले बाहर (First In, First Out — FIFO)।

जहाँ स्टैक undo और backtracking के बारे में हैं, वहीं क़तारें निष्पक्षता और क्रम के बारे में हैं:

प्रिंट क़तार: दस्तावेज़ उसी क्रम में छपते हैं जिस क्रम में भेजे गए
कार्य शेड्यूलर: प्रक्रियाएँ पहुँचने के क्रम में चलती हैं (round-robin)
BFS: नोडों को स्तर-दर-स्तर खोजना, पहले खोजे गए नोडों को पहले देखना

Enqueue (पीछे जोड़ना) और dequeue (आगे से हटाना), दोनों O(1) हैं।

मुख्य बातें

Enqueue और dequeue O(1) हैं
FIFO क्रम — सबसे पहले अंदर, सबसे पहले बाहर
BFS, कार्य शेड्यूलिंग, बफ़रिंग में इस्तेमाल
सर्कुलर बफ़र एक कुशल ऐरे-आधारित इम्प्लीमेंटेशन है

और गहराई में

दो-सिरों वाली क़तारें (deques) दोनों सिरों पर डालने/हटाने की छूट देती हैं — sliding-window एल्गोरिथ्म और "हर k आकार की विंडो में अधिकतम" को कुल O(n) में निकालने वाली monotonic-deque तरकीब के लिए उपयोगी। प्राथमिकता क़तारें (priority queues, हीप वाले पाठ में) "अन्यायपूर्ण" क़तारें हैं जहाँ महत्व पहुँचने के क्रम पर भारी पड़ता है — इस पाठ में बस एक घुंडी और घुमा दीजिए, और आपको एक हीप मिल जाती है। सर्कुलर बफ़र तय-आकार के ऐरे में लपेटकर (wrap around) क़तारों को कुशलता से लागू करते हैं।

असल दुनिया में

ROS टॉपिक क़तारें। ROS (Robot Operating System) में हर publisher प्रति टॉपिक एक तय-क्षमता वाली ring-buffer क़तार में लिखता है। जब subscriber रफ़्तार नहीं रख पाते, तो सबसे पुराने संदेश छोड़ दिए जाते हैं। उस क़तार की गहराई ट्यून करना उन पहली चीज़ों में से एक है जो कोई रोबोटिक्स इंजीनियर सीखता है।
मैसेज ब्रोकर (Kafka, RabbitMQ, NATS, Redis Streams)। सभी क़तार के अमूर्तन (abstraction) पर बने हैं, ऊपर से persistence और replication की परतें चढ़ी हुई। उपभोक्ता सिर (head) से पढ़ता है; उत्पादक पुच्छ (tail) पर जोड़ते हैं।
किसी रोबोट के नक़्शे पर BFS frontier। ग्राफ़ वाले पाठ का grid मोड इसे सीधे दिखाता है — wavefront path planning एक क़तार के साथ BFS ही है, और ज़्यादातर occupancy-grid नियोजक (A*, JPS, theta*) इसी तरह शुरुआत करते हैं।
प्रिंट स्पूलर, OS शेड्यूलर run queue, वेब-सर्वर request queue। जहाँ भी नीति "पहले आओ, पहले पाओ" हो।

ring buffer `O(1)` amortized क्यों है — हालाँकि आकार-परिवर्तन `O(n)` है

एक भोली ऐरे-आधारित क़तार आगे से dequeue करते समय बाक़ी बचे सारे n तत्वों को बाएँ खिसका देती है — O(n)। ring buffer उन modular इंडेक्सों से इससे बच निकलता है जो आपने डेमो में देखे: front और rear क्षमता के modulo में आगे बढ़ते हैं, जिससे भरने को कोई अंतराल नहीं बचता।

पर जब ring भर जाता है तब क्या होता है? आप दुगुने आकार का नया बफ़र बनाकर कॉपी करते हैं। वह O(n) है — वही आकार-परिवर्तन तरकीब जो ऐरे दुगुना करने का प्रमाण इस्तेमाल करता है। n enqueue पर कुल काम 2n − 1 होता है, इसलिए प्रति-ऑपरेशन यह O(1) amortized है। दुगुना किए बिना — मान लीजिए आप हर बार एक स्थिर मात्रा से बढ़ते — तो कुल काम फूलकर O(n²) हो जाता।

यह दूसरी बार है जब आपने दुगुना करने का पैटर्न देखा है; आप इसे फिर देखेंगे हैश-टेबल rehashing में, और परोक्ष रूप से हीप निर्माण में। आकार पहचानिए: "कभी-कभार होने वाला महँगा ऑपरेशन, जिसकी क़ीमत पहले के कई सस्तों ने चुका दी" — यही एक वाक्य में amortized विश्लेषण है।

गणितीय ब्यौरा

Time Complexity: Enqueue: O(1); Dequeue: O(1); Peek front: O(1); Search: O(n)
Circular Buffer: front = (front + 1) mod capacity; rear = (rear + 1) mod capacity

क्रियान्वयन (Implementation)

VecDeque से क़तार

use std::collections::VecDeque;

let mut queue = VecDeque::new();

queue.push_back(1);  // Enqueue
queue.push_back(2);
queue.push_back(3);  // Queue: [1, 2, 3]

let front = queue.pop_front();  // Returns Some(1)
// Queue is now [2, 3]

चिर-परिचित उपयोग

BFS ग्राफ़ traversal
कार्य/जॉब शेड्यूलिंग
प्रिंट स्पूलर
स्ट्रीमिंग डेटा के लिए बफ़र

अभ्यास

तीन क़तार सवाल, हर एक FIFO अनुशासन के अलग पहलू पर टिका है:

Queue from Two Stacks — मध्यम · आलसी निकासी (lazy drain) से दो LIFO से FIFO का स्वाँग (amortized O(1))
Sliding Window Maximum — कठिन · monotonic-deque पैटर्न, O(n log k) के बजाय O(n)
Bounded Ring Buffer (Robotics) — मध्यम · तय-क्षमता वाली FIFO जिस पर हर ROS टॉपिक और UART ड्राइवर बना है

→ सभी अभ्यास सवाल देखें

🎢 क़तार (Queues)