แถวคอย

จากวิกิพีเดีย สารานุกรมเสรี


แถวคอย
Data Queue.svg
ลักษณะการเข้าก่อนออกก่อนของแถวคอย
ความสำคัญของลำดับ FIFO (First In First Out)
การซ้ำกันของสมาชิก อนุญาตให้ซ้ำกันได้
วิธีการเข้าถึง(access) ENQUEUE/DEQUEUE
เวลาที่ใช้ในการเข้าถึง O (1)
โครงสร้างข้อมูลที่มีรูปแบบนี้ แถวคอยสองหน้า, แถวคอยลำดับความสำคัญ

แถวคอย หรือ คิว (อังกฤษ: queue) เป็นแบบชนิดข้อมูลนามธรรมที่มีลักษณะการเรียงลำดับข้อมูล การดำเนินการในแถวคอยจะแบ่งเป็น การเพิ่มข้อมูลไปที่ส่วนหลังสุดของแถวคอย และการดึงข้อมูลออกจากส่วนหน้าสุดของแถวคอย เข้าออกในลักษณะการเข้าก่อนออกก่อน (First In First Out: FIFO) ในโครงสร้างข้อมูลลักษณะเข้าก่อนออกก่อนนี้ ข้อมูลแรกสุดที่ถูกเพิ่มเข้าไปในแถวคอยจะเป็นข้อมูลแรกที่ถูกดึงออก ซึ่งก็เท่ากับว่า ความจำเป็นที่ว่า เมื่อมีข้อมูลหนึ่งถูกเพิ่มเข้ามาแล้ว ข้อมูลที่ถูกเพิ่มก่อนหน้านี้ทั้งหมดจะต้องถูกดึงออกก่อนที่ข้อมูลใหม่จะถูกใช้งาน คล้ายกับการเข้าแถวซื้อของในชีวิตประจำวัน

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

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

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

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

  • เอาข้อมูลใหม่เข้าท้ายแถว (enqueue)
  • เอาข้อมูลออกจากหัวแถว (dequeue)
  • ดูข้อมูลที่อยู่หัวแถว (peek)
  • ทำแถวคอยว่าง และตรวจสอบความว่างของแถว (empty)

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

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

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

แถวคอยสามารถสร้างขึ้นด้วยแถวลำดับประกอบกับจำนวนเต็ม ที่เก็บดัชนีของหัวแถวและท้ายแถวสองตัว หรือใช้ รายการโยงสองชั้นวน(circular doubly linked list)

แถวคอยแถวลำดับ[แก้]

สำหรับการใช้แถวลำดับในการทำแถวคอยนั้น (array queue) ตอนเริ่มต้นเราจะให้ดัชนีของหัวแถวและท้ายแถวชี้ที่ศูนย์ เมื่อเข้าแถว (enqueue) ก็จะเก็บข้อมูลตรงดัชนีท้าย พร้อมทั้งเพิ่มค่าดัชนีท้ายแถวขึ้นหนึ่ง (increment) ในทางตรงกันข้ามหากเอาข้อมูลตัวแรกออกจากแถว (dequeue) ก็คืนค่าสมาชิกตัวที่ดัชนีหัวแถวชี้อยู่พร้อมทั้งเพิ่มค่าดัชนีหัวแถวไปอีกหนึ่ง (decrement) หากดัชนีหัวแถวไล่ทับดัชนีท้ายแถวแสดงว่า แถวคอยนั้นว่าง (empty queue) ไม่ควรออกจากแถวอีกเพราะจะทำให้การทำงานรวนได้ (ควรตรวจสอบก่อนออกจากแถว)

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

แถวคอยรายการโยงสองชั้นวน[แก้]

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

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