แถวคอย

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

 แถวคอยด้วยกอง 
สำหรับการสร้างแถวคอยด้วยกอง (Implement Queue using Stacks) เป็นการสร้างแถวคอย โดยการต้องสร้างกองขึ้นมาก่อนสองกอง จากนั้นค่อยพุช (push) และป้อบ (pop) ข้อมูลออก ก็จะได้ลำดับข้อมูลที่เหมือนกับแถวคอยเดิม

 ดูเพิ่ม 

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

หมวดหมู่:แบบชนิดข้อมูลนามธรรม