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

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

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

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

จุดเด่น[แก้]

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

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

บริการที่มักจะมี[แก้]

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

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

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

วิธีการสร้าง[แก้]

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

ดูเพิ่ม[แก้]