डबल-एंडेड कतार: Difference between revisions
No edit summary |
No edit summary |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
[[कंप्यूटर विज्ञान]] में, '''डबल-एंडेड क्यू''' (संक्षिप्त रूप से डीक्यू, स्पष्ट 'डेक', जैसे चेक<ref>Jesse Liberty; Siddhartha Rao; Bradley Jones. ''C++ in One Hour a Day, Sams Teach Yourself'', Sixth Edition. Sams Publishing, 2009. {{ISBN|0-672-32941-7}}. Lesson 18: STL Dynamic Array Classes, pp. 486.</ref>) एक [[सार डेटा प्रकार|अमूर्त डेटा प्रकार]] है जो एक [[कतार (डेटा संरचना)|क्यू (डेटा संरचना)]] को सामान्यीकृत करता है, जिसके लिए तत्वों को फ्रंट (हेड) या बैक (टैल) से जोड़ा या हटाया जा सकता है।<ref>[[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 Deques, pp. 238–243.</ref> इसे प्रायः हेड-टेल लिंक्ड सूची भी कहा जाता है, हालांकि सही से यह '''डीक्यू''' की एक विशिष्ट [[डेटा संरचना]] ''कार्यान्वयन'' को संदर्भित करता है (नीचे देखें)। | |||
[[कंप्यूटर विज्ञान]] में, | |||
== नामोल्लेखन कन्वेंशन == | == नामोल्लेखन कन्वेंशन == | ||
डेक को कभी-कभी डीक्यू भी लिखा जाता है, लेकिन इस प्रयोग को सामान्य रूप से तकनीकी साहित्य या तकनीकी लेखन में बहिष्कृत किया जाता है क्योंकि डीक्यू भी एक क्रिया है जिसका अर्थ क्यू | डेक को कभी-कभी डीक्यू भी लिखा जाता है, लेकिन इस प्रयोग को सामान्य रूप से तकनीकी साहित्य या तकनीकी लेखन में बहिष्कृत किया जाता है क्योंकि डीक्यू भी एक क्रिया है जिसका अर्थ क्यू से हटाना है। फिर भी, कई [[ पुस्तकालय (कम्प्यूटिंग) |पुस्तकालय (कम्प्यूटिंग)]] और कुछ लेखक, जैसे अहो, होपक्रॉफ्ट, और उल्मैन ने अपनी पाठ्यपुस्तक डेटा संरचना और एल्गोरिदम में, इसे डीक्यू बताया है। <nowiki>''कॉन्सेप्ट्स इन प्रोग्रामिंग भाषा''</nowiki> के लेखक जॉन सी मिशेल भी इस शब्दावली का उपयोग करते हैं। | ||
== विभेद और सबटाइप == | == विभेद और सबटाइप == | ||
Line 14: | Line 10: | ||
* एक आउटपुट-प्रतिबंधित डेक वह है जहां दोनों सिरों पर प्रविष्टि किया जा सकता है, लेकिन विलोपन केवल एक एंड से किया जा सकता है। | * एक आउटपुट-प्रतिबंधित डेक वह है जहां दोनों सिरों पर प्रविष्टि किया जा सकता है, लेकिन विलोपन केवल एक एंड से किया जा सकता है। | ||
कंप्यूटिंग, क्यू | कंप्यूटिंग, क्यू (डेटा संरचना) और स्टैक (डेटा संरचना) में आधारभूत और सबसे सामान्य सूची प्रकार दोनों को डेक की विशेषज्ञता माना जा सकता है, और डेक का उपयोग करके कार्यान्वित किया जा सकता है। | ||
== संचालन == | == संचालन == | ||
Line 52: | Line 48: | ||
गतिशील सरणी दृष्टिकोण गतिशील सरणी के एक प्रकार का उपयोग करता है जो दोनों सिरों से बढ़ सकता है, जिसे कभी-कभी सरणी डेक कहा जाता है। इन सरणी डीक्यू में एक गतिशील सरणी के सभी गुण होते हैं, जैसे कि निरंतर-समय यादृच्छिक अभिगम, संदर्भ का अच्छा स्थान, और बीच में अप्रभावी प्रविष्टि/हटाना, इसके अतिरिक्त दोनों सिरों पर परिशोधित निरंतर-समय प्रविष्टि/हटाना जिसमे सिर्फ एक एंड सम्मिलित है। इसमे तीन सामान्य कार्यान्वयन में सम्मिलित हैं: | गतिशील सरणी दृष्टिकोण गतिशील सरणी के एक प्रकार का उपयोग करता है जो दोनों सिरों से बढ़ सकता है, जिसे कभी-कभी सरणी डेक कहा जाता है। इन सरणी डीक्यू में एक गतिशील सरणी के सभी गुण होते हैं, जैसे कि निरंतर-समय यादृच्छिक अभिगम, संदर्भ का अच्छा स्थान, और बीच में अप्रभावी प्रविष्टि/हटाना, इसके अतिरिक्त दोनों सिरों पर परिशोधित निरंतर-समय प्रविष्टि/हटाना जिसमे सिर्फ एक एंड सम्मिलित है। इसमे तीन सामान्य कार्यान्वयन में सम्मिलित हैं: | ||
* डेक | * डेक तत्व को एक परिपत्र बफ़र में संग्रहीत करना, और केवल तभी आकार बदलना जब बफ़र पूर्ण हो जाता है। इससे आकार बदलने की आवृत्ति कम हो जाती है। | ||
* अंतर्निहित सरणी के केंद्र से डेक | * अंतर्निहित सरणी के केंद्र से डेक तत्व आवंटित करना, और अंत तक पहुंचने पर अंतर्निहित सरणी का आकार बदलना। इस दृष्टिकोण को अधिक बार आकार बदलने और अधिक स्थान नष्ट करने की आवश्यकता हो सकती है, विशेषकर जब तत्व केवल एक एंड पर निर्दिष्ट किए जाते हैं। | ||
* | * तत्व को कई छोटे सरणियों में संग्रहीत करना, आवश्यकतानुसार प्रारंभ या अंत में अतिरिक्त सरणियाँ आवंटित करना। प्रत्येक छोटे सरणियों में पॉइंटर्स युक्त एक गतिशील सरणी रखकर इंडेक्सिंग को कार्यान्वित किया जाता है। | ||
=== पूर्ण रूप से कार्यात्मक कार्यान्वयन === | === पूर्ण रूप से कार्यात्मक कार्यान्वयन === | ||
डबल-एंडेड कतारों को [[विशुद्ध रूप से कार्यात्मक डेटा संरचना]] के रूप में भी प्रयुक्त किया जा सकता है।<ref name="functional">{{cite thesis |url=https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf |first=Chris |last=Okasaki |title=विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं|type=Ph.D. thesis |date=September 1996 |publisher=Carnegie Mellon University |id=CMU-CS-96-177}}</ref>{{rp|115}} कार्यान्वयन के दो संस्करण सम्मिलित हैं। पहला, जिसे 'वास्तविक समय डेक' कहा जाता है, नीचे प्रस्तुत किया गया है। यह क्यू | डबल-एंडेड कतारों को [[विशुद्ध रूप से कार्यात्मक डेटा संरचना]] के रूप में भी प्रयुक्त किया जा सकता है।<ref name="functional">{{cite thesis |url=https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf |first=Chris |last=Okasaki |title=विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं|type=Ph.D. thesis |date=September 1996 |publisher=Carnegie Mellon University |id=CMU-CS-96-177}}</ref>{{rp|115}} कार्यान्वयन के दो संस्करण सम्मिलित हैं। पहला, जिसे 'वास्तविक समय डेक' कहा जाता है, नीचे प्रस्तुत किया गया है। यह क्यू को ओ (1) सबसे विकृत समय में संचालन के साथ निरंतर रहने की स्वीकृति देता है, लेकिन मेमोइज़ेशन के साथ लेज़ी सूचियों की आवश्यकता होती है। दूसरा, जिसमें कोई लेज़ी सूची नहीं है और न ही मेमोइज़ेशन भागों के अंत में प्रस्तुत किया गया है। इसका परिशोधन समय O(1) है यदि दृढ़ता का उपयोग नहीं किया जाता है; लेकिन किसी संचालन की सबसे विकृत समय की जटिलता O(n) है जहां n डबल-एंडेड क्यू में तत्वों की संख्या है। | ||
आइए पुनः कॉल करते हैं कि, एक सूची के लिए <code>l</code>, <code>|l|</code> इसकी लंबाई को दर्शाता है, कि <code>NIL</code> एक रिक्त सूची का प्रतिनिधित्व करता है और <code>CONS(h, t)</code> उस सूची का प्रतिनिधित्व करता है जिसका शीर्ष | आइए पुनः कॉल करते हैं कि, एक सूची के लिए <code>l</code>, <code>|l|</code> इसकी लंबाई को दर्शाता है, कि <code>NIL</code> एक रिक्त सूची का प्रतिनिधित्व करता है और <code>CONS(h, t)</code> उस सूची का प्रतिनिधित्व करता है जिसका शीर्ष <code>h</code> है और टैल <code>t</code> है। फ़ंक्शन <code>drop(i, l)</code> और <code>take(i, l)</code> क्रमशः <code>l</code> के पहले <code>i</code>तत्वों और <code>i</code> के पहले <code>l</code>, तत्वों के बिना सूची<code>देते हैं। या, यदि |l|< i</code>, वे क्रमशः रिक्त सूची और <code>l</code> देते है। | ||
==== लेज़ी पुनर्निर्माण और शेड्यूलिंग के माध्यम से वास्तविक समय डेक ==== | ==== लेज़ी पुनर्निर्माण और शेड्यूलिंग के माध्यम से वास्तविक समय डेक ==== | ||
एक डबल-एंडेड क्यू | एक डबल-एंडेड क्यू को सेक्स्टुपल (छ: गुना) <code>(len_front, front, tail_front, len_rear, rear, tail_rear)</code> के रूप में दर्शाया गया है जहाँ <code>front</code> एक [[लिंक्ड सूची]] है जिसमें क्यू फ्रंट लंबाई की <code>len_front</code> होता है इसी प्रकार, <code>rear</code> एक लिंक की गई सूची है जो क्यू के बैक लंबाई की <code>len_rear</code>के हिस्से का प्रतिनिधित्व करती है साथ ही यह भी निश्चित करता है कि <code>|front| ≤ 2|rear|+1</code> और <code>|rear| ≤ 2|front|+1</code> - सामान्य रूप से, इसका तात्पर्य है कि फ्रंट और बैक दोनों में एक तिहाई माइनस एक और दो तिहाई प्लस एक तत्व होता है। अंत में, <code>tail_front</code> और <code>tail_rear</code> की <code>front</code> और का <code>rear</code> है, वे उस गतिविधि को शेड्यूल करने की स्वीकृति देते हैं जहां कुछ लेज़ी संचालन को अनिवार्य किया जाता है। ध्यान दें कि, जब एक डबल-एंडेड क्यू में <code>n</code> फ्रंट की सूची में तत्व और <code>n</code> बैक की सूची में तत्व सम्मिलित होता है, उसके बाद असमानता अपरिवर्तनीय <code>i</code> निवेशन और <code>d</code> विलोपन के बाद पूर्ण रहती है जब <code>(i+d) ≤ n/2</code>अर्थात्, प्रत्येक पुनर्संतुलन के बीच अधिकतम <code>n/2</code> संक्रियाएँ हो सकती हैं। | ||
आइए सबसे पहले डेक के | आइए सबसे पहले पहले डेक कॉन्स, हेड और टेल के फ्रंट को प्रभावित करने वाले विभिन्न संक्रियाओ का कार्यान्वयन दें। वे कार्यान्वयन आवश्यक रूप से अपरिवर्तनीय का सम्मान नहीं करते हैं। दूसरी बार में हम समझाएंगे कि एक डेक को कैसे संशोधित किया जाए जो इनवेरिएंट को पूर्ण नहीं करता है जो इसे पूर्ण करता है। हालाँकि, वे अपरिवर्तनीय का उपयोग करते हैं, जिसमें यदि फ्रंट रिक्त है, तो बैक के हिस्से में अधिकतम एक तत्व होता है। सूची के पिछले हिस्से को प्रभावित करने वाले संचालन समरूपता द्वारा समान रूप से परिभाषित किए गए हैं। | ||
<syntaxhighlight lang="sml"> | <syntaxhighlight lang="sml"> | ||
Line 76: | Line 72: | ||
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty | fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty | ||
</syntaxhighlight> | </syntaxhighlight> | ||
यह समझाने के लिए बनी हुई है कि किसी विधि | यह समझाने के लिए बनी हुई है कि किसी विधि <code>balance</code> को कैसे परिभाषित किया जाए जो डेक को पुन: संतुलित करता है यदि <code>insert'</code> या <code>tail</code> इंवरिएंट को तोड़ दिया। मेथड <code>insert</code> और <code>tail</code> पहले <code>insert'</code> और <code>tail'</code> लगाकर और फिर <code>balance</code> प्रयुक्त करके परिभाषित किया जा सकता है। | ||
<syntaxhighlight lang="sml"> | <syntaxhighlight lang="sml"> | ||
Line 92: | Line 88: | ||
else q | else q | ||
</syntaxhighlight> | </syntaxhighlight> | ||
जहाँ <code>rotateDrop(front, i, rear))</code> और <code>front</code> <code>drop(i, rear)</code>के संयोजन को प्रतिकृत करता है। वह<code>front' = rotateDrop(front, ceil_half_len, rear)</code> में निर्दिष्ट <code>front'</code> की तत्व <code>front</code> और की तत्व <code>rear</code> की तत्व जो पहले से ही <code>rear'</code>नहीं है <code>n</code> तत्व देता है। <math>O(n)</math> समय, हम लेज़ी का उपयोग यह सुनिश्चित करने के लिए करते हैं कि तत्वों को दो-दो से ड्रॉप कर जाए, प्रत्येक <code>tail'</code> और प्रत्येक <code>insert'</code> संचालन के समय दो ड्रॉप को किया जाता है। | |||
<syntaxhighlight lang="sml"> | |||
fun rotateDrop(front, i, rear) = | fun rotateDrop(front, i, rear) = | ||
if i < 2 then rotateRev(front, drop(i, rear), $NIL) | if i < 2 then rotateRev(front, drop(i, rear), $NIL) | ||
Line 100: | Line 96: | ||
$CONS (x, rotateDrop(front', j-2, drop(2, rear))) | $CONS (x, rotateDrop(front', j-2, drop(2, rear))) | ||
</syntaxhighlight> | </syntaxhighlight> | ||
जहाँ <code>rotateRev(front, middle, rear)</code> एक ऐसा फंक्शन है जो फ्रंट को प्रतिकृत करता है, उसके बाद मध्य प्रतिकृति, उसके बाद रियर होता है। इस फ़ंक्शन को लेज़ी का उपयोग करके भी परिभाषित किया गया है ताकि यह सुनिश्चित किया जा सके कि प्रत्येक <code>insert'</code> और <code>tail'</code> चरण के समय एक चरण के साथ इसकी गणना चरण दर चरण की जा सकती है। यह फ़ंक्शन उस इंवरिएंट का उपयोग करता है जो <code>|rear|-2|front|</code> 2 या 3 है। | |||
<syntaxhighlight lang="sml"> | |||
fun rotateRev(NIL, rear, a)= | fun rotateRev(NIL, rear, a)= | ||
reverse(rear++a) | reverse(rear++a) | ||
Line 108: | Line 104: | ||
CONS(x, rotateRev(front, drop(2, rear), reverse (take(2, rear))++a)) | CONS(x, rotateRev(front, drop(2, rear), reverse (take(2, rear))++a)) | ||
</syntaxhighlight> | </syntaxhighlight> | ||
जहाँ <code>++</code> दो सूचियों को जोड़ने वाला फ़ंक्शन है। | |||
==== | ==== लेज़ीनेस के बिना कार्यान्वयन ==== | ||
ध्यान दें कि, कार्यान्वयन के लेज़ी भाग के बिना, यह | ध्यान दें कि, कार्यान्वयन के लेज़ी भाग के बिना, यह {{math|''O''(1)}} परिशोधित समय क्यू में एक गैर-निरंतर कार्यान्वयन होगा। इस स्थिति में, सूचियाँ <code>tail_front</code> और <code>tail_rear</code> डबल-एंडेड क्यू के प्रतिनिधित्व से हटाया जा सकता है। | ||
== भाषा समर्थन == | == भाषा समर्थन == | ||
[[एडा (प्रोग्रामिंग भाषा)]] के कंटेनर सामान्य पैकेज | [[एडा (प्रोग्रामिंग भाषा)|एडीए (प्रोग्रामिंग भाषा)]] के कंटेनर क्रमशः गतिशील सरणी और लिंक्ड सूची कार्यान्वयन के लिए सामान्य पैकेज <code>Ada.Containers.Vectors</code> और <code>Ada.Containers.Doubly_Linked_Lists</code>प्रदान करते है। | ||
सी++ की [[मानक टेम्पलेट लाइब्रेरी]] क्लास टेम्पलेट | सी++ की [[मानक टेम्पलेट लाइब्रेरी]] एकाधिक सरणी और लिंक की गई सूची का कार्यान्वयन क्लास टेम्पलेट <code>std::डेक</code> और <code>std::list</code>प्रदान करती है। | ||
जावा 6 के अनुसार, जावा का | जावा 6 के अनुसार, जावा का संग्रहण रूपरेखा एक नया {{Javadoc:SE|java/util|Deque}} इंटरफ़ेस प्रदान करता है जो दोनों सिरों पर प्रविष्टि और हटाने की कार्यक्षमता प्रदान करता है। यह जैसे {{Javadoc:SE|java/util|ArrayDeque}} (जावा 6 में भी नया) और {{Javadoc:SE|java/util|LinkedList}}क्लासेस द्वारा कार्यान्वित किया जाता है, क्रमशः गतिशील सरणी और लिंक्ड सूची कार्यान्वयन प्रदान करता है। हालांकि <code>ArrayDeque</code>, इसके नाम के विपरीत, रैंडम एक्सेस का समर्थन नहीं करता है। | ||
जावास्क्रिप्ट के [https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array Array प्रोटोटाइप] और [[पर्ल]] की सरणियों को दोनों को हटाने के लिए | जावास्क्रिप्ट के [https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array Array प्रोटोटाइप] और [[पर्ल]] की सरणियों को दोनों को हटाने के लिए ([http://perldoc.perl.org /functions/shift.html shift] और [http://perldoc.perl.org/functions/pop.html pop]) और जोड़ने ([http://perldoc.perl.org/functions/unshift.html unshift] और [http://perldoc.perl.org/functions/push.html push]) दोनों के लिए मूल समर्थन है। | ||
पायथन 2.4 ने | पायथन 2.4 ने डेक वस्तुओं के समर्थन के साथ <code>collections</code> [https://docs.python.org/3/library/collections.html#deque-objects डेक ऑब्जेक्ट्स] मॉड्यूल प्रस्तुत किया। इसे निश्चित-लंबाई वाली उप-सरणियों की दोगुनी लिंक्ड सूची का उपयोग करके कार्यान्वित किया जाता है। | ||
हाइपरटेक्स्ट पूर्वप्रक्रमक 5.3 के अनुसार, हाइपरटेक्स्ट पूर्वप्रक्रमक के संरचित प्रोग्रामिंग भाषा एक्सटेंशन में 'SplDoublyLinkedList' क्लास सम्मिलित है जिसका उपयोग डेक डाटा संरचना को प्रयुक्त करने के लिए किया जा सकता है। पहले डेक संरचना बनाने के लिए सरणी फ़ंक्शन ऐरे_शिफ्ट/अनशिफ्ट/पॉप/पुश का उपयोग इसके अतिरिक्त किया जाना था। | |||
[[ग्लासगो हास्केल कंपाइलर]] [http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html Data.Sequence] मॉड्यूल [[हास्केल (प्रोग्रामिंग भाषा)]] में एक | [[ग्लासगो हास्केल कंपाइलर]] [http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html Data.Sequence] मॉड्यूल [[हास्केल (प्रोग्रामिंग भाषा)]] में एक उपयुक्त, कार्यात्मक डेक संरचना प्रयुक्त करता है। कार्यान्वयन 2–3 फिंगर ट्री का उपयोग करता है जो आकार के साथ एनोटेट किए गए हैं। विशुद्ध रूप से कार्यात्मक (इस प्रकार भी निरंतर डेटा संरचना) डबल क्यू को प्रयुक्त करने के लिए अन्य (तेज) संभावनाएं हैं (अधिकतम लेज़ी मूल्यांकन का उपयोग करते हुए)।<ref name="functional"/><ref>Adam L. Buchsbaum and Robert E. Tarjan. Confluently persistent deques via data structural bootstrapping. Journal of Algorithms, 18(3):513–547, May 1995. (pp. 58, 101, 125)</ref> कापलान और टारजन सबसे पहले इष्टतम संचार परसिस्टेंट कैटेनेबल डेक्स को प्रयुक्त करने वाले थे।<ref>Haim Kaplan and Robert E. Tarjan. Purely functional representations of catenable sorted lists. In ACM Symposium on Theory of Computing, pages 202–211, May 1996. (pp. 4, 82, 84, 124)</ref> उनका कार्यान्वयन पूरी तरह से कार्यात्मक था इस अर्थ में कि यह लेज़ी मूल्यांकन का उपयोग नहीं करता था। ओकासाकी ने बूटस्ट्रैप्ड डेटा संरचना के साथ लेज़ी मूल्यांकन का उपयोग करके डेटा संरचना को सरल बनाया और प्रदर्शन सीमा को सबसे विकृत स्थिति से परिशोधित कर दिया। कापलान, ओकासाकी, और टारजन ने एक सरल, गैर-बूटस्ट्रैप्ड, परिशोधित संस्करण का उत्पादन किया जिसे या तो लेज़ी मूल्यांकन का उपयोग करके या व्यापक रूप से अभी भी प्रतिबंधित फैशन में म्यूटेशन का उपयोग करके अधिक कुशलता से प्रयुक्त किया जा सकता है। मिहासौ और टारजन ने एक सरल (लेकिन अभी भी अत्यधिक जटिल) कैटेनेबल डेक्स का दृढ़ता से कार्यात्मक कार्यान्वयन बनाया, और दृढ़ता से पूरी तरह कार्यात्मक गैर-कैटेनेबल डेक का बहुत सरल कार्यान्वयन भी किया, जिनमें से दोनों में इष्टतम सबसे विकृत स्थिति सीमा है। | ||
आरयूएसटी का <code>std::collections</code> में [https://doc.rust-lang.org/std/collections/struct.VecDeque.html VecDeque] सम्मिलित है जो बढ़ने योग्य रिंग बफर का उपयोग करके डबल-एंडेड क्यू को प्रयुक्त करता है। | |||
== जटिलता == | == जटिलता == | ||
Line 135: | Line 131: | ||
== एप्लीकेशन == | == एप्लीकेशन == | ||
[[File:Back button history (Ecosia browser - Google Pixel 4a) - Google Android 12 (cropped).png|thumb|[[वेब ब्राउज़िंग इतिहास]] को संग्रहीत करने के लिए एक डबल-एंडेड क्यू | [[File:Back button history (Ecosia browser - Google Pixel 4a) - Google Android 12 (cropped).png|thumb|[[वेब ब्राउज़िंग इतिहास]] को संग्रहीत करने के लिए एक डबल-एंडेड क्यू का उपयोग किया जा सकता है: क्यू के अंत में नई वेबसाइटें जोड़ी जाती हैं, जबकि इतिहास बहुत बड़ा होने पर सबसे पुरानी प्रविष्टियां हटा दी जाएंगी। जब कोई उपयोगकर्ता पिछले एक घंटे के ब्राउज़िंग इतिहास को साफ़ करने के लिए कहता है, तो सबसे हाल ही में जोड़ी गई प्रविष्टियाँ हटा दी जाती हैं।]]उदाहरण जहां डेक का उपयोग किया जा सकता है वह कार्य स्टालिंग एल्गोरिथम है।<ref name="jacm">{{cite journal |last1=Blumofe |first1=Robert D. |first2=Charles E. |last2=Leiserson |author-link2=Charles E. Leiserson |title=काम चोरी करके मल्टीथ्रेडेड कंप्यूटेशंस शेड्यूल करना|journal=J ACM |volume=46 |issue=5 |year=1999 |pages=720–748 |url=http://supertech.csail.mit.edu/papers/ft_gateway.pdf |doi=10.1145/324133.324234|s2cid=5428476 }}</ref> यह एल्गोरिथम कई प्रोसेसरों के लिए टास्क शेड्यूलिंग को प्रयुक्त करता है। प्रत्येक प्रोसेसर के लिए निष्पादित किए जाने वाले थ्रेड्स के साथ एक अलग डेक बनाए रखा जाता है। अगले थ्रेड को निष्पादित करने के लिए, प्रोसेसर को डेक से पहला तत्व मिलता है (पहले तत्व डेक संचालन को हटाकर)। यदि वर्तमान थ्रेड फोर्क होता है, तो इसे डीक्यू के सामने वापस रखा जाता है (फ्रंट तत्व निर्दिष्ट) और एक नया थ्रेड निष्पादित किया जाता है। जब प्रोसेसर में से एक अपने स्वयं के थ्रेड्स का निष्पादन पूरा करता है (अर्थात इसका डेक रिक्त है), तो यह दूसरे प्रोसेसर से एक थ्रेड 'स्टील' सकता है: यह दूसरे प्रोसेसर के डेक से अंतिम तत्व प्राप्त करता है (बैक तत्व को हटा दें) और इसे निष्पादित करता है। समानांतर प्रोग्रामिंग के लिए इंटेल के थ्रेडिंग बिल्डिंग ब्लॉक्स (टीबीबी) लाइब्रेरी द्वारा कार्य स्टालिंग एल्गोरिदम का उपयोग किया जाता है। | ||
== यह भी देखें == | == यह भी देखें == | ||
* पाइप (यूनिक्स) | * पाइप (यूनिक्स) | ||
* क्यू | * क्यू (डेटा संरचना) | ||
*[[प्राथमिकता कतार|प्राथमिकता क्यू]] | *[[प्राथमिकता कतार|प्राथमिकता क्यू]] | ||
Line 155: | Line 151: | ||
{{Data structures}} | {{Data structures}} | ||
[[Category: | [[Category:Collapse templates]] | ||
[[Category:Created On 24/02/2023]] | [[Category:Created On 24/02/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:सार डेटा प्रकार]] |
Latest revision as of 10:32, 7 March 2023
कंप्यूटर विज्ञान में, डबल-एंडेड क्यू (संक्षिप्त रूप से डीक्यू, स्पष्ट 'डेक', जैसे चेक[1]) एक अमूर्त डेटा प्रकार है जो एक क्यू (डेटा संरचना) को सामान्यीकृत करता है, जिसके लिए तत्वों को फ्रंट (हेड) या बैक (टैल) से जोड़ा या हटाया जा सकता है।[2] इसे प्रायः हेड-टेल लिंक्ड सूची भी कहा जाता है, हालांकि सही से यह डीक्यू की एक विशिष्ट डेटा संरचना कार्यान्वयन को संदर्भित करता है (नीचे देखें)।
नामोल्लेखन कन्वेंशन
डेक को कभी-कभी डीक्यू भी लिखा जाता है, लेकिन इस प्रयोग को सामान्य रूप से तकनीकी साहित्य या तकनीकी लेखन में बहिष्कृत किया जाता है क्योंकि डीक्यू भी एक क्रिया है जिसका अर्थ क्यू से हटाना है। फिर भी, कई पुस्तकालय (कम्प्यूटिंग) और कुछ लेखक, जैसे अहो, होपक्रॉफ्ट, और उल्मैन ने अपनी पाठ्यपुस्तक डेटा संरचना और एल्गोरिदम में, इसे डीक्यू बताया है। ''कॉन्सेप्ट्स इन प्रोग्रामिंग भाषा'' के लेखक जॉन सी मिशेल भी इस शब्दावली का उपयोग करते हैं।
विभेद और सबटाइप
यह क्यू अमूर्त डेटा टाइप या ''प्रथम प्रवेश प्रथम निर्गम'' सूची (फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)) से भिन्न है, जहाँ तत्वों को केवल एक एंड (सिरे) पर जोड़ा जा सकता है और दूसरे से हटाया जा सकता है। इस सामान्य डेटा क्लास के कुछ संभावित सबटाइप हैं:
- एक इनपुट-प्रतिबंधित डेक वह है जहां दोनों सिरों से विलोपन किया जा सकता है, लेकिन प्रविष्टि केवल एक एंड पर किया जा सकता है।
- एक आउटपुट-प्रतिबंधित डेक वह है जहां दोनों सिरों पर प्रविष्टि किया जा सकता है, लेकिन विलोपन केवल एक एंड से किया जा सकता है।
कंप्यूटिंग, क्यू (डेटा संरचना) और स्टैक (डेटा संरचना) में आधारभूत और सबसे सामान्य सूची प्रकार दोनों को डेक की विशेषज्ञता माना जा सकता है, और डेक का उपयोग करके कार्यान्वित किया जा सकता है।
संचालन
एक डेक पर आधारभूत संचालन दोनों एंड पर एनक्यू और डीक्यू हैं। सामान्य रूप से पीक (डेटा टाइप संचालन) संचालन को भी प्रयुक्त किया जाता है, जो उस अंत में मूल्य को बिना डीक्यू किए वापस कर देता है।
भाषाओं के बीच नाम भिन्न होते हैं; प्रमुख कार्यान्वयन में सम्मिलित हैं:
संचालन | सामान्य नाम | एडीए | C++ | जावा | व्यावहारिक निष्कर्षण | हाइपरटेक्स्ट प्रीप्रोसेसर | पायथन | रूबी | आरयूएसटी | जावास्क्रिप्ट |
---|---|---|---|---|---|---|---|---|---|---|
पीछे की ओर तत्व निर्दिष्ट करे | इंजेक्ट, स्नोक, पुश | Append |
push_back |
offerLast |
push |
array_push |
append |
push
|
push_back |
push
|
सामने तत्व निर्दिष्ट करे | पुश, कॉन्स | Prepend |
push_front |
offerFirst |
unshift |
array_unshift |
appendleft |
unshift
|
push_front |
unshift
|
अंतिम तत्व को हटा दें | इजेक्ट | Delete_Last |
pop_back |
pollLast |
pop |
array_pop |
pop |
pop
|
pop_back |
pop
|
पहले तत्व को हटा दें | पॉप | Delete_First |
pop_front |
pollFirst |
shift |
array_shift |
popleft |
shift
|
pop_front |
shift
|
अंतिम तत्व का परीक्षण | पीक | Last_Element |
back |
peekLast |
$array[-1] |
end |
<obj>[-1] |
last
|
back |
<obj>.at(-1)
|
पहले तत्व का परीक्षण | First_Element |
front |
peekFirst |
$array[0] |
reset |
<obj>[0] |
first
|
front |
<obj>[0]
|
कार्यान्वयन
डेक को प्रभावी रूप से प्रयुक्त करने के कम से कम दो सामान्य तरीके हैं: एक संशोधित गतिशील सरणी के साथ या एक दोगुनी लिंक्ड सूची के साथ।
गतिशील सरणी दृष्टिकोण गतिशील सरणी के एक प्रकार का उपयोग करता है जो दोनों सिरों से बढ़ सकता है, जिसे कभी-कभी सरणी डेक कहा जाता है। इन सरणी डीक्यू में एक गतिशील सरणी के सभी गुण होते हैं, जैसे कि निरंतर-समय यादृच्छिक अभिगम, संदर्भ का अच्छा स्थान, और बीच में अप्रभावी प्रविष्टि/हटाना, इसके अतिरिक्त दोनों सिरों पर परिशोधित निरंतर-समय प्रविष्टि/हटाना जिसमे सिर्फ एक एंड सम्मिलित है। इसमे तीन सामान्य कार्यान्वयन में सम्मिलित हैं:
- डेक तत्व को एक परिपत्र बफ़र में संग्रहीत करना, और केवल तभी आकार बदलना जब बफ़र पूर्ण हो जाता है। इससे आकार बदलने की आवृत्ति कम हो जाती है।
- अंतर्निहित सरणी के केंद्र से डेक तत्व आवंटित करना, और अंत तक पहुंचने पर अंतर्निहित सरणी का आकार बदलना। इस दृष्टिकोण को अधिक बार आकार बदलने और अधिक स्थान नष्ट करने की आवश्यकता हो सकती है, विशेषकर जब तत्व केवल एक एंड पर निर्दिष्ट किए जाते हैं।
- तत्व को कई छोटे सरणियों में संग्रहीत करना, आवश्यकतानुसार प्रारंभ या अंत में अतिरिक्त सरणियाँ आवंटित करना। प्रत्येक छोटे सरणियों में पॉइंटर्स युक्त एक गतिशील सरणी रखकर इंडेक्सिंग को कार्यान्वित किया जाता है।
पूर्ण रूप से कार्यात्मक कार्यान्वयन
डबल-एंडेड कतारों को विशुद्ध रूप से कार्यात्मक डेटा संरचना के रूप में भी प्रयुक्त किया जा सकता है।[3]: 115 कार्यान्वयन के दो संस्करण सम्मिलित हैं। पहला, जिसे 'वास्तविक समय डेक' कहा जाता है, नीचे प्रस्तुत किया गया है। यह क्यू को ओ (1) सबसे विकृत समय में संचालन के साथ निरंतर रहने की स्वीकृति देता है, लेकिन मेमोइज़ेशन के साथ लेज़ी सूचियों की आवश्यकता होती है। दूसरा, जिसमें कोई लेज़ी सूची नहीं है और न ही मेमोइज़ेशन भागों के अंत में प्रस्तुत किया गया है। इसका परिशोधन समय O(1) है यदि दृढ़ता का उपयोग नहीं किया जाता है; लेकिन किसी संचालन की सबसे विकृत समय की जटिलता O(n) है जहां n डबल-एंडेड क्यू में तत्वों की संख्या है।
आइए पुनः कॉल करते हैं कि, एक सूची के लिए l
, |l|
इसकी लंबाई को दर्शाता है, कि NIL
एक रिक्त सूची का प्रतिनिधित्व करता है और CONS(h, t)
उस सूची का प्रतिनिधित्व करता है जिसका शीर्ष h
है और टैल t
है। फ़ंक्शन drop(i, l)
और take(i, l)
क्रमशः l
के पहले i
तत्वों और i
के पहले l
, तत्वों के बिना सूचीदेते हैं। या, यदि |l|< i
, वे क्रमशः रिक्त सूची और l
देते है।
लेज़ी पुनर्निर्माण और शेड्यूलिंग के माध्यम से वास्तविक समय डेक
एक डबल-एंडेड क्यू को सेक्स्टुपल (छ: गुना) (len_front, front, tail_front, len_rear, rear, tail_rear)
के रूप में दर्शाया गया है जहाँ front
एक लिंक्ड सूची है जिसमें क्यू फ्रंट लंबाई की len_front
होता है इसी प्रकार, rear
एक लिंक की गई सूची है जो क्यू के बैक लंबाई की len_rear
के हिस्से का प्रतिनिधित्व करती है साथ ही यह भी निश्चित करता है कि |front| ≤ 2|rear|+1
और |rear| ≤ 2|front|+1
- सामान्य रूप से, इसका तात्पर्य है कि फ्रंट और बैक दोनों में एक तिहाई माइनस एक और दो तिहाई प्लस एक तत्व होता है। अंत में, tail_front
और tail_rear
की front
और का rear
है, वे उस गतिविधि को शेड्यूल करने की स्वीकृति देते हैं जहां कुछ लेज़ी संचालन को अनिवार्य किया जाता है। ध्यान दें कि, जब एक डबल-एंडेड क्यू में n
फ्रंट की सूची में तत्व और n
बैक की सूची में तत्व सम्मिलित होता है, उसके बाद असमानता अपरिवर्तनीय i
निवेशन और d
विलोपन के बाद पूर्ण रहती है जब (i+d) ≤ n/2
अर्थात्, प्रत्येक पुनर्संतुलन के बीच अधिकतम n/2
संक्रियाएँ हो सकती हैं।
आइए सबसे पहले पहले डेक कॉन्स, हेड और टेल के फ्रंट को प्रभावित करने वाले विभिन्न संक्रियाओ का कार्यान्वयन दें। वे कार्यान्वयन आवश्यक रूप से अपरिवर्तनीय का सम्मान नहीं करते हैं। दूसरी बार में हम समझाएंगे कि एक डेक को कैसे संशोधित किया जाए जो इनवेरिएंट को पूर्ण नहीं करता है जो इसे पूर्ण करता है। हालाँकि, वे अपरिवर्तनीय का उपयोग करते हैं, जिसमें यदि फ्रंट रिक्त है, तो बैक के हिस्से में अधिकतम एक तत्व होता है। सूची के पिछले हिस्से को प्रभावित करने वाले संचालन समरूपता द्वारा समान रूप से परिभाषित किए गए हैं।
empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =
(len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =
(len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty
यह समझाने के लिए बनी हुई है कि किसी विधि balance
को कैसे परिभाषित किया जाए जो डेक को पुन: संतुलित करता है यदि insert'
या tail
इंवरिएंट को तोड़ दिया। मेथड insert
और tail
पहले insert'
और tail'
लगाकर और फिर balance
प्रयुक्त करके परिभाषित किया जा सकता है।
fun balance(q as (len_front, front, tail_front, len_rear, rear, tail_rear)) =
let floor_half_len = (len_front + len_rear) / 2 in
let ceil_half_len = len_front + len_rear - floor_half_len in
if len_front > 2*len_rear+1 then
let val front' = take(ceil_half_len, front)
val rear' = rotateDrop(rear, floor_half_len, front)
in (ceil_half_len, front', front', floor_half_len, rear', rear')
else if len_front > 2*len_rear+1 then
let val rear' = take(floor_half_len, rear)
val front' = rotateDrop(front, ceil_half_len, rear)
in (ceil_half_len, front', front', floor_half_len, rear', rear')
else q
जहाँ rotateDrop(front, i, rear))
और front
drop(i, rear)
के संयोजन को प्रतिकृत करता है। वहfront' = rotateDrop(front, ceil_half_len, rear)
में निर्दिष्ट front'
की तत्व front
और की तत्व rear
की तत्व जो पहले से ही rear'
नहीं है n
तत्व देता है। समय, हम लेज़ी का उपयोग यह सुनिश्चित करने के लिए करते हैं कि तत्वों को दो-दो से ड्रॉप कर जाए, प्रत्येक tail'
और प्रत्येक insert'
संचालन के समय दो ड्रॉप को किया जाता है।
fun rotateDrop(front, i, rear) =
if i < 2 then rotateRev(front, drop(i, rear), $NIL)
else let $CONS(x, front') = front in
$CONS (x, rotateDrop(front', j-2, drop(2, rear)))
जहाँ rotateRev(front, middle, rear)
एक ऐसा फंक्शन है जो फ्रंट को प्रतिकृत करता है, उसके बाद मध्य प्रतिकृति, उसके बाद रियर होता है। इस फ़ंक्शन को लेज़ी का उपयोग करके भी परिभाषित किया गया है ताकि यह सुनिश्चित किया जा सके कि प्रत्येक insert'
और tail'
चरण के समय एक चरण के साथ इसकी गणना चरण दर चरण की जा सकती है। यह फ़ंक्शन उस इंवरिएंट का उपयोग करता है जो |rear|-2|front|
2 या 3 है।
fun rotateRev(NIL, rear, a)=
reverse(rear++a)
fun rotateRev(CONS(x, front), rear, a)=
CONS(x, rotateRev(front, drop(2, rear), reverse (take(2, rear))++a))
जहाँ ++
दो सूचियों को जोड़ने वाला फ़ंक्शन है।
लेज़ीनेस के बिना कार्यान्वयन
ध्यान दें कि, कार्यान्वयन के लेज़ी भाग के बिना, यह O(1) परिशोधित समय क्यू में एक गैर-निरंतर कार्यान्वयन होगा। इस स्थिति में, सूचियाँ tail_front
और tail_rear
डबल-एंडेड क्यू के प्रतिनिधित्व से हटाया जा सकता है।
भाषा समर्थन
एडीए (प्रोग्रामिंग भाषा) के कंटेनर क्रमशः गतिशील सरणी और लिंक्ड सूची कार्यान्वयन के लिए सामान्य पैकेज Ada.Containers.Vectors
और Ada.Containers.Doubly_Linked_Lists
प्रदान करते है।
सी++ की मानक टेम्पलेट लाइब्रेरी एकाधिक सरणी और लिंक की गई सूची का कार्यान्वयन क्लास टेम्पलेट std::डेक
और std::list
प्रदान करती है।
जावा 6 के अनुसार, जावा का संग्रहण रूपरेखा एक नया Deque
इंटरफ़ेस प्रदान करता है जो दोनों सिरों पर प्रविष्टि और हटाने की कार्यक्षमता प्रदान करता है। यह जैसे ArrayDeque
(जावा 6 में भी नया) और LinkedList
क्लासेस द्वारा कार्यान्वित किया जाता है, क्रमशः गतिशील सरणी और लिंक्ड सूची कार्यान्वयन प्रदान करता है। हालांकि ArrayDeque
, इसके नाम के विपरीत, रैंडम एक्सेस का समर्थन नहीं करता है।
जावास्क्रिप्ट के Array प्रोटोटाइप और पर्ल की सरणियों को दोनों को हटाने के लिए (/functions/shift.html shift और pop) और जोड़ने (unshift और push) दोनों के लिए मूल समर्थन है।
पायथन 2.4 ने डेक वस्तुओं के समर्थन के साथ collections
डेक ऑब्जेक्ट्स मॉड्यूल प्रस्तुत किया। इसे निश्चित-लंबाई वाली उप-सरणियों की दोगुनी लिंक्ड सूची का उपयोग करके कार्यान्वित किया जाता है।
हाइपरटेक्स्ट पूर्वप्रक्रमक 5.3 के अनुसार, हाइपरटेक्स्ट पूर्वप्रक्रमक के संरचित प्रोग्रामिंग भाषा एक्सटेंशन में 'SplDoublyLinkedList' क्लास सम्मिलित है जिसका उपयोग डेक डाटा संरचना को प्रयुक्त करने के लिए किया जा सकता है। पहले डेक संरचना बनाने के लिए सरणी फ़ंक्शन ऐरे_शिफ्ट/अनशिफ्ट/पॉप/पुश का उपयोग इसके अतिरिक्त किया जाना था।
ग्लासगो हास्केल कंपाइलर Data.Sequence मॉड्यूल हास्केल (प्रोग्रामिंग भाषा) में एक उपयुक्त, कार्यात्मक डेक संरचना प्रयुक्त करता है। कार्यान्वयन 2–3 फिंगर ट्री का उपयोग करता है जो आकार के साथ एनोटेट किए गए हैं। विशुद्ध रूप से कार्यात्मक (इस प्रकार भी निरंतर डेटा संरचना) डबल क्यू को प्रयुक्त करने के लिए अन्य (तेज) संभावनाएं हैं (अधिकतम लेज़ी मूल्यांकन का उपयोग करते हुए)।[3][4] कापलान और टारजन सबसे पहले इष्टतम संचार परसिस्टेंट कैटेनेबल डेक्स को प्रयुक्त करने वाले थे।[5] उनका कार्यान्वयन पूरी तरह से कार्यात्मक था इस अर्थ में कि यह लेज़ी मूल्यांकन का उपयोग नहीं करता था। ओकासाकी ने बूटस्ट्रैप्ड डेटा संरचना के साथ लेज़ी मूल्यांकन का उपयोग करके डेटा संरचना को सरल बनाया और प्रदर्शन सीमा को सबसे विकृत स्थिति से परिशोधित कर दिया। कापलान, ओकासाकी, और टारजन ने एक सरल, गैर-बूटस्ट्रैप्ड, परिशोधित संस्करण का उत्पादन किया जिसे या तो लेज़ी मूल्यांकन का उपयोग करके या व्यापक रूप से अभी भी प्रतिबंधित फैशन में म्यूटेशन का उपयोग करके अधिक कुशलता से प्रयुक्त किया जा सकता है। मिहासौ और टारजन ने एक सरल (लेकिन अभी भी अत्यधिक जटिल) कैटेनेबल डेक्स का दृढ़ता से कार्यात्मक कार्यान्वयन बनाया, और दृढ़ता से पूरी तरह कार्यात्मक गैर-कैटेनेबल डेक का बहुत सरल कार्यान्वयन भी किया, जिनमें से दोनों में इष्टतम सबसे विकृत स्थिति सीमा है।
आरयूएसटी का std::collections
में VecDeque सम्मिलित है जो बढ़ने योग्य रिंग बफर का उपयोग करके डबल-एंडेड क्यू को प्रयुक्त करता है।
जटिलता
- एक दोगुनी-लिंक्ड सूची कार्यान्वयन में और कोई आवंटन/डीललोकेशन ओवरहेड नहीं मानते हुए, सभी डेक संचालन की समय जटिलता ओ (1) है। इसके अतिरिक्त, बीच में सम्मिलन या विलोपन की समय जटिलता, एक पुनरावर्तक दिया गया है, ओ (1) है; हालाँकि, इंडेक्स द्वारा रैंडम एक्सेस की समय जटिलता O(n) है।
- एक बढ़ते सरणी में, सभी डेक संचालन की परिशोधित समय जटिलता हे (1) है। इसके अतिरिक्त, इंडेक्स द्वारा रैंडम एक्सेस की समय जटिलता O(1) है; लेकिन बीच में प्रविष्टि या विलोपन की समय जटिलता (एन) है।
एप्लीकेशन
उदाहरण जहां डेक का उपयोग किया जा सकता है वह कार्य स्टालिंग एल्गोरिथम है।[6] यह एल्गोरिथम कई प्रोसेसरों के लिए टास्क शेड्यूलिंग को प्रयुक्त करता है। प्रत्येक प्रोसेसर के लिए निष्पादित किए जाने वाले थ्रेड्स के साथ एक अलग डेक बनाए रखा जाता है। अगले थ्रेड को निष्पादित करने के लिए, प्रोसेसर को डेक से पहला तत्व मिलता है (पहले तत्व डेक संचालन को हटाकर)। यदि वर्तमान थ्रेड फोर्क होता है, तो इसे डीक्यू के सामने वापस रखा जाता है (फ्रंट तत्व निर्दिष्ट) और एक नया थ्रेड निष्पादित किया जाता है। जब प्रोसेसर में से एक अपने स्वयं के थ्रेड्स का निष्पादन पूरा करता है (अर्थात इसका डेक रिक्त है), तो यह दूसरे प्रोसेसर से एक थ्रेड 'स्टील' सकता है: यह दूसरे प्रोसेसर के डेक से अंतिम तत्व प्राप्त करता है (बैक तत्व को हटा दें) और इसे निष्पादित करता है। समानांतर प्रोग्रामिंग के लिए इंटेल के थ्रेडिंग बिल्डिंग ब्लॉक्स (टीबीबी) लाइब्रेरी द्वारा कार्य स्टालिंग एल्गोरिदम का उपयोग किया जाता है।
यह भी देखें
- पाइप (यूनिक्स)
- क्यू (डेटा संरचना)
- प्राथमिकता क्यू
संदर्भ
- ↑ Jesse Liberty; Siddhartha Rao; Bradley Jones. C++ in One Hour a Day, Sams Teach Yourself, Sixth Edition. Sams Publishing, 2009. ISBN 0-672-32941-7. Lesson 18: STL Dynamic Array Classes, pp. 486.
- ↑ 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 Deques, pp. 238–243.
- ↑ 3.0 3.1 Okasaki, Chris (September 1996). विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं (PDF) (Ph.D. thesis). Carnegie Mellon University. CMU-CS-96-177.
- ↑ Adam L. Buchsbaum and Robert E. Tarjan. Confluently persistent deques via data structural bootstrapping. Journal of Algorithms, 18(3):513–547, May 1995. (pp. 58, 101, 125)
- ↑ Haim Kaplan and Robert E. Tarjan. Purely functional representations of catenable sorted lists. In ACM Symposium on Theory of Computing, pages 202–211, May 1996. (pp. 4, 82, 84, 124)
- ↑ Blumofe, Robert D.; Leiserson, Charles E. (1999). "काम चोरी करके मल्टीथ्रेडेड कंप्यूटेशंस शेड्यूल करना" (PDF). J ACM. 46 (5): 720–748. doi:10.1145/324133.324234. S2CID 5428476.
बाहरी संबंध
- Type-safe open source डेक implementation at Comprehensive C Archive Network
- SGI STL Documentation: डेक<T, Alloc>
- Code Project: An In-Depth Study of the STL Deque Container
- Deque implementation in C
- VBScript implementation of stack, queue, डेक, and Red-Black Tree
- Multiple implementations of non-catenable deques in Haskell