แถวคอยสองหน้า
แถวคอยสองหน้า (อังกฤษ: 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))
วิธีการสร้าง
แก้แถวคอยสองหน้าดัดแปลงมาจากแถวคอยธรรมดา สำหรับแถวคอยแถวลำดับ เพียงแต่การจัดการดัชนีทั้งที่ชี้ตัวแรกและตัวสุดท้ายให้เพิ่มได้ทั้งสองฝั่ง ส่วนแถวคอยรายการโยงสองชั้นวนก็ทำได้โดยการอนุญาตให้เพิ่มทั้งก่อนและหลังปมหัว