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

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

डबल-एंडेड प्राथमिकता क्यू के साथ भ्रमित नहीं होना चाहिए।

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

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

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

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

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

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

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

संचालन

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

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

संचालन	सामान्य नाम	एडीए	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 कि डेक अगर rebalance 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 डेक ऑब्जेक्ट्स के समर्थन के साथ मॉड्यूल। इसे निश्चित-लंबाई वाली उप-सरणियों की दोगुनी लिंक्ड सूची का उपयोग करके कार्यान्वित किया जाता है।

PHP 5.3 के अनुसार, PHP के SPL एक्सटेंशन में 'SplDoublyLinkedList' क्लास सम्मिलित है जिसका उपयोग Deque डेटास्ट्रक्चर को प्रयुक्त करने के लिए किया जा सकता है। पहले डेक संरचना बनाने के लिए सरणी फ़ंक्शन array_shift/unshift/pop/push का उपयोग इसके अतिरिक्त किया जाना था।

ग्लासगो हास्केल कंपाइलर Data.Sequence मॉड्यूल हास्केल (प्रोग्रामिंग भाषा) में एक कुशल, कार्यात्मक डेक संरचना प्रयुक्त करता है। कार्यान्वयन 2–3 ट्री | 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