แถวคอย

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

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

แถวคอยด้วยกอง แก้

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