डबल-एंडेड कतार: Difference between revisions

Revision as of 10:43, 2 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 तत्व देता है। $O(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.

बाहरी संबंध

[1] 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.

[2] 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.

[functional-3] 3.0 ^3.1 Okasaki, Chris (September 1996). विशुद्ध रूप से कार्यात्मक डेटा संरचनाएं (PDF) (Ph.D. thesis). Carnegie Mellon University. CMU-CS-96-177.

[4] 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)

[5] 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)

[jacm-6] Blumofe, Robert D.; Leiserson, Charles E. (1999). "काम चोरी करके मल्टीथ्रेडेड कंप्यूटेशंस शेड्यूल करना" (PDF). J ACM. 46 (5): 720–748. doi:10.1145/324133.324234. S2CID 5428476.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 3: / Line 3: @@
 ''डबल-एंडेड प्राथमिकता क्यू के साथ भ्रमित नहीं होना चाहिए।''
-[[कंप्यूटर विज्ञान]] में,  डबल-एंडेड क्यू  (संक्षिप्त रूप से डीक्यू, स्पष्ट 'डेक', जैसे चेक<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&ndash;243.</ref> इसे प्रायः हेड-टेल लिंक्ड सूची भी कहा जाता है, हालांकि सही से यह डीक्यू की एक विशिष्ट [[डेटा संरचना]]  ''कार्यान्वयन'' को संदर्भित करता है (नीचे देखें)।
+[[कंप्यूटर विज्ञान]] में, '''डबल-एंडेड क्यू''' (संक्षिप्त रूप से डीक्यू, स्पष्ट 'डेक', जैसे चेक<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&ndash;243.</ref> इसे प्रायः हेड-टेल लिंक्ड सूची भी कहा जाता है, हालांकि सही से यह '''डीक्यू''' की एक विशिष्ट [[डेटा संरचना]] ''कार्यान्वयन'' को संदर्भित करता है (नीचे देखें)।
 == नामोल्लेखन कन्वेंशन ==
-डेक को कभी-कभी डीक्यू भी लिखा जाता है, लेकिन इस प्रयोग को सामान्य रूप से तकनीकी साहित्य या तकनीकी लेखन में बहिष्कृत किया जाता है क्योंकि डीक्यू भी एक क्रिया है जिसका अर्थ क्यू  से हटाना है। फिर भी, कई [[ पुस्तकालय (कम्प्यूटिंग) | पुस्तकालय (कम्प्यूटिंग)]] और कुछ लेखक, जैसे अहो, होपक्रॉफ्ट, और उल्मैन ने अपनी पाठ्यपुस्तक डेटा संरचना और एल्गोरिदम में, इसे डीक्यू बताया है। <nowiki>''कॉन्सेप्ट्स इन प्रोग्रामिंग भाषा''</nowiki> के लेखक जॉन सी मिशेल भी इस शब्दावली का उपयोग करते हैं।
+डेक को कभी-कभी डीक्यू भी लिखा जाता है, लेकिन इस प्रयोग को सामान्य रूप से तकनीकी साहित्य या तकनीकी लेखन में बहिष्कृत किया जाता है क्योंकि डीक्यू भी एक क्रिया है जिसका अर्थ क्यू से हटाना है। फिर भी, कई [[ पुस्तकालय (कम्प्यूटिंग) |पुस्तकालय (कम्प्यूटिंग)]] और कुछ लेखक, जैसे अहो, होपक्रॉफ्ट, और उल्मैन ने अपनी पाठ्यपुस्तक डेटा संरचना और एल्गोरिदम में, इसे डीक्यू बताया है। <nowiki>''कॉन्सेप्ट्स इन प्रोग्रामिंग भाषा''</nowiki> के लेखक जॉन सी मिशेल भी इस शब्दावली का उपयोग करते हैं।
 == विभेद और सबटाइप ==
@@ Line 14: / Line 14: @@
 * एक आउटपुट-प्रतिबंधित डेक वह है जहां दोनों सिरों पर प्रविष्टि किया जा सकता है, लेकिन विलोपन केवल एक एंड से किया जा सकता है।
-कंप्यूटिंग, क्यू  (डेटा संरचना) और स्टैक (डेटा संरचना) में आधारभूत और सबसे सामान्य सूची प्रकार दोनों को डेक की विशेषज्ञता माना जा सकता है, और डेक का उपयोग करके कार्यान्वित किया जा सकता है।
+कंप्यूटिंग, क्यू (डेटा संरचना) और स्टैक (डेटा संरचना) में आधारभूत और सबसे सामान्य सूची प्रकार दोनों को डेक की विशेषज्ञता माना जा सकता है, और डेक का उपयोग करके कार्यान्वित किया जा सकता है।
 == संचालन ==
@@ Line 52: / Line 52: @@
 गतिशील सरणी दृष्टिकोण गतिशील सरणी के एक प्रकार का उपयोग करता है जो दोनों सिरों से बढ़ सकता है, जिसे कभी-कभी सरणी डेक कहा जाता है। इन सरणी डीक्यू में एक गतिशील सरणी के सभी गुण होते हैं, जैसे कि निरंतर-समय यादृच्छिक अभिगम, संदर्भ का अच्छा स्थान, और बीच में अप्रभावी प्रविष्टि/हटाना, इसके अतिरिक्त दोनों सिरों पर परिशोधित निरंतर-समय प्रविष्टि/हटाना जिसमे सिर्फ एक एंड सम्मिलित है। इसमे तीन सामान्य कार्यान्वयन में सम्मिलित हैं:
-* डेक सामग्री को एक परिपत्र बफ़र में संग्रहीत करना, और केवल तभी आकार बदलना जब बफ़र पूर्ण हो जाता है। इससे आकार बदलने की आवृत्ति कम हो जाती है।
+* डेक तत्व को एक परिपत्र बफ़र में संग्रहीत करना, और केवल तभी आकार बदलना जब बफ़र पूर्ण हो जाता है। इससे आकार बदलने की आवृत्ति कम हो जाती है।
-* अंतर्निहित सरणी के केंद्र से डेक सामग्री आवंटित करना, और अंत तक पहुंचने पर अंतर्निहित सरणी का आकार बदलना। इस दृष्टिकोण को अधिक बार आकार बदलने और अधिक स्थान नष्ट करने की आवश्यकता हो सकती है, विशेषकर जब तत्व केवल एक एंड पर निर्दिष्ट किए जाते हैं।
+* अंतर्निहित सरणी के केंद्र से डेक तत्व आवंटित करना, और अंत तक पहुंचने पर अंतर्निहित सरणी का आकार बदलना। इस दृष्टिकोण को अधिक बार आकार बदलने और अधिक स्थान नष्ट करने की आवश्यकता हो सकती है, विशेषकर जब तत्व केवल एक एंड पर निर्दिष्ट किए जाते हैं।
-* सामग्री को कई छोटे सरणियों में संग्रहीत करना, आवश्यकतानुसार प्रारंभ या अंत में अतिरिक्त सरणियाँ आवंटित करना। प्रत्येक छोटे सरणियों में पॉइंटर्स युक्त एक गतिशील सरणी रखकर इंडेक्सिंग को कार्यान्वित किया जाता है।
+* तत्व को कई छोटे सरणियों में संग्रहीत करना, आवश्यकतानुसार प्रारंभ या अंत में अतिरिक्त सरणियाँ आवंटित करना। प्रत्येक छोटे सरणियों में पॉइंटर्स युक्त एक गतिशील सरणी रखकर इंडेक्सिंग को कार्यान्वित किया जाता है।
 === पूर्ण रूप से कार्यात्मक कार्यान्वयन ===
-डबल-एंडेड कतारों को [[विशुद्ध रूप से कार्यात्मक डेटा संरचना]] के रूप में भी प्रयुक्त किया जा सकता है।<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 डबल-एंडेड क्यू में तत्वों की संख्या है।
+डबल-एंडेड कतारों को [[विशुद्ध रूप से कार्यात्मक डेटा संरचना]] के रूप में भी प्रयुक्त किया जा सकता है।<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>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>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) &leq; n/2</code>अर्थात्, प्रत्येक पुनर्संतुलन के बीच अधिकतम <code>n/2</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) &leq; n/2</code>अर्थात्, प्रत्येक पुनर्संतुलन के बीच अधिकतम <code>n/2</code> संक्रियाएँ हो सकती हैं।
 आइए सबसे पहले पहले डेक कॉन्स, हेड और टेल के फ्रंट को प्रभावित करने वाले विभिन्न संक्रियाओ का कार्यान्वयन दें। वे कार्यान्वयन आवश्यक रूप से अपरिवर्तनीय का सम्मान नहीं करते हैं। दूसरी बार में हम समझाएंगे कि एक डेक को कैसे संशोधित किया जाए जो इनवेरिएंट को पूर्ण नहीं करता है जो इसे पूर्ण करता है। हालाँकि, वे अपरिवर्तनीय का उपयोग करते हैं, जिसमें यदि फ्रंट रिक्त है, तो बैक के हिस्से में अधिकतम एक तत्व होता है। सूची के पिछले हिस्से को प्रभावित करने वाले संचालन समरूपता द्वारा समान रूप से परिभाषित किए गए हैं।
@@ Line 76: / Line 76: @@
 fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty
 </syntaxhighlight>
-यह समझाने के लिए बनी हुई है कि किसी विधि को कैसे परिभाषित किया जाए <code>balance</code> कि डेक अगर rebalance <code>insert'</code> या <code>tail</code> अपरिवर्तनीय तोड़ दिया। प्रक्रिया <code>insert</code> और <code>tail</code> पहले आवेदन करके परिभाषित किया जा सकता है <code>insert'</code> और <code>tail'</code> और फिर आवेदन करना <code>balance</code>.
+यह समझाने के लिए बनी हुई है कि किसी विधि <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">
@@ Line 92: / Line 92: @@
    else q
 </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> कार्यवाही।
+जहाँ <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">
@@ Line 100: / Line 100: @@
      $CONS (x, rotateDrop(front', j-2, drop(2, rear)))
 </syntaxhighlight>
-जहाँ <code>rotateRev(front, middle, rear)</code> एक ऐसा कार्य है जो सामने लौटाता है, उसके बाद मध्य उलटा होता है, उसके बाद पीछे होता है। इस फ़ंक्शन को आलस्य का उपयोग करके भी परिभाषित किया गया है ताकि यह सुनिश्चित किया जा सके कि प्रत्येक चरण के दौरान एक चरण के साथ इसकी गणना चरण दर चरण की जा सकती है <code>insert'</code> और <code>tail'</code> और लगातार समय ले रहा है। यह फ़ंक्शन उस अपरिवर्तनीय का उपयोग करता है <code>|rear|-2|front|</code> 2 या 3 है।
+जहाँ <code>rotateRev(front, middle, rear)</code> एक ऐसा फंक्शन है जो फ्रंट को प्रतिकृत करता है, उसके बाद मध्य प्रतिकृति, उसके बाद रियर होता है। इस फ़ंक्शन को लेज़ी का उपयोग करके भी परिभाषित किया गया है ताकि यह सुनिश्चित किया जा सके कि प्रत्येक <code>insert'</code> और <code>tail'</code> चरण के समय एक चरण के साथ इसकी गणना चरण दर चरण की जा सकती है। यह फ़ंक्शन उस इंवरिएंट का उपयोग करता है जो <code>|rear|-2|front|</code> 2 या 3 है।
 <syntaxhighlight lang="sml">
@@ Line 108: / Line 108: @@
    CONS(x, rotateRev(front, drop(2, rear), reverse (take(2, rear))++a))
 </syntaxhighlight>
-जहाँ <code>++</code> दो सूचियों को जोड़ने वाला कार्य है।
+जहाँ <code>++</code> दो सूचियों को जोड़ने वाला फ़ंक्शन है।
-==== आलस्य के बिना कार्यान्वयन ====
+==== लेज़ीनेस के बिना कार्यान्वयन ====
-ध्यान दें कि, कार्यान्वयन के लेज़ी भाग के बिना, यह क्यू  में एक गैर-निरंतर कार्यान्वयन होगा {{math|''O''(1)}} परिशोधित विश्लेषण। इस मामले में, सूचियाँ <code>tail_front</code> और <code>tail_rear</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>Ada.Containers.Vectors</code> और <code>Ada.Containers.Doubly_Linked_Lists</code>प्रदान करते है।
-सी++ की [[मानक टेम्पलेट लाइब्रेरी]] क्लास टेम्पलेट प्रदान करती है <code>std::डेक</code> और <code>std::list</code>, क्रमशः एकाधिक सरणी और लिंक्ड सूची कार्यान्वयन के लिए।
+सी++ की [[मानक टेम्पलेट लाइब्रेरी]] एकाधिक सरणी और लिंक की गई सूची का कार्यान्वयन क्लास टेम्पलेट <code>std::डेक</code> और <code>std::list</code>प्रदान करती है।
-जावा 6 के अनुसार, जावा का कलेक्शंस फ्रेमवर्क एक नया प्रदान करता है {{Javadoc:SE|java/util|Deque}} इंटरफ़ेस जो दोनों सिरों पर प्रविष्टि और हटाने की कार्यक्षमता प्रदान करता है। यह जैसे वर्गों द्वारा कार्यान्वित किया जाता है {{Javadoc:SE|java/util|ArrayDeque}} (जावा 6 में भी नया) और {{Javadoc:SE|java/util|LinkedList}}, क्रमशः डायनेमिक सरणी और लिंक्ड सूची कार्यान्वयन प्रदान करता है। हालांकि <code>ArrayDeque</code>, इसके नाम के विपरीत, रैंडम एक्सेस का समर्थन नहीं करता है।
+जावा 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 प्रोटोटाइप] और [[पर्ल]] की सरणियों को दोनों को हटाने के लिए मूल समर्थन है ([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]) दोनों सिरों पर तत्व।
+जावास्क्रिप्ट के [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 ने पेश किया <code>collections</code> [https://docs.python.org/3/library/collections.html#deque-objects डेक ऑब्जेक्ट्स] के समर्थन के साथ मॉड्यूल। इसे निश्चित-लंबाई वाली उप-सरणियों की दोगुनी लिंक्ड सूची का उपयोग करके कार्यान्वित किया जाता है।
+पायथन 2.4 ने डेक वस्तुओं के समर्थन के साथ <code>collections</code> [https://docs.python.org/3/library/collections.html#deque-objects डेक ऑब्जेक्ट्स] मॉड्यूल प्रस्तुत किया। इसे निश्चित-लंबाई वाली उप-सरणियों की दोगुनी लिंक्ड सूची का उपयोग करके कार्यान्वित किया जाता है।
-PHP 5.3 के अनुसार, PHP के SPL एक्सटेंशन में 'SplDoublyLinkedList' क्लास सम्मिलित है जिसका उपयोग Deque डेटास्ट्रक्चर को प्रयुक्त करने के लिए किया जा सकता है। पहले डेक संरचना बनाने के लिए सरणी फ़ंक्शन array_shift/unshift/pop/push का उपयोग इसके अतिरिक्त किया जाना था।
+हाइपरटेक्स्ट पूर्वप्रक्रमक 5.3 के अनुसार, हाइपरटेक्स्ट पूर्वप्रक्रमक के संरचित प्रोग्रामिंग भाषा एक्सटेंशन में 'SplDoublyLinkedList' क्लास सम्मिलित है जिसका उपयोग डेक डाटा संरचना को प्रयुक्त करने के लिए किया जा सकता है। पहले डेक संरचना बनाने के लिए सरणी फ़ंक्शन ऐरे_शिफ्ट/अनशिफ्ट/पॉप/पुश का उपयोग इसके अतिरिक्त किया जाना था।
-[[ग्लासगो हास्केल कंपाइलर]] [http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Sequence.html Data.Sequence] मॉड्यूल [[हास्केल (प्रोग्रामिंग भाषा)]] में एक कुशल, कार्यात्मक डेक संरचना प्रयुक्त करता है। कार्यान्वयन 2–3 ट्री | 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> उनका कार्यान्वयन पूरी तरह से कार्यात्मक था इस अर्थ में कि यह लेज़ी मूल्यांकन का उपयोग नहीं करता था। ओकासाकी ने बूटस्ट्रैप्ड डेटा संरचना के साथ लेज़ी मूल्यांकन का उपयोग करके डेटा संरचना को सरल बनाया और प्रदर्शन सीमा को सबसे खराब स्थिति से परिशोधित कर दिया। कापलान, ओकासाकी, और टारजन ने एक सरल, गैर-बूटस्ट्रैप्ड, परिशोधित संस्करण का उत्पादन किया जिसे या तो लेज़ी मूल्यांकन का उपयोग करके या व्यापक रूप से अभी भी प्रतिबंधित फैशन में म्यूटेशन का उपयोग करके अधिक कुशलता से प्रयुक्त किया जा सकता है। मिहासौ और टारजन ने एक सरल (लेकिन अभी भी अत्यधिक जटिल) कैटेनेबल डेक्स का सख्ती से कार्यात्मक कार्यान्वयन बनाया, और सख्ती से पूरी तरह कार्यात्मक गैर-कैटेनेबल डेक्स का बहुत सरल कार्यान्वयन भी किया, जिनमें से दोनों में इष्टतम सबसे खराब स्थिति सीमा है।
+[[ग्लासगो हास्केल कंपाइलर]] [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] सम्मिलित है जो बढ़ने योग्य रिंग बफर का उपयोग करके डबल-एंडेड क्यू  को प्रयुक्त करता है।
+आरयूएसटी का <code>std::collections</code> में [https://doc.rust-lang.org/std/collections/struct.VecDeque.html VecDeque] सम्मिलित है जो बढ़ने योग्य रिंग बफर का उपयोग करके डबल-एंडेड क्यू को प्रयुक्त करता है।
 == जटिलता ==
@@ Line 135: / Line 135: @@
 == एप्लीकेशन ==
-[[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> यह एल्गोरिथम कई प्रोसेसरों के लिए टास्क शेड्यूलिंग को प्रयुक्त करता है। प्रत्येक प्रोसेसर के लिए निष्पादित किए जाने वाले थ्रेड्स के साथ एक अलग डेक बनाए रखा जाता है। अगले थ्रेड को निष्पादित करने के लिए, प्रोसेसर को डेक से पहला तत्व मिलता है (पहले तत्व डेक संचालन को हटाकर)। यदि वर्तमान थ्रेड फोर्क होता है, तो इसे डीक्यू के सामने वापस रखा जाता है (फ्रंट तत्व निर्दिष्ट) और एक नया थ्रेड निष्पादित किया जाता है। जब प्रोसेसर में से एक अपने स्वयं के थ्रेड्स का निष्पादन पूरा करता है (अर्थात इसका डेक रिक्त है), तो यह दूसरे प्रोसेसर से एक थ्रेड 'स्टील' सकता है: यह दूसरे प्रोसेसर के डेक से अंतिम तत्व प्राप्त करता है (बैक तत्व को हटा दें) और इसे निष्पादित करता है। समानांतर प्रोग्रामिंग के लिए इंटेल के थ्रेडिंग बिल्डिंग ब्लॉक्स (टीबीबी) लाइब्रेरी द्वारा कार्य स्टालिंग एल्गोरिदम का उपयोग किया जाता है।
+[[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> यह एल्गोरिथम कई प्रोसेसरों के लिए टास्क शेड्यूलिंग को प्रयुक्त करता है। प्रत्येक प्रोसेसर के लिए निष्पादित किए जाने वाले थ्रेड्स के साथ एक अलग डेक बनाए रखा जाता है। अगले थ्रेड को निष्पादित करने के लिए, प्रोसेसर को डेक से पहला तत्व मिलता है (पहले तत्व डेक संचालन को हटाकर)। यदि वर्तमान थ्रेड फोर्क होता है, तो इसे डीक्यू के सामने वापस रखा जाता है (फ्रंट तत्व निर्दिष्ट) और एक नया थ्रेड निष्पादित किया जाता है। जब प्रोसेसर में से एक अपने स्वयं के थ्रेड्स का निष्पादन पूरा करता है (अर्थात इसका डेक रिक्त है), तो यह दूसरे प्रोसेसर से एक थ्रेड 'स्टील' सकता है: यह दूसरे प्रोसेसर के डेक से अंतिम तत्व प्राप्त करता है (बैक तत्व को हटा दें) और इसे निष्पादित करता है। समानांतर प्रोग्रामिंग के लिए इंटेल के थ्रेडिंग बिल्डिंग ब्लॉक्स (टीबीबी) लाइब्रेरी द्वारा कार्य स्टालिंग एल्गोरिदम का उपयोग किया जाता है।
 == यह भी देखें ==
 * पाइप (यूनिक्स)
-* क्यू  (डेटा संरचना)
+* क्यू (डेटा संरचना)
 *[[प्राथमिकता कतार|प्राथमिकता क्यू]]

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 10:43, 2 March 2023

Contents

नामोल्लेखन कन्वेंशन

विभेद और सबटाइप

संचालन

कार्यान्वयन

पूर्ण रूप से कार्यात्मक कार्यान्वयन

लेज़ी पुनर्निर्माण और शेड्यूलिंग के माध्यम से वास्तविक समय डेक

लेज़ीनेस के बिना कार्यान्वयन

भाषा समर्थन

जटिलता

एप्लीकेशन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डबल-एंडेड कतार: Difference between revisions

Revision as of 10:43, 2 March 2023

नामोल्लेखन कन्वेंशन

विभेद और सबटाइप

संचालन

कार्यान्वयन

पूर्ण रूप से कार्यात्मक कार्यान्वयन

लेज़ी पुनर्निर्माण और शेड्यूलिंग के माध्यम से वास्तविक समय डेक

लेज़ीनेस के बिना कार्यान्वयन

भाषा समर्थन

जटिलता

एप्लीकेशन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories