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

पंक्ति
एक FIFO (फर्स्ट इन, फर्स्ट आउट) कतार का प्रतिनिधित्व
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)

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

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

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

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

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

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

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

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

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

कतारें एवं योजनािंग भाषाएं

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

सी ++ की मानक क्रमादेश कतार संग्रह प्रदान करता है जो सिर्फ प्रेरणा/सहसा संचालन तक ही सीमित है। जेटूएसईफाइव .शून्य के पश्चात, जावा क्रमादेश संग्रह में कतारअंतराफलक जो कतार संचालन निर्दिष्ट करता है; कार्यान्वयन वर्ग सम्मलित हैं सूची.html श्रृंखलित सूची एवं (जेटूएसईएक.छह से) समूह विपंक्ति.html शृंखला समूह विपंक्ति. पीएचपी में [./Http://www.php.net/manual/en/class.splqueue.php एसक्यूएल शृंखला समूह] वर्ग एवंजर्मनी जैसी तृतीय पक्ष क्रमादेश का संग्रह हैं।

उदाहरण

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

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

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

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

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

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

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

इस कतार का डेटा दो श्रृंखलित सूची नाम की दो सूचियों में संग्रहीत है $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)$ उस सूची का प्रतिनिधित्व करता है जिसका सिर एच है एवं जिसकी पूंछ टी है।

हमारी कतारों को लागू करने के लिए उपयोग की जाने वाली डेटा संरचना में तीन श्रृंखलित सूचियाँ सम्मलित हैं $(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 का आंतरिक प्रतिनिधित्व का कुछ परिशिष्ट हो सकता है, एवं बल लगाना अब एक निरंतर समय संचालन नहीं होता है।

यह भी देखें

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

संदर्भ

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

•  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