ป้อนข้อมูล

ป้อนข้อมูล

เอาต์พุต

เอาต์พุต

ในฐานะคิว

เป็นกอง

คิวสองด้านเปรียบเสมือนท่อ

ในวิทยาการคอมพิวเตอร์คิวสองด้าน (ย่อว่าdeque — / d ɛ k / DEK ) เป็นชนิดข้อมูลนามธรรมที่ทำหน้าที่เป็นภาชนะบรรจุโดยมีการจำกัดการเข้าถึงรายการที่จัดเก็บไว้ โดยเป็นส่วนขยายของทั้งสแต็กและคิว deque อาจมีฟังก์ชันคล้ายกับบัฟเฟอร์ข้อมูล กล่าว คือ สามารถใช้ได้ทั้งเป็นตัวเก็บรักษา (คิว) หรือสำหรับการย้อนกลับ (สแต็ก) อย่างไรก็ตาม deque มีความยืดหยุ่นมากกว่าในการจัดการลำดับขององค์ประกอบ และอัลกอริทึมบางอย่างก็ใช้ฟังก์ชันการทำงานของมันเป็นพื้นฐาน

คิวแบบสองปลายมักถูกนำเสนอในฐานะคิวแบบทั่วไป ซึ่งเป็นที่มาของชื่อ คิวประเภทนี้คือคิวที่ "อนุญาตให้มีการแทรกและการลบที่ปลายทั้งสองข้าง" เดคิวยังถูกอธิบายว่าเป็น โครงสร้างข้อมูลนามธรรมแบบ สแต็กแบบทั่วไป โดยเป็น "สแต็กสองอันที่เชื่อมต่อกันที่ฐาน" โดยมีรายการด้านล่างร่วมกัน หรือเป็นการผสมผสานระหว่างสแต็กและคิว^{[ 1 ] [ a ] ​​[ b ]}และในทางกลับกัน คิวและสแต็กก็เป็นรูปแบบที่จำกัดของเดคิว

มีการใช้การเปรียบเทียบที่แตกต่างกันกับวัตถุในโลกแห่งความเป็นจริงเพื่ออธิบายเดก (deque) โดยเปรียบเทียบกับ "สำรับไพ่" ซึ่งโครงสร้างมีคุณสมบัติบางอย่างและการออกเสียงที่คล้ายคลึง กัน ^{[ 3 ] [ 4 ] : 239 [ 5 ]}เดกยังถูกเปรียบเทียบกับ "สร้อยคอที่มีลูกปัดที่สามารถเพิ่มและ/หรือถอดออกได้ที่ปลายทั้งสองข้าง" เช่นเดียวกับคิว (queue) เดกถูกแสดงเป็นชุดของสิ่งของที่เรียงกันอยู่ในท่อที่เปิดอยู่ทั้งสองด้าน แต่ต่างจากคิวตรงที่สิ่งของสามารถเคลื่อนที่ได้ทั้งสองทิศทางในท่อ "แบบจำลองทางรถไฟ" ที่นำเสนอโดย Knuth (หลังจาก"ลานสับเปลี่ยนของ Dijkstra" ) ^{[ 4 ] : 240} เน้นความคล้ายคลึงกับคิว โดยมีทางเข้าหนึ่งทางและทางออกหนึ่งทาง และสวิตช์เพื่อเลือกด้านของเดกที่จะเข้าถึง^{[ 6 ] : 175}

การดำเนินการหลักบนเดคิวกล่าวกันว่าเกิดขึ้นที่ด้านใดด้าน หนึ่ง (หรือปลาย ) ของโครงสร้าง ได้แก่ การเพิ่มรายการลงในคอลเลกชัน ( enqueue ) การลบรายการ(dequeue ) และการอ่านรายการ ( peek ) ณ จุดเวลาใดเวลาหนึ่ง จะสามารถเข้าถึงรายการได้เพียงสองรายการจากด้านใดด้านหนึ่งของเดคิว โดยอิงตามประวัติของโครงสร้าง รายการที่กำหนดไว้ในด้านหนึ่งจะเป็นรายการล่าสุดที่ถูกแทรกเข้ามาในด้านนั้น ( พฤติกรรม LIFO ) หรือ หากไม่มีรายการใดถูกแทรกเข้ามา ก็จะเป็นรายการที่เก่าที่สุดที่ถูกแทรกเข้ามาในอีกด้านหนึ่ง (พฤติกรรมFIFO ) นโยบายการให้บริการนี้ทำให้โครงสร้างมีความยืดหยุ่นและอเนกประสงค์มากขึ้น แต่ก็เข้าใจและใช้งานได้ยากขึ้นเช่นกัน^{[ c ]}

การดำเนินการหลักหกอย่างบนเดคิวสามารถอธิบายได้สองวิธี โดยอิงจากการดำเนินการคิว (หรือสแต็ก): โดยการทำซ้ำการดำเนินการเหล่านั้นที่ปลายแต่ละด้านของโครงสร้าง ( add_left, add_right, เป็นต้น) หรือโดยการทำให้เป็นแบบทั่วไปด้วยพารามิเตอร์ที่ระบุตำแหน่งที่ดำเนินการ ( add(left,...), add(right,...), เป็นต้น) แต่ละวิธีมีข้อดี: วิธีแรกอนุญาตให้โอเวอร์โหลดการดำเนินการได้ แต่จำเป็นต้องมีชื่อที่แตกต่างกันในแต่ละด้าน ในขณะที่วิธีที่สองทำให้ส่วนต่อประสานง่ายขึ้นโดยการลดจำนวนการดำเนินการลงครึ่งหนึ่งและอนุญาตให้ใช้ความสมมาตรของโครงสร้าง^{[ 7 ]}ต่อไปนี้ เราจะใช้ตัวเลือกที่สองเพื่อหลีกเลี่ยงการทำซ้ำที่ไม่จำเป็น

เดคิวมีประเภทย่อยที่เป็นไปได้อีกสองประเภท (รูปแบบที่จำกัดกว่านี้ไม่มีประโยชน์) :

• เดคิวแบบจำกัดการป้อนข้อมูลคือ เดคิวที่สามารถลบข้อมูลได้จากทั้งสองด้าน แต่สามารถแทรกข้อมูลได้จากด้านใดด้านหนึ่งเท่านั้น มันคือคิวที่มีเอาต์พุตด้านหลัง หรือสแต็กที่มีเอาต์พุตด้านล่าง
• เดคิวแบบจำกัดการส่งออกคือ เดคิวที่สามารถแทรกข้อมูลได้จากทั้งสองด้าน แต่สามารถลบข้อมูลได้จากด้านใดด้านหนึ่งเท่านั้น มันคือคิวที่มีอินพุตด้านหน้า หรือสแต็กที่มีอินพุตด้านล่าง

แม้จะมีข้อจำกัดอยู่บ้าง แต่ประเภทย่อยเหล่านี้ก็มีประโยชน์ในการใช้งาน หลายด้าน และบางวิธีการใช้งานอาจง่ายกว่าด้วยซ้ำ

หลังจาก Knuth ^{[ 4 ]}โครงสร้างเหล่านี้มักถูกอธิบายว่าเป็นรูปแบบต่างๆ ของรายการเชิงเส้น แบบจำกัด หรือลำดับโดยจะรักษาองค์ประกอบที่บรรจุไว้ตามลำดับที่กำหนด ในขณะที่อนุญาตให้เข้าถึงได้เพียงบางส่วนเท่านั้น คือ ตัวแรกและ/หรือตัวสุดท้ายในลำดับ อย่างไรก็ตาม ผู้เขียนคนอื่นๆ คัดค้านว่าโครงสร้างเหล่านี้ "ซ่อนพลวัตภายในจากผู้ใช้" ^{[ 2 ] : 139} และมีเพียงการใช้งาน ทั่วไปเท่านั้นที่เป็นเชิงเส้น พวกเขาพิจารณาว่า โครงสร้างข้อมูลที่มีการเข้าถึงแบบจำกัดเหล่านี้เป็นอย่างใดอย่างหนึ่งดังต่อไปนี้:

• กึ่งโครงสร้าง : พวกมันมี "รายการพิเศษหรือที่กำหนดไว้ แต่ไม่มีความสัมพันธ์เชิงตรรกะระหว่างรายการที่เหลือ" และ "การดำเนินการที่ลบรายการจะไม่รับรายการใดเป็นพารามิเตอร์" ^{[ 8 ] : xiii, 189}
• หรือโครงสร้างจุด "เพราะมีเพียงสองจุดของคิวเท่านั้นที่มีอยู่สำหรับโลกภายนอก" ^{[ 2 ] : 129} : สแต็กจึงเป็นโครงสร้างจุดเดียว ในขณะที่คิวและเดคิวเป็นโครงสร้างสองจุด

ตัวอย่างเช่น เดคิวสามารถนำไปใช้กับฮีปแบบ min-maxหรือกับเซ็ตได้ : ก่อนที่จะแทรกรายการ รายการนั้นจะถูกติดแท็กด้วยจำนวนเต็มที่ใช้เป็นค่าในฮีป ซึ่งขึ้นอยู่กับประวัติของคอนเทนเนอร์^{[ 8 ] : A1} องค์ประกอบที่จัดเก็บในฮีปไม่ได้เรียงลำดับ และตำแหน่งขององค์ประกอบเหล่านั้นขึ้นอยู่กับสถานะภายในของโครงสร้าง โครงสร้างการเข้าถึงแบบจำกัดทั่วไปอีกอย่างหนึ่งคือคิวลำดับความสำคัญซึ่งไม่ใช่โครงสร้างเชิงเส้น

เดคิวสามารถขยายความทั่วไปได้โดยการเพิ่มการดำเนินการบางอย่าง: เดคิวที่มีลำดับฮีป หรือmindequeช่วยให้สามารถ ดำเนินการ find-minได้ นอกจากนี้ยังสามารถสร้าง catenation ที่รวดเร็วหรือเหมาะสมที่สุดได้อีกด้วย^{[ 9 ] : 276 [ 10 ] [ 11 ]}

ผู้เขียนบางคนมองว่าโครงสร้างเดคิวมีประโยชน์น้อย มีประโยชน์น้อยกว่ารูปแบบที่จำกัด โดยเฉพาะสแต็กและคิว^{[ 1 ] [ 2 ] [ 9 ] [ d ]}

ในที่นี้ deque ถือว่าไม่มีขอบเขต: มันสามารถบรรจุรายการได้ไม่จำกัดจำนวน (และไม่มีการกำหนด) Deque ที่มีขอบเขตนั้นเป็นไปได้ และต้องใช้ข้อกำหนดที่แตกต่างออกไปเล็กน้อย แต่เมื่อเกิดการล้น พฤติกรรมจะขึ้นอยู่กับการใช้งาน: ค่าข้อผิดพลาด ข้อยกเว้น การลบ ฯลฯ

ให้d ∈ D เป็นเดคิว (deque) , x ∈ X เป็น ไอเทม และe ∈ E เป็นด้าน (ปลาย) = {ซ้าย, ขวา}โดยที่¬ ซ้าย = ขวา

     การดำเนินการหลัก:ด้วยD ^* = D \ {Λ}

เนื่องจากโครงสร้างเชิงเส้น เดคิวจึงสามารถระบุได้ในแง่ของการเชื่อมต่อ (ระบุด้วย " ~ ") ของลำดับและลำดับเดี่ยว (ระบุด้วย " < ... > ")

ข้อกำหนดเชิงสัจพจน์ (หรือเชิงพีชคณิต ) ของเดคิวสามารถได้รับโดยการขยายและรวมข้อกำหนดของสแต็กและคิว^{[ 13 ] [ 14 ] [ 15 ]} (ดูวิทยานิพนธ์ของ Nguyen สำหรับสูตรทางเลือกอื่น^{[ 16 ]} )

     ข้อจำกัดเชิงสัจพจน์:

ลำดับการดำเนินการในตัวอย่างก่อนหน้านี้ส่งผลให้ได้นิพจน์ดังต่อไปนี้:

d = ลบ (ขวา, เพิ่ม (ซ้าย, DE, ลบ (ซ้าย, ลบ (ซ้าย, เพิ่ม (ขวา, UE, เพิ่ม (ขวา, QUE, เพิ่ม (ซ้าย, STA, ลบ (ซ้าย, เพิ่ม (ขวา, CK, เพิ่ม (ซ้าย, DE,Λ) )))))))))

สิ่งนี้สามารถทำให้ง่ายขึ้นได้ด้วยสัจพจน์ ( 1 ), ( 2 ) และ ( 3 ) ตามลำดับการใช้งาน จากเดคิวว่าง:

ซึ่งจะได้ผลลัพธ์ดังต่อไปนี้:

d = add (ซ้าย, DE, add (ขวา, QUE,Λ))

เป็นการแปลงจากลำดับว่างเปล่า:

< >เพิ่ม (ขวา, QUE)⟼< QUE>เพิ่ม (ซ้าย, DE)⟼< DE, QUE>

ในทางกลับกัน สแต็กและคิวสามารถระบุได้โดยใช้สัจพจน์โดยอ้างอิงจากเดคิว

คำว่าdeque ( / d ɛ k / DEK ) ใช้เป็นคำย่อของDouble - Ended Queueบางครั้งมีการใช้ dequeue แต่ก็อาจทำให้สับสนได้ เนื่องจากคำนี้ยังใช้สำหรับการดำเนินการลบองค์ประกอบของ deque ด้วย deque อาจถูกเรียกว่า head-tail linked list ก็ได้แม้ว่าโดยหลักแล้วจะหมายถึงการใช้งานเฉพาะอย่างหนึ่ง deque ที่จำกัดการส่งออกอาจถูกกำหนดให้เป็นsteque (สำหรับ stack - ended queue) ^{[ 17 ] : 53}

ไม่มีคำศัพท์มาตรฐานที่เกี่ยวข้องกับเดคิว คำว่าenqueueและdequeueซึ่งยืมมาจากโครงสร้างคิว โดยทั่วไปแล้วจะหมายถึงการดำเนินการพื้นฐานบนเดคิวที่ปลายทั้งสองด้าน แต่ในเอกสารและในการใช้งานจริงมักใช้ชื่อที่แตกต่างกัน ชื่อของการดำเนินการจะแตกต่างกันไปขึ้นอยู่กับบริบท ผู้เขียน การใช้งาน หรือภาษาโปรแกรม:

• ในทำนองเดียวกับคิว: เพิ่มเข้าคิวและนำออกจากคิวหรือผลักและดึง ;
• เปรียบเสมือนกองซ้อน: สามารถผลักและดึงข้อมูลออกได้ทางด้านหนึ่ง และอาจมีการใส่และนำข้อมูลออกทางอีกด้านหนึ่ง
• เปรียบเสมือนรายการ: ข้อดีและข้อเสียอยู่ด้านหนึ่ง และสิ่งที่ชอบและไม่ชอบอยู่ด้านอีกด้านหนึ่ง
• ในทำนองเดียวกับอาร์เรย์: เพิ่มข้อมูลทางด้านหนึ่งเพิ่มข้อมูลด้านหน้าทางอีกด้านหนึ่ง หรือเลื่อนและยกเลิกการเลื่อนข้อมูล

แตกต่างจากโครงสร้างข้อมูลที่เกี่ยวข้อง เดคิวมีความสมมาตร ด้านต่างๆ ของเดคิวสามารถตั้งชื่อได้อย่างอิสระตามบริบท:

• เปรียบเสมือนแถวรอคิว: ด้านหน้าและด้านหลัง ;
• เปรียบเสมือนกองสิ่งของ: ด้านบนและด้านล่าง ;
• ในทำนองเดียวกับรายการ: หัวเรื่องหรือสุดท้าย ;
• ในทำนองเดียวกับอาร์เรย์: ตัวแรกและตัวสุดท้ายหรือตัวแรกและตัวสุดท้าย ;
• สุดท้ายแล้วด้านซ้ายและขวายังคงรักษาสมมาตรดั้งเดิมของโครงสร้างไว้

ชื่อเต็มของการดำเนินการอาจเป็นการรวมกันของชื่อของการดำเนินการพื้นฐานและชื่อของด้าน เช่นpush_frontและpop_backคำศัพท์จากแนวคิดที่แตกต่างกันอาจถูกนำมาใช้ร่วมกันในบริบทเดียว เช่นappendและpop , pushและshiftหรือfrontและtailสุดท้ายนี้ ภาษาโปรแกรมบางภาษายังใช้ชื่อที่แตกต่างกันไปตามโครงสร้างข้อมูลพื้นฐานอีกด้วย

โดยทั่วไปแล้วจะมีการใช้ งานโอเปอเรชัน "peek"ซึ่งจะส่งคืนค่าที่ปลายด้านหนึ่งโดยไม่ต้องดึงข้อมูลออกจากคิว มักตั้งชื่อตามด้านเป้าหมาย เช่นtopคือค่าขององค์ประกอบที่อยู่ด้านบนสุดของ deque ในบริบทของการเขียนโปรแกรมเชิงฟังก์ชัน โอเปอเร ชัน dequeue (ซึ่งส่งคืนสองค่า คือ องค์ประกอบที่ถูกลบออกและ deque ใหม่) จะไม่ถูกนำมาใช้ แต่จะถูกแทนที่ด้วยฟังก์ชัน peek (เช่นheadและlast ) และฟังก์ชันที่ส่งคืน deque ลบด้วยค่าที่ปลายสุด เช่นtailและinit

มีอย่างน้อยสองวิธีที่ใช้กันทั่วไปในการสร้าง deque อย่างมีประสิทธิภาพซึ่งมักถูกนำมาเปรียบเทียบกันคือ การใช้ลิสต์เชื่อมโยงสองทาง หรือการใช้ไดนามิกอาร์เรย์ที่ดัดแปลง นอกจากนี้ยังมีรูปแบบที่หลากหลาย และการใช้งานจริงมักเป็นการผสมผสานระหว่างสองวิธีนี้ ยิ่งไปกว่านั้นยังมีการใช้งานคิวสองปลาย แบบฟังก์ชันล้วนๆ อีกหลายรูปแบบด้วย

แม้ว่าลิสต์ธรรมดาอาจใช้สร้างเดคิวได้ แต่ลิสต์แบบเชื่อมโยงสองทิศทางนั้นเหมาะสมกว่าเนื่องจากสมมาตรของมัน ทำให้สามารถเข้าถึงปลายทั้งสองด้านของลิสต์ได้อย่างรวดเร็ว ( หัวและท้ายจึงเป็นที่มาของชื่อลิสต์แบบเชื่อมโยงหัว-ท้าย ) วิธีแก้ปัญหาที่ชัดเจนคือการจัดการการอ้างอิงสองรายการ หรืออีกทางเลือกหนึ่งคือสร้างเดคิวเป็นลิสต์แบบวงกลม

ในการใช้งานลิสต์แบบเชื่อมโยงสองทิศทาง และสมมติว่าไม่มีค่าใช้จ่ายเพิ่มเติมในการจัดสรร/ยกเลิกการจัดสรรความซับซ้อนของเวลาในการดำเนินการ deque ทั้งหมดคือO(1)นอกจากนี้ การแทรกหรือลบตรงกลาง เมื่อกำหนดตัววนซ้ำแล้ว สามารถทำได้ในเวลาคงที่ อย่างไรก็ตาม เวลาที่ใช้ในการเข้าถึงแบบสุ่มโดยใช้ดัชนีคือO(n)ในทำนองเดียวกัน การค้นหาองค์ประกอบเฉพาะมักต้องใช้เวลาO(n)โครงสร้างข้อมูลแบบเชื่อมโยงโดยทั่วไปมีความใกล้เคียงของการอ้างอิงที่ไม่ดี

ในกรณีนี้เช่นกัน แม้ว่าอาร์เรย์แบบไดนามิกจะสามารถใช้ในการสร้างเดคิวได้ แต่รูปแบบที่สามารถขยายได้จากทั้งสองด้านจะเหมาะสมกว่า ซึ่งบางครั้งเรียกว่าอาร์เรย์เดคิวสามารถทำได้หลายวิธี เช่น:

• โดยการเลื่อนตำแหน่งขององค์ประกอบแรกของอาร์เรย์ในหน่วยความจำที่สงวนไว้: พื้นที่ที่ไม่ได้ใช้จะถูกกระจายไปทั้งสองด้านของข้อมูล
• ด้วยการจัดเรียงแบบวงกลม

ความ ซับซ้อนของเวลา โดยเฉลี่ยของการดำเนินการ deque ทั้งหมดกับอาร์เรย์ dequeคือO(1)เนื่องจากการขยายตัวทางเรขาคณิตของบัฟเฟอร์แบ็กเอนด์ นอกจากนี้ การเข้าถึงแบบสุ่มโดยใช้ดัชนีใช้เวลาคงที่ แต่เวลาเฉลี่ยที่ใช้สำหรับการแทรกหรือลบตรงกลางคือO(n)ด้วยการเข้าถึงแบบสุ่มที่รวดเร็ว การค้นหาองค์ประกอบในอาร์เรย์ที่เรียงลำดับแล้วจึงใช้เวลาO(log n) ( การค้นหาแบบไบนารี ) ทุกครั้งที่มีการปรับขนาดอาร์เรย์ เนื้อหาทั้งหมดจะถูกย้าย การใช้งานหน่วยความจำจะเพิ่มขึ้นเป็นสองเท่า (หรือมากกว่า) ชั่วขณะ และการอ้างอิงโดยตรง (ภายนอก) ทั้งหมดไปยังเนื้อหาของอาร์เรย์จะหายไป

รายการเชื่อมโยงสองทางไม่สามารถใช้เป็นโครงสร้างข้อมูลที่ไม่เปลี่ยนแปลงได้และอาร์เรย์ที่ไม่เปลี่ยนแปลงได้จะไม่มีประสิทธิภาพอย่างมาก (อาร์เรย์มักถูกจำลองโดยต้นไม้ ) การใช้งาน deque ในรูปแบบฟังก์ชันล้วนๆ สามารถใช้ stack เป็นพื้นฐานได้ ซึ่งสามารถนำไปใช้งานได้ง่ายด้วยรายการเชื่อมโยงทางเดียว เป็น โครงสร้างที่ไม่เปลี่ยนแปลงและ คงอยู่ ถาวร

มีงานวิจัยหลายชิ้นในวรรณกรรมที่กล่าวถึงปัญหานี้ งานวิจัยเหล่านั้นทั้งหมดใช้แนวคิดหลักสองประการ ประการแรกคือ การแทนเดคิวด้วยสแต็กสองตัว ตัวหนึ่งแทนส่วนหน้าของเดคิว และอีกตัวแทนส่วนหลังที่กลับด้าน เมื่อด้านใดด้านหนึ่งว่างลงเนื่องจาก การดำเนินการ ป๊อปหรืออีเจ็กต์ มากเกินไป เดคิวซึ่งตอนนี้อยู่บนสแต็กเดียว จะถูกคัดลอกไปยังสแต็กสองตัว โดยแต่ละตัวมีองค์ประกอบของเดคิวครึ่งหนึ่ง การแบ่งครึ่งต่อครึ่งนี้รับประกันว่าการคัดลอกดังกล่าว แม้จะมีค่าใช้จ่ายสูง แต่ก็เกิดขึ้นไม่บ่อยนัก การคำนวณค่าเฉลี่ยอย่างง่ายแสดงให้เห็นว่าการจำลองเดคิวด้วยจำนวนสแต็กคงที่นั้นใช้เวลาเชิงเส้น: การดำเนินการเดคิว kครั้งเริ่มต้นจากเดคิวว่างจะถูกจำลองด้วยการดำเนินการสแต็ก O(k) ครั้ง [...] แนวคิดที่สองคือการใช้การคัดลอกแบบเพิ่มทีละน้อยเพื่อแปลงการจำลองเวลาเชิงเส้นนี้ให้เป็นการจำลองแบบเรียลไทม์: ทันทีที่สแต็กทั้งสองไม่สมดุลกันมากพอ การคัดลอกใหม่เพื่อสร้างสแต็กที่สมดุลสองสแต็กก็จะเริ่มต้นขึ้น

กระบวนการสุดท้ายนี้อาจค่อนข้างซับซ้อน เนื่องจากต้องดำเนินการพร้อมกันกับการดำเนินการอื่นๆ และต้องเสร็จสิ้นก่อนการดำเนินการถัดไป เพื่อให้ได้ความซับซ้อนแบบเรียลไทม์เฉลี่ย ขั้นตอนต่อไปคือการสนับสนุนการดำเนินการใน เวลา O(1) ในกรณี ที่เลวร้ายที่สุดความท้าทายอีกประการหนึ่งคือการเชื่อมต่อ deque แบบเรียลไทม์ Okasakiเสนอวิธีแก้ปัญหาง่ายๆ ที่ใช้รายการแบบ lazyร่วมกับการจดจำ (memoization ) การปรับสมดุลระหว่าง stack กับ stack จะเป็นไปโดยอัตโนมัติบางส่วนโดยการจัดตารางเวลาที่แม่นยำของฟังก์ชันแบบเพิ่มขึ้น^{[ 17 ] : 52−59 : 115} อย่างไรก็ตาม ผู้เขียนบางคนมองว่าอัลกอริทึมดังกล่าวไม่ใช่ฟังก์ชันบริสุทธิ์ เนื่องจากถือว่าการจดจำเป็น ผล ข้างเคียง^{[ 18 ] : 581} Kaplan และ Tarjan เสนอ deque เวอร์ชันฟังก์ชันบริสุทธิ์ (ไม่สามารถเชื่อมต่อได้) ของตนเอง โดยอิงจากแนวคิดสามประการ: ^{[ 18 ]}

• การสร้างโครงสร้างข้อมูลแบบบูตสแตรป ส่งผลให้เกิดโครงสร้างแบบเรียกซ้ำที่คาดการณ์ถึงโครงสร้างแบบต้นไม้ของนิ้วมือ : เดคิวเป็นสามส่วนที่ประกอบด้วยซับเดคิวที่ขนาบข้างด้วยบัฟเฟอร์สองตัวที่มีขนาดจำกัดการเพิ่มข้อมูล ลงในคิว และ การลบข้อมูลออกจาก คิวโดยพื้นฐานแล้วจะทำงานกับบัฟเฟอร์ (แบบเรียลไทม์เนื่องจากขนาดที่จำกัด) และก้าวไปข้างหน้าหนึ่งขั้นตอนในกระบวนการปรับสมดุล
• การชะลอตัวแบบเรียกซ้ำ ได้รับแรงบันดาลใจจากการแสดงเลขฐานสองที่ซ้ำซ้อน (RBR) โดยที่2ตัวเลขเพิ่มเติมแทนการทดเลขที่ถูกระงับ: เดคย่อยประกอบด้วยคู่ขององค์ประกอบจากเดคหลัก และการแพร่กระจายของกระบวนการปรับสมดุลไปยังเดคย่อยจะล่าช้าเช่นเดียวกับการแพร่กระจายการทดเลขหลังจากการเพิ่มหรือลดจำนวน RBR [ ^{17 ] : 105}
• และการดัดแปลงโครงสร้างหลักของโครงสร้างคล้ายต้นไม้ของนิ้ว (สแต็ก) ให้เป็นสแต็กของสแต็ก ซึ่งสามารถคิดได้ว่าเป็นสคิปลิสต์ 2 ระดับ สิ่งนี้ช่วยให้สามารถเข้าถึงซับเดคที่ไม่สมดุลได้แบบเรียลไทม์ ในทำนองเดียวกับ RBR ซับสแต็กจะแทนบล็อก1ตัวเลขที่ต่อเนื่องกัน ซึ่งสามารถข้ามไปเพื่อเข้าถึงตัวเลขถัดไปได้2เช่น ตัวทดที่แขวนอยู่

ในเอกสารนี้ Kaplan และ Tarjan ยังนำเสนอเวอร์ชันที่ซับซ้อนยิ่งขึ้นซึ่งทำให้เกิดการเชื่อมต่อแบบเรียลไทม์ อย่างไรก็ตาม คำอธิบายนี้ส่วนใหญ่เป็นข้อความ J. Viennot, A. Wendling, A. Guéneau และ F. Pottier ได้เผยแพร่การใช้งานโครงสร้างข้อมูลนี้ที่ได้รับการตรวจสอบแล้ว (ในOCamlและRocq ) พร้อมกับคำอธิบายอย่างเป็นทางการและการวิเคราะห์โดยละเอียดของอัลกอริทึม^{[ 19 ]}

โดยทั่วไปแล้ว การเชื่อมต่อแบบเรียลไทม์จำเป็นต้องใช้เดคิวที่เป็นทูเพิลซึ่งประกอบด้วยโครงสร้างย่อยสองส่วนเป็นหลัก ซึ่งแต่ละส่วนย่อยนั้นก็ประกอบด้วยเดคิวหรือสารประกอบของเดคิวอีกที จากนั้นแกนหลักเชิงเส้นของเดคิวที่ไม่สามารถเชื่อมต่อได้จะถูกแทนที่ด้วยโครง ร่างไบนารี

Kaplan, Okasaki และ Tarjan ได้สร้างเวอร์ชันที่เรียบง่ายกว่าและมีการถมเฉลี่ย ซึ่งสามารถนำไปใช้ได้โดยใช้การประเมินแบบขี้เกียจ หรือใช้การกลายพันธุ์อย่างมีประสิทธิภาพมากขึ้นในรูปแบบที่กว้างขึ้นแต่ยังคงมีข้อจำกัดอยู่^{[ 20 ]} Mihaescu และ Tarjan ได้สร้างการใช้งาน deque ที่สามารถเชื่อมต่อกันได้แบบบริสุทธิ์อย่างเคร่งครัดที่เรียบง่ายกว่า (แต่ยังคงซับซ้อนมาก) และยังมีการใช้งาน deque ที่ไม่สามารถเชื่อมต่อกันได้แบบบริสุทธิ์อย่างเคร่งครัดที่เรียบง่ายกว่ามาก ซึ่งทั้งสองแบบมีขอบเขตกรณีที่เลวร้ายที่สุดที่เหมาะสมที่สุด (ไม่ได้เผยแพร่อย่างเป็นทางการ) ^{[ 21 ]}

คอนเทนเนอร์ของAdaAda.Containers.Vectors มีแพ็กเกจทั่วไป `containers` และAda.Containers.Doubly_Linked_Lists`containers` สำหรับการใช้งานอาร์เรย์แบบไดนามิกและรายการเชื่อมโยงตามลำดับ

ไลบรารีเทมเพลตมาตรฐานของ C++ มีคลาสเทมเพลต `<class template> std::deque` และstd::list`<class template>` สำหรับการใช้งานอาร์เรย์หลายตัวและรายการเชื่อมโยงตามลำดับ

ตั้งแต่ Java 6 เป็นต้นมา Collections Framework ของ Java ได้เพิ่มDequeอินเทอร์เฟซใหม่ที่ให้ฟังก์ชันการแทรกและการลบที่ปลายทั้งสองด้าน โดยมีการใช้งานผ่านคลาสต่างๆ เช่นArrayDeque(ซึ่งเป็นสิ่งใหม่ใน Java 6 เช่นกัน) และLinkedListซึ่งให้การใช้งานอาร์เรย์แบบไดนามิกและรายการเชื่อมโยงตามลำดับ อย่างไรก็ตาม นั้นArrayDequeแม้ชื่อจะบอกว่าเป็นการเข้าถึงแบบสุ่ม แต่กลับไม่รองรับการเข้าถึงแบบสุ่ม

ต้นแบบอาร์เรย์ของ JavaScript และอาร์เรย์ของPerl มีการรองรับการลบ ( shiftและpop ) และการเพิ่ม ( unshiftและpush ) องค์ประกอบที่ปลายทั้งสองข้าง อย่างเป็นธรรมชาติ

Python 2.4 ได้แนะนำcollectionsโมดูลที่รองรับอ็อบเจ็กต์ dequeซึ่งใช้งานโดยใช้ลิสต์แบบเชื่อมโยงสองทางของซับอาร์เรย์ที่มีความยาวคงที่

ตั้งแต่ PHP เวอร์ชัน 5.3 เป็นต้นไป ส่วนขยาย SPL ของ PHP มีคลาส 'SplDoublyLinkedList' ที่สามารถใช้สร้างโครงสร้างข้อมูล Deque ได้ ก่อนหน้านี้ การสร้างโครงสร้าง Deque ต้องใช้ฟังก์ชันอาร์เรย์ array_shift/unshift/pop/push แทน

โมดูล Data.SequenceของGHCนำเสนอโครงสร้าง deque ที่มีประสิทธิภาพและใช้งานได้จริงในภาษา Haskellการใช้งานนั้นใช้โครงสร้างแบบ finger tree 2-3 ตัวที่ระบุขนาดไว้

Rust std::collectionsมีVecDequeซึ่งเป็นไลบรารีที่ใช้คิวแบบสองปลายโดยใช้บัฟเฟอร์วงแหวนที่ขยายได้

R DELQUE.(J) - ลบผู้ใช้ J ออกจากคิว R ENDQUE.(J) - วางผู้ใช้ J ไว้ที่ท้ายคิวระดับ(J) R BEGQUE.(J) - วางผู้ใช้ J ไว้ที่จุดเริ่มต้นของระดับคิว(J) 

คิวแบบสองปลายสามารถใช้แทนคิวหรือโครงสร้างสแต็กได้เสมอ ดังนั้นการใช้งานจริงของเดคิวจึงมักเป็นเวอร์ชันที่ขยายเพิ่มเติมของอัลกอริทึมแบบสแต็กหรือคิว ที่จริงแล้ว แอปพลิเคชันจำนวนมากต้องการเพียงเดคิวที่มีข้อจำกัดด้านเอาต์พุตหรือ (ในบางกรณี) อินพุตเท่านั้น เฉพาะแอปพลิเคชันในโลกแห่งความเป็นจริงที่เหมาะสมที่สุดโดยใช้เดคิวแบบเข้มงวด กล่าวคือ แอปพลิเคชันที่ต้องการเข้าถึงเฉพาะองค์ประกอบที่ปลายทั้งสองข้างและทีละรายการเท่านั้น จะถูกนำมาแสดงไว้ในที่นี้

สามารถใช้เดคิวแบบจำกัดอินพุตเพื่อสร้างคิวแบบโมโนโทนิก ได้ กล่าวคือลำดับย่อยที่มีองค์ประกอบอยู่ในลำดับที่กำหนด ไม่ว่าจะเป็นลำดับเพิ่มขึ้นหรือลดลง เมื่อกำหนดลำดับมาให้ อัลกอริทึมจะเก็บเฉพาะองค์ประกอบที่อยู่ในลำดับที่ต้องการและทิ้งองค์ประกอบอื่นๆ ลำดับขององค์ประกอบจะถูกรักษาไว้ ในการสร้างลำดับโมโนโทนิกที่เพิ่มขึ้น (หรือลดลง) จะใช้เฉพาะการดำเนินการบนสแต็กเท่านั้น

• เริ่มต้นด้วยเดคิวที่ว่างเปล่า
• สำหรับแต่ละองค์ประกอบในลำดับอินพุต:
  • ในขณะที่องค์ประกอบสุดท้ายของเดคิวมีค่ามากกว่า (หรือน้อยกว่า) องค์ประกอบปัจจุบัน ให้ดึงองค์ประกอบนั้นออกมา
  • ผลักองค์ประกอบปัจจุบันเข้าไปในคิว

std :: deque <int> increasing_monotonic_queue ( std :: vector <int> & seq [ ] ) { std :: deque <int> q ; for ( std :: size_t i = 0 ; i < seq.size ( ) ; i ++ ) { while ( ! q.empty ( ) && q.back ( ) > seq [ i ] ) q.pop_back ( ) ; q.push_back ( seq [ i ] ) ; } return q ; }​​​​​

จากนั้นจึงสามารถดึงองค์ประกอบของลำดับโมโนโทนิกออกจากอีกด้านหนึ่งได้ (จึงเป็นที่มาของการใช้ deque)

สามารถใช้คิวโมโนโทนิกเพื่อค้นหาค่าต่ำสุดหรือสูงสุดในหน้าต่างเลื่อนเหนือลำดับด้วยความซับซ้อนของเวลาเชิงเส้น^{[ 23 ]}ความซับซ้อนของวิธีแก้ปัญหาแบบง่ายๆ คือ เวลา O(nk)และพื้นที่O(1) โดยที่ nคือความยาวของลำดับอินพุตและkคือขนาดของหน้าต่าง วิธีแก้ปัญหาที่ใช้วิธีการค้นหาบางประเภทคือเวลาO(n.log n) และ พื้นที่ O(n)

ในโค้ดต่อไปนี้ คิวแบบโมโนโทนิกจะเก็บการอ้างอิงถึงองค์ประกอบของลำดับ

#include <vector> #include <deque>typedef std :: vector <int> :: const_iterator seq_iterator ; typedef std :: deque <seq_iterator> monotonic_queue ;​​​monotonic_queue & decreasing_monotonic_queue_push ( monotonic_queue & q , seq_iterator i ) { while ( ! q . empty () && * q . back () < * i ) q . pop_back (); q . push_back ( i ); return q ; }std :: vector <int> max_of_subarrays ( std :: vector <int> & seq , std :: size_t win_sz ) { std :: vector <int> max_of_sub ; monotonic_queue decreasing ; seq_iterator i = seq.begin ( ) ; // สแกนหน้าต่างแรกfor ( size_t win_i = 0 ; i < seq.end ( ) && win_i < win_sz ; i ++ , win_i ++ ) decreasing_monotonic_queue_push ( decreasing , i ) ; max_of_sub.push_back ( * decreasing.front ( ) ) ; // สแกนส่วน ที่เหลือของลำดับfor ( / * keep i * / ; i < seq.end ( ) ; i ++ ) { if ( decreasing.front ( ) < = i - win_sz ) decreasing.pop_front ( ) ; // หลุดออกจากขอบเขตdecreasing_monotonic_queue_push ( decreasing , i ); max_of_sub . push_back ( * decreasing . front () ); } return max_of_sub ; }

แต่ละองค์ประกอบของลำดับอินพุตจะถูกผลักและดึงออกอย่างมากที่สุดหนึ่งครั้ง ส่งผลให้มี การดำเนินการ 2.n ครั้งดังนั้นความซับซ้อนของเวลาจึงเป็นO(n)ความซับซ้อนของพื้นที่คือO(k)ซึ่งเป็นขนาดสูงสุดของเดคิว

ในทำนองเดียวกัน คิวแบบโมโนโทนิกช่วยให้สามารถปรับ กรณี การเขียนโปรแกรมแบบไดนามิก บาง กรณีที่เทียบเท่ากับปัญหาลำดับย่อยที่มีน้ำหนักน้อยที่สุด  เช่นปัญหาเส้นทางที่สั้นที่สุดสำหรับกราฟทิศทางที่มีน้ำหนักการแบ่งย่อหน้าเป็นต้น ปัญหาเหล่านี้เรียกว่าปัญหาแบบนูนหรือเว้าและเป็นแบบโมโนโทนิกความซับซ้อนของเวลาจะลดลงจากO(n² ⁾เป็น O (n.log n)และO(n)ในสถานการณ์ที่เหมาะสม ^{[ 24 ] [ 25 ]}

การประยุกต์ใช้คิวโมโนโทนิกโดยตรงอีกอย่างหนึ่งคือคิวขั้นต่ำหรือminqueueในกรณีนี้จำนวนรายการในหน้าต่างจะแตกต่างกันไป minqueue เป็นโครงสร้างข้อมูลที่มี อินเทอร์เฟ ซคิวซึ่งให้การเข้าถึงรายการที่จัดเก็บขั้นต่ำโดยตรง การดำเนินการหลักคือenqueue , dequeueและfind minแม้ว่าชื่อจะสื่อถึงฮีป (min/max-)แต่ min/max-queue ไม่ใช่คิวลำดับความสำคัญ : ลำดับของรายการจะถูกรักษาไว้ตั้งแต่เข้าจนถึงออก (นโยบาย FIFO) เวอร์ชันง่ายๆ ของ min-queue ที่มี เวลาเฉลี่ย O(1)คือคิวปกติที่รวมกับคิวโมโนโทนิกเสริมที่เพิ่มขึ้น ซึ่งให้รายการที่น้อยที่สุดที่ด้านหน้า การเพิ่มรายการจะใช้กับทั้งสองคิว และเมื่อรายการที่น้อยที่สุดถูกดึงออกจากคิวปกติ (เช่น รายการด้านหน้าเดียวกัน) ก็จะถูกดึงออกจากคิวโมโนโทนิกด้วย^{[ 9 ]}

อัลกอริทึมของ Melkman คำนวณส่วนนูนของโซ่รูปหลายเหลี่ยมแบบง่าย (หรือรูปหลายเหลี่ยมแบบง่าย ) ในเวลาเชิงเส้น ความแตกต่างหลักกับอัลกอริทึมที่คล้ายกันอื่นๆ คือ Melkman ต้องการให้มีการเพิ่มหรือลบจุดยอดที่ปลายทั้งสองข้างของโซ่ส่วนนูนที่กำลังก่อตัว ดังนั้นจึงมีการใช้ deque อัลกอริทึมจะคำนวณตำแหน่งของจุดยอดใหม่แต่ละจุดเทียบกับส่วนแรกและส่วนสุดท้าย (ส่วนละสองจุดยอด) ของโซ่ส่วนนูน (เก็บไว้ใน deque) จุดยอดนั้นจะถูกละเลยหรือเพิ่ม (enqueued) เข้าไปที่ทั้งสองด้านของ deque (ส่วนนูนเป็นวงวน) หลังจากลบ (dequeueing) จุดยอดก่อนหน้าบางจุดที่อยู่ด้านในของส่วนนูนแล้ว^{[ 26 ] [ 27 ] [ 28 ]}

จากคอลเลกชันนำเข้าเดคิวdef position ( A , B , C ): det = ( B . X - A . X ) * ( C . Y - A . Y ) - ( B . Y - A . Y ) * ( C . X - A . X ) if det > 0 : return 1 # C อยู่ทางซ้ายของเส้น AB elif det < 0 : return 0 # C อยู่ทางขวาของเส้น AB else : return - 1 # AB และ C อยู่บนเส้นเดียวกันdef melkman ( path ): if position ( path [ 0 ], path [ 1 ], path [ 2 ]) == 1 : hull = deque ([ path [ 2 ], path [ 0 ], path [ 1 ], path [ 2 ]]) else : hull = deque ([ path [ 2 ], path [ 1 ], path [ 0 ], path [ 2 ]]) for v in path [ 3 :] : if position ( hull [ 0 ], hull [ 1 ], v ) == 1 and position ( hull [ - 2 ], hull [ - 1 ], v ) == 1 : continue while position ( hull [ 0 ], hull [ 1 ], v ) <= 0 : hull . popleft () hull . appendleft ( 0 , v ) ในขณะที่position ( hull [ -2 ] , hull [ -1 ] , v ) < = 0 : hull.pop ( ) hull.append ( v ) ส่งคืนhull

สแต็กและคิวสามารถมองได้ว่าเป็น คิวลำดับความสำคัญประเภทหนึ่งโดยลำดับความสำคัญจะถูกกำหนดโดยลำดับการแทรกองค์ประกอบ ในทำนองเดียวกัน เดคิวสามารถใช้คิวลำดับความสำคัญที่มีลำดับความสำคัญสองระดับได้ โดยองค์ประกอบที่มีลำดับความสำคัญสูงจะถูกเพิ่มเข้าไปที่ด้านหน้าของเดคิว ในขณะที่องค์ประกอบที่มีลำดับความสำคัญต่ำจะถูกเพิ่มเข้าไปที่ด้านหลัง^{[ 1 ]}เว้นแต่ว่าองค์ประกอบจะถูกยกเลิกหรือถูกขโมยแล้วถูกขับออกจากด้านล่าง เดคิวที่มีการจำกัดการส่งออกก็เพียงพอแล้ว

ดังนั้นจึงเป็นไปได้ที่จะปรับเปลี่ยนอัลกอริธึมของ Dijkstra มาตรฐาน เพื่อค้นหาเส้นทางที่สั้นที่สุดจากแหล่งกำเนิดเดียวในกราฟที่มีขอบต้นทุน 0 และ 1 โดยใช้ deque แทนคิวลำดับความสำคัญต่ำสุดองค์ประกอบต้นทุน 0 จะถูกเพิ่มเข้าไปในคิวด้านหน้าของ deque (ลำดับความสำคัญสูง) และจะถูกประมวลผลก่อนองค์ประกอบต้นทุนที่สูงกว่า (ลำดับความสำคัญต่ำ) ซึ่งถูกเพิ่มเข้าไปในคิวด้านหลังเสมอ

มีการใช้ deque ในอัลกอริทึมการขโมยงาน^{[ 29 ]}อัลกอริทึมนี้ใช้การจัดตารางงานสำหรับโปรเซสเซอร์หลายตัว โดยแต่ละโปรเซสเซอร์จะรักษา deque แยกต่างหากที่มีเธรดที่จะดำเนินการไว้ เพื่อดำเนินการเธรดถัดไป โปรเซสเซอร์จะดึงองค์ประกอบแรกจาก deque (โดยใช้การดำเนินการ deque "ลบองค์ประกอบแรก") หากเธรดปัจจุบันแยกออกเป็นหลายเธรด มันจะถูกใส่กลับไปที่ด้านหน้าของ deque ("แทรกองค์ประกอบที่ด้านหน้า") และเธรดใหม่จะถูกดำเนินการ เมื่อโปรเซสเซอร์ตัวใดตัวหนึ่งเสร็จสิ้นการดำเนินการเธรดของตนเอง (เช่น deque ของมันว่างเปล่า) มันสามารถ "ขโมย" เธรดจากโปรเซสเซอร์อื่นได้ โดยจะดึงองค์ประกอบสุดท้ายจาก deque ของโปรเซสเซอร์อื่น ("ลบองค์ประกอบสุดท้าย") และดำเนินการ อัลกอริทึมการขโมยงานนี้ถูกใช้โดยไลบรารี Threading Building Blocks (TBB) ของ Intel สำหรับการเขียนโปรแกรมแบบขนาน

ออโตมาตอนเดค ( DA) เป็นเครื่องสถานะจำกัดที่มีหน่วยความจำเสริมเดค มันเป็นการขยายแนวคิดของออโตมาตอนพุชดาวน์ (PDA) (ออโตมาตอนสแต็ก) และออโตมาตอนคิว (ออโตมาตอนพูลอัพ, PUA) ดังนั้นจึงเทียบเท่ากับเครื่องทัวริง และด้วยเหตุนี้จึงสามารถประมวลผล ภาษาเชิงรูปธรรมประเภทเดียวกันได้แต่ต่างจาก PDA และ PUA ที่กำหนดให้มีการเรียงลำดับ ออโตมาตอนเดคอนุญาตให้ดำเนินการแบบขนานหรือสลับกันได้^{[ 30 ]}

• ท่อ
• คิวลำดับความสำคัญ

• การใช้งาน deque แบบโอเพนซอร์สที่ปลอดภัยต่อประเภทข้อมูล ณ เครือข่ายเก็บถาวร C ที่ครอบคลุม
• เอกสาร SGI STL: deque<T, Alloc>
• Code Project: การศึกษาเชิงลึกเกี่ยวกับคอนเทนเนอร์ Deque ของ STL
• การใช้งาน Deque ในภาษา C เก็บถาวรเมื่อ 2014-03-06 ที่Wayback Machine
• การใช้งาน Stack, Queue, Deque และ Red-Black Tree ด้วย VBScript
• การใช้งาน deque ที่ไม่สามารถ catenable ได้หลายรูปแบบใน Haskell