สรุปคิว (Queue)
คิว (queue) คือโครงสร้างข้อมูลที่มีลักษณะเป็นแบบเชิงเส้นตรง (Linear list) มีปลายเปิด 2ด้านซึ่ง
1. การนำข้อมูลเข้า (enqueue) นำข้อมูลเข้าที่ปลายด้านหลังของโครงสร้างคิว
2. การนำข้อมูลออก (dequeue) นำข้อมูลออกที่ปลายด้านหน้าของโครงสร้างคิว
คุณสมบัตินี้เรียกว่า “เข้าก่อนออกก่อน” (First come, first serve หรือ first in, first out: FIFO) ในคิว ผู้ที่อยู่หน้าจะได้ซื้อตั๋วหนังหรือได้รับการบริการก่อน
ตัวอย่างการใช้
1. คนเข้าคิวซื้อตั๋วหนัง
2. นักศึกษาเข้าคิวเพื่อรับบริการในธนาคาร
3. นักศึกษาเข้าคิวซื้ออาหาร
4. ลูกค้าเข้าคิวจ่ายเงินที่เค้าเตอร์
การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย 2 ส่วน คือ
1. Head Nodeจะประกอบไปด้วย 3 ส่วนคือพอยเตอร์จำนวน 2 ตัว คือ Front และ rearกับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับคิว
การดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queueจัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าเป็น null และจำนวนสมาชิกเป็น 0
2. Enqueueการเพิ่มข้อมูลเข้าไปในคิว
3. Dequeueการนำข้อมูลออกจากคิว
4. Queue Frontเป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rearเป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queueเป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Countเป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9. Destroy Queueเป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว
การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้าพยายามนำเข้าจะทำให้เกิดความผิดพลาดที่เรียกว่า overflowการนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ ถ้าพยายามจะทำ
ให้เกิดความผิดพลาดที่เรียกว่าunderflow
การประยุกต์ใช้งานคิวในการจำลองแบบ
การจำลองแบบ (Simulation) หมายถึง การใช้ระบบหนึ่งเพื่อเลียนแบบพฤติกรรมของอีกระบบหนึ่ง ใช้งานเมื่อการทดลองด้วยระบบจริงๆ มีค่าใช้จ่ายสูง หรือเสี่ยงต่ออันตราย การจำลองแบบของคอมพิวเตอร์ จะใช้ขั้นตอนการทำงานของโปรแกรม เพื่อการเลียนแบบพฤติกรรมของระบบที่เราต้องการศึกษา
การจำลองแบบของระบบแบ่งกันใช้เวลา
ระบบคอมพิวเตอร์ที่มีการทำงานแบบแบ่งกันใช้เวลา เป็นระบบที่มีผู้ใช้เครื่องคอมพิวเตอร์พร้อมกันในเวลาเดียวกัน โดยระบบมีหน่วยผลกลาง (ซีพียู) และหน่วยความจำหลักเพียงอย่างละ 1 เท่านั้น ผู้ใช้หลายๆ คนนี้ จะต้องมีการใช้หน่วยความจำหลักและหน่วยประมวลผลกลางร่วมกัน ซึ่งอนุญาติให้ผู้ใช้แต่ละคนประมวลผลโปรแกรม (ใช้ทรัพยากรของระบบ) ในเวลาหนึ่งๆ แล้วก็จะให้ผู้ใช้คนต่อไปใช้จนกว่าจะวนกลับมายังผู้ใช้คนแรกอีก วิธีการประมวลผลร่วมกันระหว่างผู้ใช้หลายๆ คน เราเรียกว่า ระบบแบ่งกันใช้เวลา (Time sharing) ซึ่งลักษณะการใช้ซีพียูจะเป็นไปตามลำดับคือ “มาก่อนได้ก่อน” (first – come – first – serve) และมีลำดับการทำงานดังนี้
1. เมื่อโปรแกรมขอใช้เวลาซีพียู โปรแกรมนั้นจะถูกนำไปต่อท้ายคิวประมวลผล
2. โปรแกรมที่อยู่ต้นคิวจะถูกส่งไปทำงาน และยังคงอยู่ที่ต้นคิวจนกว่าจะใช้ซีพียูเสร็จ
3. เมื่อรันโปรแกรมทำงานเสร็จตามเวลาการขอใช้ซีพียู ก็จะถูกนำออกจากคิว และจะไม่ถูกนำกลับมาอีก จนกว่าจะมีการขอใช้ซีพียูครั้งใหม่ (จึงจะกลับไปที่ข้อ 1. อีก)
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น