क्यू (एब्स्ट्रैक्ट डेटा प्रकार)

Queue
Representation of a FIFO (first in, first out) queue
Time complexity in big O notation
Algorithm Average Worst case Space O(n) O(n) Search O(n) O(n) Insert O(1) O(1) Delete O(1) O(1)

अभिकलन विज्ञान में कतार संस्थाओं का एक संग्रह (अमूर्त डेटा प्रकार) है जो क्रम में बनाए रखा जाता है एवं अनुक्रम के छोर पर संस्थाओं को जोड़कर अनुक्रम के दूसरे छोर से संस्थाओं को हटाकर संशोधित करता है। सम्मेलन के अनुसार, जिस क्रम में तत्वों को जोड़ा जाता है उसके अंत को कतार का पिछला भाग कहा जाता है एवं जिस अंत में तत्वों को हटा दिया जाता है उसे कतार का अगला भाग कहा जाता है जो कि जब उपयोग किए गए शब्दों के अनुरूप होता है जिसके लिए लोग सामान या सेवाओं की प्रतीक्षा करने के लिए क्रम में लगते हैं।

कतार के पिछले भाग में तत्व जोड़ने की क्रिया को 'एनक्यू' के रूप में जाना जाता है, एवं किसी तत्व को सामने से हटाने की क्रिया को 'डीक्यू' के रूप में जाना जाता है। अन्य कार्यों की भी अनुमति दी जाती है, जिसमें अधिकांशतः पीक (डेटा प्रकार संचालन) या मुख्य संचालन सम्मलित होता है, जो अगले तत्व के मूल्य को बिना डीक्यू किए वापस करता है।

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

अभिकलन विज्ञान, परिवहन एवं संचालन अनुसंधान में कतारें सेवाएं प्रदान करती हैं जहां डेटा, ऑब्जेक्ट्स, व्यक्तियों या घटनाओं जैसी विभिन्न संस्थाओं को संग्रहीत एवं पश्चात संसाधित करने के लिए आयोजित किया जाता है। इन संदर्भों में, क्यू एक बफ़र (अभिकलन विज्ञान) का कार्य करता है। क्यू का एक अन्य उपयोग चौड़ाई-प्रथम खोज के कार्यान्वयन में है।

कतार कार्यान्वयन

सैद्धांतिक रूप से, कतार की एक विशेषता यह है कि इसकी कोई विशिष्ट क्षमता नहीं होती है। यदि कितने तत्व पहले से सम्मलित हों, एक नवीन तत्व निरंतर जोड़ा जा सकता है। यह खाली भी हो सकता है, जिस बिंदु पर एक तत्व को हटाना तब तक असंभव होगा जब तक कि एक नवीन तत्व फिर से जोड़ा नहीं जाता।

निश्चित-लंबाई सरणियों की क्षमता सीमित है, लेकिन यह सच नहीं है कि आइटम को कतार के प्रमुख की ओर कॉपी करने की आवश्यकता है। सरणी को एक बंद सर्कल में बदलने एवं उस सर्कल में सिर एवं पूंछ को अंतहीन रूप से घूमने देने की सरल चाल सरणी में संग्रहीत वस्तुओं को कभी भी स्थानांतरित करने के लिए अनावश्यक बनाती है। यदि n सरणी का बनावट है, तो अभिकलन सूचकांक modulo n सरणी को एक वृत्त में बदल देगा। यह अभी भी एक उच्च-स्तरीय भाषा में कतार बनाने का वैचारिक रूप से सबसे सरल विधि है, लेकिन यह निश्चित रूप से चीजों को थोड़ा धीमा करता है, क्योंकि सरणी सूचकांकों की तुलना शून्य एवं सरणी बनावट से की जानी चाहिए, जो कि इसमें लगने वाले समय के बराबर है। जांचें कि क्या कोई सरणी अनुक्रमणिका सीमा से बाहर है, जो कुछ भाषाएं करती हैं, लेकिन यह निश्चित रूप से त्वरित एवं गंदे कार्यान्वयन के लिए, या किसी भी उच्च-स्तरीय भाषा के लिए पसंद का विधि होगा जिसमें पॉइंटर सिंटैक्स नहीं है। समय से पहले सरणी बनावट घोषित किया जाना चाहिए, लेकिन अतिप्रवाह होने पर कुछ कार्यान्वयन सिर्फ घोषित सरणी बनावट को दोगुना कर देते हैं। ऑब्जेक्ट्स या पॉइंटर (अभिकलन प्रोग्रामिंग) के साथ अधिकांश आधुनिक भाषाएं गतिशील सूचियों के लिए पुस्तकालयों को लागू कर सकती हैं या उनके साथ आ सकती हैं। हो सकता है कि ऐसी डेटा संरचनाओं में स्मृति बाधाओं के अतिरिक्त एक निश्चित क्षमता सीमा निर्दिष्ट न हो। कतार अतिप्रवाह परिणाम एक पूर्ण कतार में एक तत्व जोड़ने की कोशिश करने से होता है एवं एक खाली कतार से एक तत्व को निकालने का प्रयास करते समय कतार अंडरफ्लो होता है।

एक बंधी हुई कतार एक निश्चित संख्या में वस्तुओं तक सीमित एक कतार है। फीफो कतारों के कई कुशल कार्यान्वयन हैं। एक कुशल कार्यान्वयन वह है जो बिग ओ नोटेशन | ओ (1) समय में संचालन-एन-क्यूइंग एवं डी-क्यूइंग- कर सकता है।

• लिंक्ड सूची
  • एक दोगुनी लिंक की गई सूची में दोनों सिरों पर ओ (1) सम्मिलन एवं विलोपन होता है, इसलिए यह कतारों के लिए एक स्वाभाविक विकल्प है।
  • नियमित रूप से एकल रूप से जुड़ी सूची में सिर्फ एक छोर पर प्रभावी प्रविष्टि एवं विलोपन होता है। चूंकि, एक छोटा संशोधन - पहले के अतिरिक्त अंतिम नोड के लिए एक पॉइंटर रखना - इसे एक कुशल कतार को लागू करने में सक्षम करेगा।
• एक संशोधित गतिशील सरणी का उपयोग करके कार्यान्वित एक डबल-एंडेड कतार

कतारें एवं प्रोग्रामिंग भाषाएं

कतारों को एक भिन्न डेटा प्रकार के रूप में लागू किया जा सकता है, या संभवतः डबल-एंडेड कतार (डीक्यू) का एक विशेष स्थिति माना जाता है एवं भिन्न से लागू नहीं किया जाता है। उदाहरण के लिए, पर्ल एवं रूबी (प्रोग्रामिंग भाषा) दोनों सिरों से एक सरणी को पुश एवं पॉप करने की अनुमति देते हैं, इसलिए कोई पुश एवं शिफ्ट फ़ंक्शंस का उपयोग किसी सूची को एन्क्यू एवं डीक्यू करने के लिए कर सकता है (या, रिवर्स में, कोई अनशिफ्ट एवं पॉप का उपयोग कर सकता है), चूंकि कुछ स्थितियों में ये संचालन कुशल नहीं हैं।

C++ की मानक टेम्पलेट लाइब्रेरी प्रदान करती है aqueueटेम्पलेट क्लास जो सिर्फ पुश/पॉप ऑपरेशंस तक ही सीमित है। J2SE5.0 के पश्चात से, Java लाइब्रेरी में a Queue इंटरफ़ेस जो कतार संचालन निर्दिष्ट करता है; कार्यान्वयन वर्ग सम्मलित हैं LinkedList एवं (J2SE 1.6 से) ArrayDeque. PHP में SplQueue क्लास एवं बीनस्टॉकड एवं जर्मनी जैसी थर्ड पार्टी लाइब्रेरी हैं।

उदाहरण

जावास्क्रिप्ट में लागू एक साधारण कतार:

class Queue {
    constructor() {
        this.items = [];
    }

    enqueue(element) {
        this.items.push(element);
    }

    dequeue() {
        return this.items.shift();
    }
}

विशुद्ध रूप से कार्यात्मक कार्यान्वयन

कतारों को विशुद्ध रूप से कार्यात्मक डेटा संरचना के रूप में भी लागू किया जा सकता है। दो कार्यान्वयन हैं। पहला ही प्राप्त करता है $O(1)$ प्रति संचालन औसतन। यही है, परिशोधित विश्लेषण का समय है $O(1)$, लेकिन व्यक्तिगत संचालन लग सकते हैं $O(n)$ जहाँ n कतार में तत्वों की संख्या है। दूसरे कार्यान्वयन को 'रीयल-टाइम क्यू' कहा जाता है एवं यह कतार को ओ (1) सबसे खराब समय में संचालन के साथ लगातार डेटा संरचना होने की अनुमति देता है। यह एक अधिक जटिल कार्यान्वयन है एवं memoization के साथ आलसी मूल्यांकन सूचियों की आवश्यकता होती है।

परिशोधित कतार

इस कतार का डेटा दो Linked_list#Singly_linked_list|singly-linked_list नाम की दो सूचियों में संग्रहीत है $f$ एवं $r$. सूची $f$ कतार के सामने का भाग रखता है। सूची $r$ शेष तत्वों (उर्फ, कतार के पीछे) को उल्टे क्रम में रखता है। के सिर पर एक नोड जोड़कर कतार के सामने सम्मिलित करना आसान है $f$. एवं यदि $r$ खाली नहीं है, के सिर पर नोड को हटाकर कतार के अंत से हटाना आसान है $r$. कब $r$ खाली है, सूची $f$ उलटा एवं सौंपा गया है $r$ एवं उसके पश्चात के सिर $r$ हटा दिया गया।

इन्सर्ट (एनक्यू) निरंतर लेता है $O(1)$ समय। निष्कासन (डेक्यू) लेता है $O(1)$ जब सूची $r$ खाली नहीं है। कब $r$ खाली है, उल्टा लेता है $O(n)$ कहाँ $n$ में तत्वों की संख्या है $f$. लेकिन, हम कह सकते हैं कि यह है $O(1)$ परिशोधित विश्लेषण समय, क्योंकि प्रत्येक तत्व में $f$ डाला जाना था एवं जब इसे डाला गया था, तब हम रिवर्स में प्रत्येक तत्व के लिए एक स्थिर लागत निर्दिष्ट कर सकते हैं।

वास्तविक समय कतार

रीयल-टाइम कतार प्राप्त होती है $O(1)$ परिशोधन के बिना, सभी कार्यों के लिए समय। यह चर्चा तकनीकी होगी, इसलिए याद रखें कि, के लिए $l$ एक सूची, $|l|$ इसकी लंबाई को दर्शाता है, कि NIL एक खाली सूची का प्रतिनिधित्व करता है एवं $\operatorname {CONS} (h,t)$ उस सूची का प्रतिनिधित्व करता है जिसका सिर एच है एवं जिसकी पूंछ टी है।

हमारी कतारों को लागू करने के लिए उपयोग की जाने वाली डेटा संरचना में तीन Linked_list#Singly_linked_list|singly-linked सूचियाँ सम्मलित हैं $(f,r,s)$ जहाँ f कतार का अगला भाग है, r विपरीत क्रम में कतार का पिछला भाग है। संरचना का अपरिवर्तनीय यह है कि एस इसके बिना एफ के पीछे है $|r|$ पहला तत्व, अर्थात् $|s|=|f|-|r|$. कतार की पूँछ $(\operatorname {CONS} (x,f),r,s)$ तब लगभग है $(f,r,s)$ एवं एक तत्व x को सम्मिलित करना $(f,r,s)$ लगभग है $(f,\operatorname {CONS} (x,r),s)$. ऐसा लगभग इसलिए कहा जाता है, क्योंकि उन दोनों परिणामों में, $|s|=|f|-|r|+1$. एक सहायक कार्य $aux$ फिर संतुष्ट होने के लिए अपरिवर्तनीय को बुलाया जाना चाहिए। इस पर निर्भर करते हुए दो स्थितियों पर विचार किया जाना चाहिए $s$ खाली सूची है, किस स्थितियों में $|r|=|f|+1$, या नहीं। औपचारिक परिभाषा है $\operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)$ एवं $\operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')$ कहाँ $f'$ f के पश्चात r का उल्टा होता है।

चलो फोन करते हैं $\operatorname {reverse} (f,r)$ फ़ंक्शन जो f के पश्चात r देता है, उलटा होता है। चलिए यह भी मान लेते हैं $|r|=|f|+1$, क्योंकि यह वह स्थिति है जब इस फ़ंक्शन को कॉल किया जाता है। अधिक त्रुटिहीन रूप से, हम एक आलसी कार्य को परिभाषित करते हैं $\operatorname {rotate} (f,r,a)$ जो इनपुट तीन सूची के रूप में लेता है $|r|=|f|+1$, एवं r का उलटा एवं a का f का संयोजन लौटाता है। तब $\operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})$. घुमाने की आगमनात्मक परिभाषा है $\operatorname {rotate} ({\text{NIL}},\operatorname {Cons} (y,{\text{NIL}}),a)=\operatorname {Cons} (y,a)$ एवं $\operatorname {rotate} (\operatorname {CONS} (x,f),\operatorname {CONS} (y,r),a)=\operatorname {Cons} (x,\operatorname {rotate} (f,r,\operatorname {CONS} (y,a)))$. इसके चलने का समय है $O(r)$, लेकिन, चूंकि आलसी मूल्यांकन का उपयोग किया जाता है, गणना तब तक विलंबित होती है जब तक कि गणना द्वारा परिणाम को मजबूर नहीं किया जाता है।

डेटा संरचना में सूची के दो उद्देश्य हैं। यह सूची काउंटर के रूप में कार्य करती है $|f|-|r|$, वास्तव में, $|f|=|r|$ यदि एवं सिर्फ यदि खाली सूची है। यह काउंटर हमें यह सुनिश्चित करने की अनुमति देता है कि पिछला कभी भी सामने की सूची से अधिक लंबा न हो। इसके अतिरिक्त, एस का उपयोग करना, जो कि एफ की पूंछ है, प्रत्येक पूंछ के समय (आलसी) सूची एफ के एक हिस्से की गणना को मजबूर करता है एवं संचालन सम्मिलित करता है। इसलिए कब $|f|=|r|$, सूची f पूरी प्रकार से मजबूर है। यदि ऐसा नहीं होता, तो f का आंतरिक प्रतिनिधित्व परिशिष्ट का... परिशिष्ट का कुछ परिशिष्ट हो सकता है, एवं बल लगाना अब एक निरंतर समय संचालन नहीं होगा।

यह भी देखें

• सर्कुलर बफर
• डबल-एंडेड कतार (डीक्यू)
• प्राथमिकता कतार
• कतार सिद्धांत
• स्टैक (अमूर्त डेटा प्रकार) - कतार के विपरीत: LIFO (लास्ट इन फ़र्स्ट आउट)

संदर्भ

सामान्यतः संदर्भ

•  This article incorporates public domain material from Black, Paul E. "Bounded queue". Dictionary of Algorithms and Data Structures.

अग्रिम पठन

• Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Dequeues, pp. 238–243.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp. 200–204.
• William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 8: Queues and Priority Queues, pp. 386–390.
• Adam Drozdek. Data Structures and Algorithms in C++, Third Edition. Thomson Course Technology, 2005. ISBN 0-534-49182-0. Chapter 4: Stacks and Queues, pp. 137–169.

बाहरी संबंध

• STL Quick Reference
• VBScript implementation of stack, queue, deque, and Red-Black Tree