แถวคอยสองหน้า

แถวคอยสองหน้า (อังกฤษ: Double-Ended Queue: Deque) เป็นแบบชนิดข้อมูลนามธรรมที่เราสามารถนำข้อมูลแรกสุดหรือหลังสุดที่เราเพิ่มเข้าหรือออกก็ได้ เปรียบเสมือนเป็นแถวคอยที่มีหัวเปิดสองด้านให้เข้า-ออกได้ นั้นเอง

แถวคอยสองหน้า
ความสำคัญของลำดับ	FLO (First Last Out)
การซ้ำกันของสมาชิก	อนุญาตให้ซ้ำกันได้
เวลาที่ใช้ในการเข้าถึง	headenqueue/headdequeue,tailenqueue/taildequeue

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

จุดเด่น

แถวคอยสองหน้าสามารถรวมแนวคิดของแถวคอยและกองซ้อนได้ดังนี้

บริการของแถวคอยสองหน้า	บริการของแถวคอย	บริการของกองซ้อน
headenqueue	enqueue	push
headdequeue	-	pop
taildequeue	dequeue	-
peek	peek	top

บริการที่มักจะมี

• เอาข้อมูลใหม่เข้าในหัวแถว (headenqueue)
• เอาข้อมูลออกจากหัวแถว (headdequeue)
• เอาข้อมูลใหม่เข้าในท้ายแถว (tailenqueue)
• เอาข้อมูลออกจากท้ายแถว (taildequeue)
• ดูข้อมูลที่อยู่หัวแถว (peek)

ความเร็วที่ใช้ในการทำงาน

การทำงานยังคงเป็นการจัดการการข้อมูลเข้าออกเหมือนแถวคอยและกองซ้อน จึงใช้เวลาคงที่ (O(1))

วิธีการสร้าง

แถวคอยสองหน้าดัดแปลงมาจากแถวคอยธรรมดา สำหรับแถวคอยแถวลำดับ เพียงแต่การจัดการดัชนีทั้งที่ชี้ตัวแรกและตัวสุดท้ายให้เพิ่มได้ทั้งสองฝั่ง ส่วนแถวคอยรายการโยงสองชั้นวนก็ทำได้โดยการอนุญาตให้เพิ่มทั้งก่อนและหลังปมหัว

ดูเพิ่ม

• แถวคอย
• กองซ้อน
• แถวคอยลำดับความสำคัญ