เรื่อง คิว(Queue)
คิว(Queue) เป็นโครงสร้างข้อมูลเชิงเส้นที่นิยามการเพิ่มหรือการลบข้อมูลว่าจะทำที่ปลายลิสต์คนละด้าน ปลายลิสต์ด้านที่เป็นทางเข้าจะเรียกว่าส่วนท้ายหรือเรียร์(rear) ปลายลิสต์ด้านที่เป็นทางออกจะเรียกว่าส่วนหน้าหรือฟรอนต์(front) ข้อมูลที่เข้ามาในคิวก่อนจะออกจากคิวก่อนตามลำดับการเข้ามา จึงเรียกคุณลักษณะแบบนี้ว่า "เข้าก่อนออกก่อน" หรือ First In First Out (FIFO)
การจัดการคิวด้วยแถวลำดับ
การดำเนินการขั้นพื้นฐานกับคิวโดยทั่วไป ได้แก่ การสร้าง การเพิ่ม และการลบข้อมูล รายละเอียดของการดำเนินการแต่ละแบบ มีดังนี้
- การสร้างคิวด้วยแถวลำดับ
- การเพิ่มข้อมูลให้กับคิว
- การนำเข้าข้อมูลจากคิว
ข้อจำกัดของคิว
โครงสร้างคิวยังไม่มีประสิทธิภาพเท่าที่ควร เนื่องจากเมื่อมีการเพิ่มข้อมูลจนเต็มและมีการลบข้อมูลบางจำนวนออกจากโครงสร้างคิวแล้ว ตัวแปร rear ยังมีค่าเท่าเดิม ไม่สามารถเปลี่ยนไปยังต้นแถวลำดับได้จนกว่าจะมีการลบข้อมูลทุกจำนวนออกจากคิว ทำให้เสียพื้นที่ส่วนต้นของโครงส้รางคิวในตำแหน่งที่ตัวแปร front ผ่านมาแล้ว จากสาเหตุนี้ทำให้มีการพัฒนาโครงสร้างคิวใหม่ ให้รับข้อมูลเพิ่มในพื้นที่ส่วนต้นแถวลำดับที่ว่าง ด้วยการนำส่วนปลายของโครงสร้างคิว ทั้ง 2 ด้านมาบรรจบกันในลักษณะวงกลม เรียกว่า คิววงกลม(Circular Queue)
คิววงกลม คือ คิวที่เมื่อเก็บข้อมูลถึงปลายลิสต์แล้วยอมให้เก็บข้อมูลใหม่เพิ่มที่ส่วนต้นลิสต์ได้ถ้าพื้นที่ส่วนต้นของลิสต์ว่าง
รายละเอียดของการดำเนินการแต่ละแบบ มีดังนี้
- การสร้างคิววงกลมด้วยแถวลำดับ
- การเพิ่ข้อมูลให้กับคิววงกลม
- การนำข้อมูลออกคิววงกลม
การจัดการคิวด้วยรายการโยง
การแทนข้อมูลของคิวด้วยแถวลำดับมีข้อจำกัดเรื่องชนิดของข้อมูลต้องเป็นชนิดเดียวกัน และพื้นที่หน่วยความจำที่ใช้เป็นการจองใช้แบบถาวร จะปรับเพิ่มหรือปรับลดไม่ได้ ข้อจำกัดดังกล่าวจะไม่ปรากฎถ้าเปลี่ยนมาใช้รายการโยงแทน ทั้งนี้เนื่งจากรายการโยงเป็นโครงสร้างที่สร้างแบบระเบียนได้ นอกจากนี้การใช้พื้นที่หน่วยความจำหลักเป็นแบบพลวัต(dynamic) การดำเนินการขั้นพื้นฐานมีดังนี้
- การประกาศโครงสร้างข้อมูลคิววงกลม
- การเพิ่มข้อมูลลงในคิววงกลม
- การนำข้อมูลออกจากคิวงวกลม
- การแสดงข้อมูลในคิววงกลม
*********************************************************************************
ไม่มีความคิดเห็น:
แสดงความคิดเห็น