สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Queue
เรื่อง Queue
คิวเป็นโครงสร้างข้อมูลแบบหนึ่งซึ่งมีลักษณะที่ว่า ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง ขึ้นอยู่กับลำดับการเก็บข้อมูล จะเรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO) การเพิ่มข้อมูลจะเพิ่มจากด้านท้ายหรือเรียร์
การทำงานของคิว
1.การใส่ข้อมูลตัวใหม่ลงในคิว เรียกว่า Enqueue ก่อนที่จะใส่ข้อมูลลงไปต้องตรวจสอบก่อนว่าคิวเต็มหรือไม่ ถ้าพยายามใส่ข้อมูลลงไปอาจเกิดข้อผิดพลาด ที่เรียกว่า overflow
2.การนำสมาชิกออกจากคิว เรียกว่า Dequeue จะไม่สามารถนำข้อมูลออกจากคิวที่ว่างได้ ถ้าพยายามนำข้อมูลออกอาจเกิดข้อผิดพลาดที่เรียกว่า underflow
3.การนำข้อมูลที่อยู่ตอนต้นของคิวหรือข้อมูลที่อยู่ลำดับแรกมาแสดง เรียกว่า Queue Front เพื่อรู้ว่าข้อมูลตัวต่อไปคืออะไร
4.การนำข้อมูลที่อยู่ตอนท้ายของคิว หรือข้อมูลที่เข้ามาตัวสุดท้ายมาแสดง เรียกว่า Queue Rear เพื่อรู้ว่าข้อมูลตัวสุดท้ายคืออะไร
การแทนที่ข้อมูลของคิว มี 2 วิธี คือ
1.การแทนที่ข้อมูลของคิวแบบอะเรย์ มีการกำหนดขนาดของคิวไว้ล่วงหน้าว่ามีขนาดเท่าไร และจะมีการจัดสรรเนื้อที่หน่วยความจำให้เลย เมื่อพื้นที่ของอะเรย์มีพื้นที่ว่าง อาจหมายความว่า พื้นที่ว่างนั้นเคยเก็บข้อมูลแล้วกับพื้นที่ว่างนั้นยังไม่เคยเก็บข้อมูลมาก่อน
*** กรณีที่ Front ไม่ได้อยู่ช่องแรก พื้นที่ว่างจะไม่สามารถใช้งานได้อีก จะแก้โดยใช้คิวแบบวงกลม คือ ช่องสุดท้ายต่อกับช่องแรก คิวแบบวงกลมจะเต็มก็ต่อเมื่อ rear มีค่าน้อยกว่า front
2.การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์ ประกอบไปด้วย 2 ส่วน คือ Head Node มี 3 ส่วนมีพอยเตอร์ 2 ตัว และจำนวนสมาชิก กับ Data Node จะมีข้อมูล และพอยเตอร์ชี้ตัวถัดไป
การดำเนินการเกี่ยวกับคิว
1.Create Queue คือการสร้างคิวขึ้นมา แล้วจัดสรรหน่วยความจำให้กับ Head Node และพอยเตอร์มีค่าเป็น Null
2.Enqueue คือ การเพิ่มข้อมูลลงไปในคิวโดยการเพิ่มจะเพิ่มจากส่วนท้าย
3.Dequeue คือ การนำข้อมูลในคิวออก จะออกโดยข้อมูลที่เข้าไปตัวแรกจะออกก่อน
4.Queue Front คือ การนำข้อมูลตัวแรกที่เข้าไปในคิวออกมาแสดง
5.Queue Rear คือ การนำข้อมูลตัวสุดท้ายที่เข้ามาในคิวออกมาแสดง
6.Empty Queue คือ เป็นการตรวจสอบว่าคิวนั้นยังคงว่างอยู่หรือไม่
7.Full Queue คือ เป็นการตรวจสอบว่าคิวนั้นเต็มหรือไม่
8.Queue Count คือ เป็นการนับจำนวนข้อมูลที่อยูในคิว ว่ามีจำนวนเท่าไร
9.Destroy Queue คือ การลบข้อมูลที่อยูในคิวทิ้ง
การประยุกต์ใช้คิว จะถูกประยุกต์ใช้มากในระบบธุรกิจ เช่นการให้บริการลูกค้า คือลูกค้าที่มาก่อนย่อมต้องได้รับบริการก่อน และในด้านคอมพิวเตอร์ในระบบปฏิบัติงาน (Operating System) คือจัดให้งานที่เข้ามา ได้ทำงานตามความสำคัญ (Priority)
***เช่น สมมติว่า Priority มีงาน 3 ระดับ เรียงจากมากไปหาน้อยระบุโดยตัวเลข เลข 1 มากสุดเรื่อยไปจนถึง 3 น้อยสุด ถ้ามีงาน A,B,C เข้ามาขอใช้ CPU โดยมี Priority เป็น 4,2,1, ตามลำดับ ที่นี้งาน C จะถูกนำไปทำงานก่อน ตามด้วย B และ A
ไม่มีความคิดเห็น:
แสดงความคิดเห็น