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

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