डबल-एंडेड कतार

कंप्यूटर विज्ञान में, डबल-एंडेड क्यू (संक्षिप्त रूप से डीक्यू, स्पष्ट 'डेक', जैसे चेक) एक अमूर्त डेटा प्रकार है जो एक क्यू (डेटा संरचना) को सामान्यीकृत करता है, जिसके लिए तत्वों को फ्रंट (हेड) या बैक (टैल) से जोड़ा या हटाया जा सकता है। इसे प्रायः हेड-टेल लिंक्ड सूची भी कहा जाता है, हालांकि सही से यह डीक्यू की एक विशिष्ट डेटा संरचना कार्यान्वयन को संदर्भित करता है (नीचे देखें)।

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

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

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

यह क्यू अमूर्त डेटा टाइप या ''प्रथम प्रवेश प्रथम निर्गम'' सूची (फीफो (कंप्यूटिंग और इलेक्ट्रॉनिक्स)) से भिन्न है, जहाँ तत्वों को केवल एक एंड (सिरे) पर जोड़ा जा सकता है और दूसरे से हटाया जा सकता है। इस सामान्य डेटा क्लास के कुछ संभावित सबटाइप हैं:

• एक इनपुट-प्रतिबंधित डेक वह है जहां दोनों सिरों से विलोपन किया जा सकता है, लेकिन प्रविष्टि केवल एक एंड पर किया जा सकता है।
• एक आउटपुट-प्रतिबंधित डेक वह है जहां दोनों सिरों पर प्रविष्टि किया जा सकता है, लेकिन विलोपन केवल एक एंड से किया जा सकता है।

कंप्यूटिंग, क्यू (डेटा संरचना) और स्टैक (डेटा संरचना) में आधारभूत और सबसे सामान्य सूची प्रकार दोनों को डेक की विशेषज्ञता माना जा सकता है, और डेक का उपयोग करके कार्यान्वित किया जा सकता है।

संचालन

एक डेक पर आधारभूत संचालन दोनों एंड पर एनक्यू और डीक्यू हैं। सामान्य रूप से पीक (डेटा टाइप संचालन) संचालन को भी प्रयुक्त किया जाता है, जो उस अंत में मूल्य को बिना डीक्यू किए वापस कर देता है।

भाषाओं के बीच नाम भिन्न होते हैं; प्रमुख कार्यान्वयन में सम्मिलित हैं:

संचालन	सामान्य नाम	एडीए	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]

कार्यान्वयन

डेक को प्रभावी रूप से प्रयुक्त करने के कम से कम दो सामान्य तरीके हैं: एक संशोधित गतिशील सरणी के साथ या एक दोगुनी लिंक्ड सूची के साथ।

गतिशील सरणी दृष्टिकोण गतिशील सरणी के एक प्रकार का उपयोग करता है जो दोनों सिरों से बढ़ सकता है, जिसे कभी-कभी सरणी डेक कहा जाता है। इन सरणी डीक्यू में एक गतिशील सरणी के सभी गुण होते हैं, जैसे कि निरंतर-समय यादृच्छिक अभिगम, संदर्भ का अच्छा स्थान, और बीच में अप्रभावी प्रविष्टि/हटाना, इसके अतिरिक्त दोनों सिरों पर परिशोधित निरंतर-समय प्रविष्टि/हटाना जिसमे सिर्फ एक एंड सम्मिलित है। इसमे तीन सामान्य कार्यान्वयन में सम्मिलित हैं:

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

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

डबल-एंडेड कतारों को विशुद्ध रूप से कार्यात्मक डेटा संरचना के रूप में भी प्रयुक्त किया जा सकता है। कार्यान्वयन के दो संस्करण सम्मिलित हैं। पहला, जिसे 'वास्तविक समय डेक' कहा जाता है, नीचे प्रस्तुत किया गया है। यह क्यू को ओ (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 फिंगर ट्री का उपयोग करता है जो आकार के साथ एनोटेट किए गए हैं। विशुद्ध रूप से कार्यात्मक (इस प्रकार भी निरंतर डेटा संरचना) डबल क्यू को प्रयुक्त करने के लिए अन्य (तेज) संभावनाएं हैं (अधिकतम लेज़ी मूल्यांकन का उपयोग करते हुए)। कापलान और टारजन सबसे पहले इष्टतम संचार परसिस्टेंट कैटेनेबल डेक्स को प्रयुक्त करने वाले थे। उनका कार्यान्वयन पूरी तरह से कार्यात्मक था इस अर्थ में कि यह लेज़ी मूल्यांकन का उपयोग नहीं करता था। ओकासाकी ने बूटस्ट्रैप्ड डेटा संरचना के साथ लेज़ी मूल्यांकन का उपयोग करके डेटा संरचना को सरल बनाया और प्रदर्शन सीमा को सबसे विकृत स्थिति से परिशोधित कर दिया। कापलान, ओकासाकी, और टारजन ने एक सरल, गैर-बूटस्ट्रैप्ड, परिशोधित संस्करण का उत्पादन किया जिसे या तो लेज़ी मूल्यांकन का उपयोग करके या व्यापक रूप से अभी भी प्रतिबंधित फैशन में म्यूटेशन का उपयोग करके अधिक कुशलता से प्रयुक्त किया जा सकता है। मिहासौ और टारजन ने एक सरल (लेकिन अभी भी अत्यधिक जटिल) कैटेनेबल डेक्स का दृढ़ता से कार्यात्मक कार्यान्वयन बनाया, और दृढ़ता से पूरी तरह कार्यात्मक गैर-कैटेनेबल डेक का बहुत सरल कार्यान्वयन भी किया, जिनमें से दोनों में इष्टतम सबसे विकृत स्थिति सीमा है।

आरयूएसटी का std::collections में VecDeque सम्मिलित है जो बढ़ने योग्य रिंग बफर का उपयोग करके डबल-एंडेड क्यू को प्रयुक्त करता है।

जटिलता

• एक दोगुनी-लिंक्ड सूची कार्यान्वयन में और कोई आवंटन/डीललोकेशन ओवरहेड नहीं मानते हुए, सभी डेक संचालन की समय जटिलता ओ (1) है। इसके अतिरिक्त, बीच में सम्मिलन या विलोपन की समय जटिलता, एक पुनरावर्तक दिया गया है, ओ (1) है; हालाँकि, इंडेक्स द्वारा रैंडम एक्सेस की समय जटिलता O(n) है।
• एक बढ़ते सरणी में, सभी डेक संचालन की परिशोधित समय जटिलता हे (1) है। इसके अतिरिक्त, इंडेक्स द्वारा रैंडम एक्सेस की समय जटिलता O(1) है; लेकिन बीच में प्रविष्टि या विलोपन की समय जटिलता (एन) है।

एप्लीकेशन

वेब ब्राउज़िंग इतिहास को संग्रहीत करने के लिए एक डबल-एंडेड क्यू का उपयोग किया जा सकता है: क्यू के अंत में नई वेबसाइटें जोड़ी जाती हैं, जबकि इतिहास बहुत बड़ा होने पर सबसे पुरानी प्रविष्टियां हटा दी जाएंगी। जब कोई उपयोगकर्ता पिछले एक घंटे के ब्राउज़िंग इतिहास को साफ़ करने के लिए कहता है, तो सबसे हाल ही में जोड़ी गई प्रविष्टियाँ हटा दी जाती हैं।

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

यह भी देखें

• पाइप (यूनिक्स)
• क्यू (डेटा संरचना)
• प्राथमिकता क्यू

बाहरी संबंध

• 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