แถวคอยสองหน้า
จากวิกิพีเดีย สารานุกรมเสรี
| แถวคอยสองหน้า | |
|---|---|
| ความสำคัญของลำดับ | FLO (First Last Out) |
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
| วิธีการเข้าถึง(access) | headenqueue/headdequeue,tailenqueue/taildequeue |
| เวลาที่ใช้ในการเข้าถึง | O(1) |
| โครงสร้างข้อมูลที่มีรูปแบบนี้ | |
แถวคอยสองหน้า (อังกฤษ: Double-Ended Queue: Deque) เป็นแบบชนิดข้อมูลนามธรรมที่เราสามารถนำข้อมูลแรกสุดหรือหลังสุดที่เราเพิ่มเข้าหรือออกก็ได้ เปรียบเสมือนเป็นแถวคอยที่มีหัวเปิดสองด้านให้เข้า-ออกได้ นั้นเอง
แถวคอยสองหน้า สามารถประยุกต์ใช้ในแนวคิด กึ่งแถวคอยกึ่งกองซ้อนได้ ทำให้จัดการกับการเข้าออกของข้อมูลได้ทุกรูปแบบ
เนื้อหา |
จุดเด่น [แก้]
แถวคอยสองหน้าสามารถรวมแนวคิดของแถวคอยและกองซ้อนได้ดังนี้
| บริการของแถวคอยสองหน้า | บริการของแถวคอย | บริการของกองซ้อน |
|---|---|---|
| headenqueue | enqueue | push |
| headdequeue | - | pop |
| taildequeue | dequeue | - |
| peek | peek | top |
บริการที่มักจะมี [แก้]
- เอาข้อมูลใหม่เข้าในหัวแถว (headenqueue)
- เอาข้อมูลออกจากหัวแถว (headdequeue)
- เอาข้อมูลใหม่เข้าในท้ายแถว (tailenqueue)
- เอาข้อมูลออกจากท้ายแถว (taildequeue)
- ดูข้อมูลที่อยู่หัวแถว (peek)
ความเร็วที่ใช้ในการทำงาน [แก้]
การทำงานยังคงเป็นการจัดการการข้อมูลเข้าออกเหมือนแถวคอยและกองซ้อน จึงใช้เวลาคงที่ (O(1))
วิธีการสร้าง [แก้]
แถวคอยสองหน้าดัดแปลงมาจากแถวคอยธรรมดา สำหรับแถวคอยแถวลำดับ เพียงแต่การจัดการดัชนีทั้งที่ชี้ตัวแรกและตัวสุดท้ายให้เพิ่มได้ทั้งสองฝั่ง ส่วนแถวคอยรายการโยงสองชั้นวนก็ทำได้โดยการอนุญาตให้เพิ่มทั้งก่อนและหลังปมหัว
ดูเพิ่ม [แก้]
|
||||||||||||||||||||
