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

"Deque" redirects here. Not to be confused with dequeueing, a queue operation.

Not to be confused with Double-ended priority queue.

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

नामकरण परंपराएं

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

भेद और उप-प्रकार

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

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

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

संचालन

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

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

operation	common name(s)	Ada	C++	Java	Perl	PHP	Python	Ruby	Rust	JavaScript
insert element at back	inject, snoc, push	Append	push_back	offerLast	push	array_push	append	push	push_back	push
insert element at front	push, cons	Prepend	push_front	offerFirst	unshift	array_unshift	appendleft	unshift	push_front	unshift
remove last element	eject	Delete_Last	pop_back	pollLast	pop	array_pop	pop	pop	pop_back	pop
remove first element	pop	Delete_First	pop_front	pollFirst	shift	array_shift	popleft	shift	pop_front	shift
examine last element	peek	Last_Element	back	peekLast	$array[-1]	end	<obj>[-1]	last	back	<obj>.at(-1)
examine first element		First_Element	front	peekFirst	$array[0]	reset	<obj>[0]	first	front	<obj>[0]

कार्यान्वयन

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

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

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

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

डबल-एंडेड कतारों को विशुद्ध रूप से कार्यात्मक डेटा संरचना के रूप में भी लागू किया जा सकता है। कार्यान्वयन के दो संस्करण मौजूद हैं। पहला, जिसे रीयल-टाइम डेक कहा जाता है, नीचे प्रस्तुत किया गया है। यह कतार में संचालन के साथ लगातार डेटा संरचना होने की अनुमति देता है O(1) सबसे खराब समय, लेकिन memoization के साथ आलसी मूल्यांकन सूचियों की आवश्यकता होती है। दूसरा, जिसमें कोई आलसी सूची नहीं है और न ही संस्मरण खंडों के अंत में प्रस्तुत किया गया है। इसका परिशोधित विश्लेषण समय है 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 कि deque अगर 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::deque और 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 deque implementation at Comprehensive C Archive Network
• SGI STL Documentation: deque<T, Alloc>
• Code Project: An In-Depth Study of the STL Deque Container
• Deque implementation in C
• VBScript implementation of stack, queue, deque, and Red-Black Tree
• Multiple implementations of non-catenable deques in Haskell