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

पंक्ति
एक 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();
    }
}

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

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

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

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

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

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

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

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

चलो फोन करते हैं $\operatorname {reverse} (f,r)$ फल जो ऍफ़ के पश्चात आर देता है, विपरीत होता है। यह मान लेते हैं $|r|=|f|+1$, क्योंकि यह वह स्थिति है जब इस फल को कॉल किया जाता है। अधिक त्रुटिहीन रूप से, हम एक मंद कार्य को परिभाषित करते हैं $\operatorname {rotate} (f,r,a)$ जो निविष्ट तीन सूची के रूप में लेता है $|r|=|f|+1$, एवं आर का विपरीत एवं ए का ऍफ़ का संयोजन लौटाता है। तब $\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 पूरी प्रकार से असहाय है। यदि ऐसा नहीं होता, तो ऍफ़ का आंतरिक प्रतिनिधित्व का कुछ परिशिष्ट हो सकता है, एवं बल लगाना अब एक निरंतर समय संचालन नहीं होता है।

यह भी देखें

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

संदर्भ

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

•  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