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

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

Revision as of 21:38, 1 March 2023

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

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

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

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

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

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

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

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

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

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

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

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();
    }
}

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

कतारों को विशुद्ध रूप से कार्यात्मक डेटा संरचना के रूप में भी लागू किया जा सकता है।^[3] दो कार्यान्वयन हैं। पहला ही प्राप्त करता है $O(1)$ प्रति संचालन औसतन। यही है, परिशोधित विश्लेषण का समय है $O(1)$ , लेकिन व्यक्तिगत संचालन लग सकते हैं $O(n)$ जहाँ n कतार में तत्वों की संख्या है। दूसरे कार्यान्वयन को 'रीयल-टाइम क्यू' कहा जाता है^[4] एवं यह कतार को ओ (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 (लास्ट इन फ़र्स्ट आउट)

संदर्भ

↑ "Queue (Java Platform SE 7)". Docs.oracle.com. 2014-03-26. Retrieved 2014-05-22.
↑ "Array (Ruby 3.1)". 2021-12-25. Retrieved 2022-05-11.
↑ Okasaki, Chris. "विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं" (PDF).
↑ Hood, Robert; Melville, Robert (November 1981). "शुद्ध लिस्प में रीयल-टाइम कतार संचालन". Information Processing Letters. 13 (2): 50–54. doi:10.1016/0020-0190(81)90030-2. hdl:1813/6273.

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

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.

बाहरी संबंध

[1] "Queue (Java Platform SE 7)". Docs.oracle.com. 2014-03-26. Retrieved 2014-05-22.

[2] "Array (Ruby 3.1)". 2021-12-25. Retrieved 2022-05-11.

[3] Okasaki, Chris. "विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं" (PDF).

[4] Hood, Robert; Melville, Robert (November 1981). "शुद्ध लिस्प में रीयल-टाइम कतार संचालन". Information Processing Letters. 13 (2): 50–54. doi:10.1016/0020-0190(81)90030-2. hdl:1813/6273.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-{{short description|Abstract data type}}
-{{More footnotes|date=January 2014}}
 {{Infobox data structure
 |name=Queue
@@ Line 15: / Line 12: @@
 |delete_worst={{math|O(1)}}
 }}
-[[कंप्यूटर विज्ञान]] में, एक कतार संस्थाओं का एक संग्रह (अमूर्त डेटा प्रकार) है जो एक क्रम में बनाए रखा जाता है और अनुक्रम के एक छोर पर संस्थाओं को जोड़कर और अनुक्रम के दूसरे छोर से संस्थाओं को हटाकर संशोधित किया जा सकता है। परिपाटी के अनुसार, जिस क्रम में तत्वों को जोड़ा जाता है, उसके अंत को कतार का पिछला, पूंछ या पिछला भाग कहा जाता है, और जिस अंत में तत्वों को हटा दिया जाता है, उसे कतार का सिर या अगला भाग कहा जाता है, जो कि जब इस्तेमाल किए गए शब्दों के अनुरूप होता है। लोग सामान या सेवाओं की प्रतीक्षा करने के लिए लाइन में लगते हैं।
+[[Index.php?title=अभिकलन विज्ञान|अभिकलन विज्ञान]] में कतार संस्थाओं का एक संग्रह (अमूर्त डेटा प्रकार) है जो क्रम में बनाए रखा जाता है एवं अनुक्रम के छोर पर संस्थाओं को जोड़कर अनुक्रम के दूसरे छोर से संस्थाओं को हटाकर संशोधित करता है। सम्मेलन के अनुसार, जिस क्रम में तत्वों को जोड़ा जाता है उसके अंत को कतार का पिछला भाग कहा जाता है एवं जिस अंत में तत्वों को हटा दिया जाता है उसे कतार का अगला भाग कहा जाता है जो कि जब उपयोग किए गए शब्दों के अनुरूप होता है जिसके लिए लोग सामान या सेवाओं की प्रतीक्षा करने के लिए क्रम में लगते हैं।
-कतार के पिछले भाग में एक तत्व जोड़ने की क्रिया को 'एनक्यू' के रूप में जाना जाता है, और किसी तत्व को सामने से हटाने की क्रिया को 'डीक्यू' के रूप में जाना जाता है। अन्य कार्यों की भी अनुमति दी जा सकती है, जिसमें अक्सर ''पीक (डेटा टाइप ऑपरेशन)'' या ''फ्रंट'' ऑपरेशन शामिल होता है, जो अगले तत्व के मूल्य को बिना डीक्यू किए वापस कर देता है।
+कतार के पिछले भाग में तत्व जोड़ने की क्रिया को 'एनक्यू' के रूप में जाना जाता है, एवं किसी तत्व को सामने से हटाने की क्रिया को 'डीक्यू' के रूप में जाना जाता है। अन्य कार्यों की भी अनुमति दी जाती है, जिसमें अधिकांशतः ''पीक (डेटा प्रकार संचालन)'' या ''मुख्य'' संचालन सम्मलित होता है, जो अगले तत्व के मूल्य को बिना डीक्यू किए वापस करता है।
-कतार के संचालन इसे एक [[फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)]] बनाते हैं | पहले-में-पहले-बाहर (फीफो) डेटा संरचना। फीफो डेटा संरचना में, कतार में जोड़ा गया पहला तत्व हटा दिया जाने वाला पहला तत्व होगा। यह आवश्यकता के बराबर है कि एक बार एक नया तत्व जोड़ा जाता है, नए तत्व को हटाए जाने से पहले सभी तत्व जो पहले जोड़े गए थे उन्हें हटा दिया जाना चाहिए। एक कतार एक रेखीय डेटा संरचना का एक उदाहरण है, या अधिक संक्षेप में एक अनुक्रमिक संग्रह है।
+फीफो डेटा संरचना में कतार में जोड़ा गया पहला हटा दिया जाने वाला तत्व होता है। यह आवश्यकता है कि एक बार एक नवीन तत्व जोड़ा जाता है जोकि नए तत्व को हटाए जाने से पहले सभी तत्व जो पहले जोड़े गए थे उन्हें हटा दिया जाना चाहिए। एक कतार एक रेखीय डेटा संरचना का एक उदाहरण है, या अधिक संक्षेप में एक अनुक्रमिक संग्रह है।
-कंप्यूटर प्रोग्राम में कतारें आम हैं, जहां उन्हें एक्सेस रूटीन के साथ डेटा संरचनाओं के रूप में कार्यान्वित किया जाता है, एक [[सार डेटा संरचना]] के रूप में या ऑब्जेक्ट-ओरिएंटेड भाषाओं में कक्षाओं के रूप में। सामान्य कार्यान्वयन [[गोलाकार बफर]] और लिंक्ड सूचियाँ हैं।
+अभिकलन प्रोग्राम में कतारें सामान्य हैं, जहां उन्हें एक्सेस रूटीन के साथ डेटा संरचनाओं के रूप में कार्यान्वित किया जाता है, एक [[सार डेटा संरचना]] के रूप में या ऑब्जेक्ट-ओरिएंटेड भाषाओं में कक्षाओं के रूप में। सामान्यतः कार्यान्वयन [[गोलाकार बफर]] एवं लिंक्ड सूचियाँ हैं।
-कंप्यूटर विज्ञान, [[परिवहन]] और संचालन अनुसंधान में कतारें सेवाएं प्रदान करती हैं जहां डेटा, ऑब्जेक्ट्स, व्यक्तियों या घटनाओं जैसी विभिन्न संस्थाओं को संग्रहीत और बाद में संसाधित करने के लिए आयोजित किया जाता है। इन संदर्भों में, क्यू एक बफ़र (कंप्यूटर विज्ञान) का कार्य करता है।
+अभिकलन विज्ञान, [[परिवहन]] एवं संचालन अनुसंधान में कतारें सेवाएं प्रदान करती हैं जहां डेटा, ऑब्जेक्ट्स, व्यक्तियों या घटनाओं जैसी विभिन्न संस्थाओं को संग्रहीत एवं पश्चात संसाधित करने के लिए आयोजित किया जाता है। इन संदर्भों में, क्यू एक बफ़र (अभिकलन विज्ञान) का कार्य करता है।
 क्यू का एक अन्य उपयोग चौड़ाई-प्रथम खोज के कार्यान्वयन में है।
 =={{Anchor|BOUNDED}}कतार कार्यान्वयन ==
-सैद्धांतिक रूप से, कतार की एक विशेषता यह है कि इसकी कोई विशिष्ट क्षमता नहीं होती है। भले ही कितने तत्व पहले से मौजूद हों, एक नया तत्व हमेशा जोड़ा जा सकता है। यह खाली भी हो सकता है, जिस बिंदु पर एक तत्व को हटाना तब तक असंभव होगा जब तक कि एक नया तत्व फिर से जोड़ा नहीं जाता।
+सैद्धांतिक रूप से, कतार की एक विशेषता यह है कि इसकी कोई विशिष्ट क्षमता नहीं होती है। यदि कितने तत्व पहले से सम्मलित हों, एक नवीन तत्व निरंतर जोड़ा जा सकता है। यह खाली भी हो सकता है, जिस बिंदु पर एक तत्व को हटाना तब तक असंभव होगा जब तक कि एक नवीन तत्व फिर से जोड़ा नहीं जाता।
-निश्चित-लंबाई सरणियों की क्षमता सीमित है, लेकिन यह सच नहीं है कि आइटम को कतार के प्रमुख की ओर कॉपी करने की आवश्यकता है। [[सरणी]] को एक बंद सर्कल में बदलने और उस सर्कल में सिर और पूंछ को अंतहीन रूप से घूमने देने की सरल चाल सरणी में संग्रहीत वस्तुओं को कभी भी स्थानांतरित करने के लिए अनावश्यक बनाती है। यदि n सरणी का आकार है, तो कंप्यूटिंग सूचकांक modulo n सरणी को एक वृत्त में बदल देगा। यह अभी भी एक उच्च-स्तरीय भाषा में कतार बनाने का वैचारिक रूप से सबसे सरल तरीका है, लेकिन यह निश्चित रूप से चीजों को थोड़ा धीमा करता है, क्योंकि सरणी सूचकांकों की तुलना शून्य और सरणी आकार से की जानी चाहिए, जो कि इसमें लगने वाले समय के बराबर है। जांचें कि क्या कोई सरणी अनुक्रमणिका सीमा से बाहर है, जो कुछ भाषाएं करती हैं, लेकिन यह निश्चित रूप से त्वरित और गंदे कार्यान्वयन के लिए, या किसी भी उच्च-स्तरीय भाषा के लिए पसंद का तरीका होगा जिसमें पॉइंटर सिंटैक्स नहीं है। समय से पहले सरणी आकार घोषित किया जाना चाहिए, लेकिन अतिप्रवाह होने पर कुछ कार्यान्वयन केवल घोषित सरणी आकार को दोगुना कर देते हैं। ऑब्जेक्ट्स या पॉइंटर (कंप्यूटर प्रोग्रामिंग) के साथ अधिकांश आधुनिक भाषाएं गतिशील सूचियों के लिए पुस्तकालयों को लागू कर सकती हैं या उनके साथ आ सकती हैं। हो सकता है कि ऐसी [[डेटा संरचना]]ओं में स्मृति बाधाओं के अलावा एक निश्चित क्षमता सीमा निर्दिष्ट न हो। कतार अतिप्रवाह परिणाम एक पूर्ण कतार में एक तत्व जोड़ने की कोशिश करने से होता है और एक खाली कतार से एक तत्व को निकालने का प्रयास करते समय कतार अंडरफ्लो होता है।
+निश्चित-लंबाई सरणियों की क्षमता सीमित है, लेकिन यह सच नहीं है कि आइटम को कतार के प्रमुख की ओर कॉपी करने की आवश्यकता है। [[सरणी]] को एक बंद सर्कल में बदलने एवं उस सर्कल में सिर एवं पूंछ को अंतहीन रूप से घूमने देने की सरल चाल सरणी में संग्रहीत वस्तुओं को कभी भी स्थानांतरित करने के लिए अनावश्यक बनाती है। यदि n सरणी का बनावट है, तो अभिकलन सूचकांक modulo n सरणी को एक वृत्त में बदल देगा। यह अभी भी एक उच्च-स्तरीय भाषा में कतार बनाने का वैचारिक रूप से सबसे सरल विधि है, लेकिन यह निश्चित रूप से चीजों को थोड़ा धीमा करता है, क्योंकि सरणी सूचकांकों की तुलना शून्य एवं सरणी बनावट से की जानी चाहिए, जो कि इसमें लगने वाले समय के बराबर है। जांचें कि क्या कोई सरणी अनुक्रमणिका सीमा से बाहर है, जो कुछ भाषाएं करती हैं, लेकिन यह निश्चित रूप से त्वरित एवं गंदे कार्यान्वयन के लिए, या किसी भी उच्च-स्तरीय भाषा के लिए पसंद का विधि होगा जिसमें पॉइंटर सिंटैक्स नहीं है। समय से पहले सरणी बनावट घोषित किया जाना चाहिए, लेकिन अतिप्रवाह होने पर कुछ कार्यान्वयन सिर्फ घोषित सरणी बनावट को दोगुना कर देते हैं। ऑब्जेक्ट्स या पॉइंटर (अभिकलन प्रोग्रामिंग) के साथ अधिकांश आधुनिक भाषाएं गतिशील सूचियों के लिए पुस्तकालयों को लागू कर सकती हैं या उनके साथ आ सकती हैं। हो सकता है कि ऐसी [[डेटा संरचना]]ओं में स्मृति बाधाओं के अतिरिक्त एक निश्चित क्षमता सीमा निर्दिष्ट न हो। कतार अतिप्रवाह परिणाम एक पूर्ण कतार में एक तत्व जोड़ने की कोशिश करने से होता है एवं एक खाली कतार से एक तत्व को निकालने का प्रयास करते समय कतार अंडरफ्लो होता है।
 एक बंधी हुई कतार एक निश्चित संख्या में वस्तुओं तक सीमित एक कतार है।<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html |title=Queue (Java Platform SE 7) |publisher=Docs.oracle.com |date=2014-03-26 |access-date=2014-05-22}}</ref>
-फीफो कतारों के कई कुशल कार्यान्वयन हैं। एक कुशल कार्यान्वयन वह है जो [[बिग ओ नोटेशन]] | ओ (1) समय में संचालन-एन-क्यूइंग और डी-क्यूइंग- कर सकता है।
+फीफो कतारों के कई कुशल कार्यान्वयन हैं। एक कुशल कार्यान्वयन वह है जो [[बिग ओ नोटेशन]] | ओ (1) समय में संचालन-एन-क्यूइंग एवं डी-क्यूइंग- कर सकता है।
 *लिंक्ड सूची
-** एक दोगुनी लिंक की गई सूची में दोनों सिरों पर ओ (1) सम्मिलन और विलोपन होता है, इसलिए यह कतारों के लिए एक स्वाभाविक विकल्प है।
+** एक दोगुनी लिंक की गई सूची में दोनों सिरों पर ओ (1) सम्मिलन एवं विलोपन होता है, इसलिए यह कतारों के लिए एक स्वाभाविक विकल्प है।
-** नियमित रूप से एकल रूप से जुड़ी सूची में केवल एक छोर पर प्रभावी प्रविष्टि और विलोपन होता है। हालाँकि, एक छोटा संशोधन - पहले के अलावा अंतिम नोड के लिए एक पॉइंटर रखना - इसे एक कुशल कतार को लागू करने में सक्षम करेगा।
+** नियमित रूप से एकल रूप से जुड़ी सूची में सिर्फ एक छोर पर प्रभावी प्रविष्टि एवं विलोपन होता है। चूंकि, एक छोटा संशोधन - पहले के अतिरिक्त अंतिम नोड के लिए एक पॉइंटर रखना - इसे एक कुशल कतार को लागू करने में सक्षम करेगा।
 * एक संशोधित गतिशील सरणी का उपयोग करके कार्यान्वित एक [[डबल-एंडेड कतार]]
-=== कतारें और प्रोग्रामिंग भाषाएं ===
+=== कतारें एवं प्रोग्रामिंग भाषाएं ===
-कतारों को एक अलग डेटा प्रकार के रूप में लागू किया जा सकता है, या शायद डबल-एंडेड कतार (डीक्यू) का एक विशेष मामला माना जाता है और अलग से लागू नहीं किया जाता है। उदाहरण के लिए, [[पर्ल]] और [[ रूबी (प्रोग्रामिंग भाषा) ]] दोनों सिरों से एक सरणी को पुश और पॉप करने की अनुमति देते हैं, इसलिए कोई पुश और शिफ्ट फ़ंक्शंस का उपयोग किसी सूची को एन्क्यू और डीक्यू करने के लिए कर सकता है (या, रिवर्स में, कोई अनशिफ्ट और पॉप का उपयोग कर सकता है),<ref>{{cite web|url=https://ruby-doc.org/core-3.1.0/Array.html#class-Array-label-Adding+Items+to+Arrays |title=Array (Ruby 3.1) |date=2021-12-25 |access-date=2022-05-11}}</ref> हालांकि कुछ मामलों में ये ऑपरेशन कुशल नहीं हैं।
+कतारों को एक भिन्न डेटा प्रकार के रूप में लागू किया जा सकता है, या संभवतः डबल-एंडेड कतार (डीक्यू) का एक विशेष स्थिति माना जाता है एवं भिन्न से लागू नहीं किया जाता है। उदाहरण के लिए, [[पर्ल]] एवं [[ रूबी (प्रोग्रामिंग भाषा) ]] दोनों सिरों से एक सरणी को पुश एवं पॉप करने की अनुमति देते हैं, इसलिए कोई पुश एवं शिफ्ट फ़ंक्शंस का उपयोग किसी सूची को एन्क्यू एवं डीक्यू करने के लिए कर सकता है (या, रिवर्स में, कोई अनशिफ्ट एवं पॉप का उपयोग कर सकता है),<ref>{{cite web|url=https://ruby-doc.org/core-3.1.0/Array.html#class-Array-label-Adding+Items+to+Arrays |title=Array (Ruby 3.1) |date=2021-12-25 |access-date=2022-05-11}}</ref> चूंकि कुछ स्थितियों में ये संचालन कुशल नहीं हैं।
-C++ की [[मानक टेम्पलेट लाइब्रेरी]] प्रदान करती है a<code>queue</code>टेम्पलेट क्लास जो केवल पुश/पॉप ऑपरेशंस तक ही सीमित है। J2SE5.0 के बाद से, Java लाइब्रेरी में a {{Javadoc:SE|java/util|Queue}} इंटरफ़ेस जो कतार संचालन निर्दिष्ट करता है; कार्यान्वयन वर्ग शामिल हैं {{Javadoc:SE|java/util|LinkedList}} और (J2SE 1.6 से) {{Javadoc:SE|java/util|ArrayDeque}}. PHP में [http://www.php.net/manual/en/class.splqueue.php SplQueue] क्लास और बीनस्टॉकड और [[ जर्मनी ]] जैसी थर्ड पार्टी लाइब्रेरी हैं।
+C++ की [[मानक टेम्पलेट लाइब्रेरी]] प्रदान करती है a<code>queue</code>टेम्पलेट क्लास जो सिर्फ पुश/पॉप ऑपरेशंस तक ही सीमित है। J2SE5.0 के पश्चात से, Java लाइब्रेरी में a {{Javadoc:SE|java/util|Queue}} इंटरफ़ेस जो कतार संचालन निर्दिष्ट करता है; कार्यान्वयन वर्ग सम्मलित हैं {{Javadoc:SE|java/util|LinkedList}} एवं (J2SE 1.6 से) {{Javadoc:SE|java/util|ArrayDeque}}. PHP में [http://www.php.net/manual/en/class.splqueue.php SplQueue] क्लास एवं बीनस्टॉकड एवं [[ जर्मनी ]] जैसी थर्ड पार्टी लाइब्रेरी हैं।
 === उदाहरण ===
@@ Line 63: / Line 60: @@
 == विशुद्ध रूप से कार्यात्मक कार्यान्वयन ==
-कतारों को [[विशुद्ध रूप से कार्यात्मक डेटा संरचना]] के रूप में भी लागू किया जा सकता है।<ref>{{cite web |last1=Okasaki|first1=Chris|title=विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं|url=https://doc.lagout.org/programmation/Functional%20Programming/Chris_Okasaki-Purely_Functional_Data_Structures-Cambridge_University_Press%281998%29.pdf}}</ref> दो कार्यान्वयन हैं। पहला ही प्राप्त करता है <math>O(1)</math> प्रति ऑपरेशन औसतन। यही है, [[परिशोधित विश्लेषण]] का समय है <math>O(1)</math>, लेकिन व्यक्तिगत संचालन लग सकते हैं <math>O(n)</math> जहाँ n कतार में तत्वों की संख्या है। दूसरे कार्यान्वयन को 'रीयल-टाइम क्यू' कहा जाता है<ref>{{cite journal|last1=Hood|first1=Robert|last2=Melville|first2=Robert|title=शुद्ध लिस्प में रीयल-टाइम कतार संचालन|journal=Information Processing Letters|date=November 1981|volume=13|issue=2|pages=50–54 |doi=10.1016/0020-0190(81)90030-2 |hdl=1813/6273|hdl-access=free}}</ref> और यह कतार को ओ (1) सबसे खराब समय में संचालन के साथ [[लगातार डेटा संरचना]] होने की अनुमति देता है। यह एक अधिक जटिल कार्यान्वयन है और [[memoization]] के साथ [[आलसी मूल्यांकन]] सूचियों की आवश्यकता होती है।
+कतारों को [[विशुद्ध रूप से कार्यात्मक डेटा संरचना]] के रूप में भी लागू किया जा सकता है।<ref>{{cite web |last1=Okasaki|first1=Chris|title=विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं|url=https://doc.lagout.org/programmation/Functional%20Programming/Chris_Okasaki-Purely_Functional_Data_Structures-Cambridge_University_Press%281998%29.pdf}}</ref> दो कार्यान्वयन हैं। पहला ही प्राप्त करता है <math>O(1)</math> प्रति संचालन औसतन। यही है, [[परिशोधित विश्लेषण]] का समय है <math>O(1)</math>, लेकिन व्यक्तिगत संचालन लग सकते हैं <math>O(n)</math> जहाँ n कतार में तत्वों की संख्या है। दूसरे कार्यान्वयन को 'रीयल-टाइम क्यू' कहा जाता है<ref>{{cite journal|last1=Hood|first1=Robert|last2=Melville|first2=Robert|title=शुद्ध लिस्प में रीयल-टाइम कतार संचालन|journal=Information Processing Letters|date=November 1981|volume=13|issue=2|pages=50–54 |doi=10.1016/0020-0190(81)90030-2 |hdl=1813/6273|hdl-access=free}}</ref> एवं यह कतार को ओ (1) सबसे खराब समय में संचालन के साथ [[लगातार डेटा संरचना]] होने की अनुमति देता है। यह एक अधिक जटिल कार्यान्वयन है एवं [[memoization]] के साथ [[आलसी मूल्यांकन]] सूचियों की आवश्यकता होती है।
 === परिशोधित कतार ===
-इस कतार का डेटा दो Linked_list#Singly_linked_list|singly-linked_list नाम की दो सूचियों में संग्रहीत है <math>f</math> और <math>r</math>. सूची <math>f</math> कतार के सामने का हिस्सा रखता है। सूची <math>r</math> शेष तत्वों (उर्फ, कतार के पीछे) को उल्टे क्रम में रखता है। के सिर पर एक नोड जोड़कर कतार के सामने सम्मिलित करना आसान है <math>f</math>. और अगर <math>r</math> खाली नहीं है, के सिर पर नोड को हटाकर कतार के अंत से हटाना आसान है <math>r</math>. कब <math>r</math> खाली है, सूची <math>f</math> उलटा और सौंपा गया है <math>r</math> और उसके बाद के सिर <math>r</math> हटा दिया गया।
+इस कतार का डेटा दो Linked_list#Singly_linked_list|singly-linked_list नाम की दो सूचियों में संग्रहीत है <math>f</math> एवं <math>r</math>. सूची <math>f</math> कतार के सामने का भाग रखता है। सूची <math>r</math> शेष तत्वों (उर्फ, कतार के पीछे) को उल्टे क्रम में रखता है। के सिर पर एक नोड जोड़कर कतार के सामने सम्मिलित करना आसान है <math>f</math>. एवं यदि <math>r</math> खाली नहीं है, के सिर पर नोड को हटाकर कतार के अंत से हटाना आसान है <math>r</math>. कब <math>r</math> खाली है, सूची <math>f</math> उलटा एवं सौंपा गया है <math>r</math> एवं उसके पश्चात के सिर <math>r</math> हटा दिया गया।
-इन्सर्ट (एनक्यू) हमेशा लेता है <math>O(1)</math> समय। निष्कासन (डेक्यू) लेता है <math>O(1)</math> जब सूची <math>r</math> खाली नहीं है। कब <math>r</math> खाली है, उल्टा लेता है <math>O(n)</math> कहाँ <math>n</math> में तत्वों की संख्या है <math>f</math>. लेकिन, हम कह सकते हैं कि यह है <math>O(1)</math> परिशोधित विश्लेषण समय, क्योंकि प्रत्येक तत्व में <math>f</math> डाला जाना था और जब इसे डाला गया था, तब हम रिवर्स में प्रत्येक तत्व के लिए एक स्थिर लागत निर्दिष्ट कर सकते हैं।
+इन्सर्ट (एनक्यू) निरंतर लेता है <math>O(1)</math> समय। निष्कासन (डेक्यू) लेता है <math>O(1)</math> जब सूची <math>r</math> खाली नहीं है। कब <math>r</math> खाली है, उल्टा लेता है <math>O(n)</math> कहाँ <math>n</math> में तत्वों की संख्या है <math>f</math>. लेकिन, हम कह सकते हैं कि यह है <math>O(1)</math> परिशोधित विश्लेषण समय, क्योंकि प्रत्येक तत्व में <math>f</math> डाला जाना था एवं जब इसे डाला गया था, तब हम रिवर्स में प्रत्येक तत्व के लिए एक स्थिर लागत निर्दिष्ट कर सकते हैं।
 === वास्तविक समय कतार ===
-रीयल-टाइम कतार प्राप्त होती है <math>O(1)</math> परिशोधन के बिना, सभी कार्यों के लिए समय। यह चर्चा तकनीकी होगी, इसलिए याद रखें कि, के लिए <math>l</math> एक सूची, <math>|l|</math> इसकी लंबाई को दर्शाता है, कि NIL एक खाली सूची का प्रतिनिधित्व करता है और <math>\operatorname{CONS}(h,t)</math> उस सूची का प्रतिनिधित्व करता है जिसका सिर एच है और जिसकी पूंछ टी है।
+रीयल-टाइम कतार प्राप्त होती है <math>O(1)</math> परिशोधन के बिना, सभी कार्यों के लिए समय। यह चर्चा तकनीकी होगी, इसलिए याद रखें कि, के लिए <math>l</math> एक सूची, <math>|l|</math> इसकी लंबाई को दर्शाता है, कि NIL एक खाली सूची का प्रतिनिधित्व करता है एवं <math>\operatorname{CONS}(h,t)</math> उस सूची का प्रतिनिधित्व करता है जिसका सिर एच है एवं जिसकी पूंछ टी है।
-हमारी कतारों को लागू करने के लिए उपयोग की जाने वाली डेटा संरचना में तीन Linked_list#Singly_linked_list|singly-linked सूचियाँ शामिल हैं <math>(f,r,s)</math> जहाँ f कतार का अगला भाग है, r विपरीत क्रम में कतार का पिछला भाग है। संरचना का अपरिवर्तनीय यह है कि एस इसके बिना एफ के पीछे है <math>|r|</math> पहला तत्व, अर्थात् <math>|s|=|f|-|r|</math>. कतार की पूँछ <math>(\operatorname{CONS}(x,f),r,s)</math> तब लगभग है <math>(f,r,s)</math> और
+हमारी कतारों को लागू करने के लिए उपयोग की जाने वाली डेटा संरचना में तीन Linked_list#Singly_linked_list|singly-linked सूचियाँ सम्मलित हैं <math>(f,r,s)</math> जहाँ f कतार का अगला भाग है, r विपरीत क्रम में कतार का पिछला भाग है। संरचना का अपरिवर्तनीय यह है कि एस इसके बिना एफ के पीछे है <math>|r|</math> पहला तत्व, अर्थात् <math>|s|=|f|-|r|</math>. कतार की पूँछ <math>(\operatorname{CONS}(x,f),r,s)</math> तब लगभग है <math>(f,r,s)</math> एवं
-एक तत्व x को सम्मिलित करना <math>(f,r,s)</math> लगभग है <math>(f,\operatorname{CONS}(x,r),s)</math>. ऐसा लगभग इसलिए कहा जाता है, क्योंकि उन दोनों परिणामों में, <math>|s|=|f|-|r|+1</math>. एक सहायक कार्य <math>aux</math> फिर संतुष्ट होने के लिए अपरिवर्तनीय को बुलाया जाना चाहिए। इस पर निर्भर करते हुए दो मामलों पर विचार किया जाना चाहिए <math>s</math> खाली सूची है, किस मामले में <math>|r|=|f|+1</math>, या नहीं। औपचारिक परिभाषा है <math>\operatorname{aux}(f,r,\operatorname{Cons}(\_,s))=(f,r,s)</math> और <math>\operatorname{aux}(f,r,\text{NIL})=(f',\text{NIL},f')</math> कहाँ <math>f'</math> f के बाद r का उल्टा होता है।
+एक तत्व x को सम्मिलित करना <math>(f,r,s)</math> लगभग है <math>(f,\operatorname{CONS}(x,r),s)</math>. ऐसा लगभग इसलिए कहा जाता है, क्योंकि उन दोनों परिणामों में, <math>|s|=|f|-|r|+1</math>. एक सहायक कार्य <math>aux</math> फिर संतुष्ट होने के लिए अपरिवर्तनीय को बुलाया जाना चाहिए। इस पर निर्भर करते हुए दो स्थितियों पर विचार किया जाना चाहिए <math>s</math> खाली सूची है, किस स्थितियों में <math>|r|=|f|+1</math>, या नहीं। औपचारिक परिभाषा है <math>\operatorname{aux}(f,r,\operatorname{Cons}(\_,s))=(f,r,s)</math> एवं <math>\operatorname{aux}(f,r,\text{NIL})=(f',\text{NIL},f')</math> कहाँ <math>f'</math> f के पश्चात r का उल्टा होता है।
-चलो फोन करते हैं <math>\operatorname{reverse}(f,r)</math> फ़ंक्शन जो f के बाद r देता है, उलटा होता है। चलिए यह भी मान लेते हैं <math>|r|=|f|+1</math>, क्योंकि यह वह स्थिति है जब इस फ़ंक्शन को कॉल किया जाता है। अधिक सटीक रूप से, हम एक आलसी कार्य को परिभाषित करते हैं <math>\operatorname{rotate}(f,r,a)</math> जो इनपुट तीन सूची के रूप में लेता है <math>|r|=|f|+1</math>, और r का उलटा और a का f का संयोजन लौटाता है। तब <math>\operatorname{reverse}(f,r)=\operatorname{rotate}(f,r,\text{NIL})</math>.
+चलो फोन करते हैं <math>\operatorname{reverse}(f,r)</math> फ़ंक्शन जो f के पश्चात r देता है, उलटा होता है। चलिए यह भी मान लेते हैं <math>|r|=|f|+1</math>, क्योंकि यह वह स्थिति है जब इस फ़ंक्शन को कॉल किया जाता है। अधिक त्रुटिहीन रूप से, हम एक आलसी कार्य को परिभाषित करते हैं <math>\operatorname{rotate}(f,r,a)</math> जो इनपुट तीन सूची के रूप में लेता है <math>|r|=|f|+1</math>, एवं r का उलटा एवं a का f का संयोजन लौटाता है। तब <math>\operatorname{reverse}(f,r)=\operatorname{rotate}(f,r,\text{NIL})</math>.
-घुमाने की आगमनात्मक परिभाषा है <math>\operatorname{rotate}(\text{NIL},\operatorname{Cons}(y,\text{NIL}),a)=\operatorname{Cons}(y,a)</math> और <math>\operatorname{rotate}(\operatorname{CONS}(x,f),\operatorname{CONS}(y,r),a)=\operatorname{Cons}(x,\operatorname{rotate}(f,r,\operatorname{CONS}(y,a)))</math>. इसके चलने का समय है <math>O(r)</math>, लेकिन, चूंकि आलसी मूल्यांकन का उपयोग किया जाता है, गणना तब तक विलंबित होती है जब तक कि गणना द्वारा परिणाम को मजबूर नहीं किया जाता है।
+घुमाने की आगमनात्मक परिभाषा है <math>\operatorname{rotate}(\text{NIL},\operatorname{Cons}(y,\text{NIL}),a)=\operatorname{Cons}(y,a)</math> एवं <math>\operatorname{rotate}(\operatorname{CONS}(x,f),\operatorname{CONS}(y,r),a)=\operatorname{Cons}(x,\operatorname{rotate}(f,r,\operatorname{CONS}(y,a)))</math>. इसके चलने का समय है <math>O(r)</math>, लेकिन, चूंकि आलसी मूल्यांकन का उपयोग किया जाता है, गणना तब तक विलंबित होती है जब तक कि गणना द्वारा परिणाम को मजबूर नहीं किया जाता है।
-डेटा संरचना में सूची के दो उद्देश्य हैं। यह सूची काउंटर के रूप में कार्य करती है <math>|f|-|r|</math>, वास्तव में, <math>|f|=|r|</math> अगर और केवल अगर खाली सूची है। यह काउंटर हमें यह सुनिश्चित करने की अनुमति देता है कि पिछला कभी भी सामने की सूची से अधिक लंबा न हो। इसके अलावा, एस का उपयोग करना, जो कि एफ की पूंछ है, प्रत्येक पूंछ के दौरान (आलसी) सूची एफ के एक हिस्से की गणना को मजबूर करता है और ऑपरेशन सम्मिलित करता है। इसलिए कब <math>|f|=|r|</math>, सूची f पूरी तरह से मजबूर है। यदि ऐसा नहीं होता, तो f का आंतरिक प्रतिनिधित्व परिशिष्ट का... परिशिष्ट का कुछ परिशिष्ट हो सकता है, और बल लगाना अब एक निरंतर समय संचालन नहीं होगा।
+डेटा संरचना में सूची के दो उद्देश्य हैं। यह सूची काउंटर के रूप में कार्य करती है <math>|f|-|r|</math>, वास्तव में, <math>|f|=|r|</math> यदि एवं सिर्फ यदि खाली सूची है। यह काउंटर हमें यह सुनिश्चित करने की अनुमति देता है कि पिछला कभी भी सामने की सूची से अधिक लंबा न हो। इसके अतिरिक्त, एस का उपयोग करना, जो कि एफ की पूंछ है, प्रत्येक पूंछ के समय  (आलसी) सूची एफ के एक हिस्से की गणना को मजबूर करता है एवं संचालन सम्मिलित करता है। इसलिए कब <math>|f|=|r|</math>, सूची f पूरी प्रकार से मजबूर है। यदि ऐसा नहीं होता, तो f का आंतरिक प्रतिनिधित्व परिशिष्ट का... परिशिष्ट का कुछ परिशिष्ट हो सकता है, एवं बल लगाना अब एक निरंतर समय संचालन नहीं होगा।
 == यह भी देखें ==
@@ Line 97: / Line 94: @@
-=== सामान्य संदर्भ ===
+=== सामान्यतः संदर्भ ===
 * {{DADS|Bounded queue|boundedqueue}}

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:38, 1 March 2023

Contents