สรุป เรื่อง Queue
คิวเป็นโครงสร้างข้อมูลแบบลำดับ (Sequential) ลักษณะของคิวเราสามารถพบได้ในชีวิตประจำวัน เช่น การเข้าแถวตามคิวเพื่อรอรับบริการต่างๆ ลำดับการสั่งพิมพ์งาน เป็นต้น ซึ่งจะเห็นได้ว่าลักษณะของการทำงานจะเป็นแบบใครมาเข้าคิวก่อน จะได้รับบริการก่อน เรียกได้ว่าเป็นลักษณะการทำงานแบบ FIFO (First In , First Out) ลักษณะของคิว จะมีปลายสองข้าง ซึ่งข้างหนึ่งจะเป็นช่องทางสำหรับข้อมูลเข้าที่เรียกว่า REAR และอีกข้างหนึ่งซึ่งจะเป็นช่องทางสำหรับข้อมูลออก เรียกว่า FRONT
การสร้างคิว (Queue) คิวที่อยู่ในคอมพิวเตอร์สามารถจัดเก็บได้หลายลักษณะ แต่โดยทั่วไปแล้วจะใช้การจัดเก็บแบบลิงค์ลิสท์เดี่ยวหรือจัดเก็บโดยใช้อาร์เรย์ ก่อนที่จะทำการสร้างคิวจะต้องทำความเข้าใจถึงโครงสร้างของคิว ซึ่งประกอบไปด้วย ตัวคิว ซึ่งในที่นี้ขอแทนด้วยอาร์เรย์ และจะต้องมีตัวชี้อีก 2 ตัว ได้แก่ ตัวชี้ F (Front Pointer) ชี้ไปที่สมาชิกตัวแรก และตัวชี้ R (Rear Pointer) ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวจะออกทาง
ในการทำงานกับคิวที่ต้องมีการนำข้อมูลเข้าและออกนั้น จะต้องมีการตรวจสอบว่าคิวว่างหรือไม่ เมื่อต้องการนำข้อมูลเข้า เพราะหากคิวเต็มก็จะไม่สามารถทำการนำข้อมูลเข้าได้ เช่นเดียวกัน เมื่อต้องการนำข้อมูลออกก็ต้องตรวจสอบด้วยเช่นกัน ว่าในคิวมีข้อมูลอยู่หรือไม่ หากคิวไม่มีข้อมูลก็จะไม่สามารถนำข้อมูลออกได้เช่นกัน การInsertion เป็นการนำข้อมูลเข้าสู่คิว โดยการที่จะนำข้อมูลเข้าสู่คิวนั้นจะแบ่งออกเป็น 2 กรณี คือ
1. การนำข้อมูลเข้าไปในคิวว่าง โดยจะต้องดำเนินการให้พอยน์เตอร์ทั้ง 2 คือ F และ R ชี้ไปยังช่องแรกหรือตำแหน่งที่จะเก็บข้อมูลแรก
2. การนำข้อมูลเข้าไปในคิวต่อจากข้อมูลเดิม จะต้องจัดการให้พอยน์เตอร์ R ชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไป ส่วนพอยน์เตอร์ F ยังคงชี้ไปยังช่องหรือตำแหน่งของข้อมูลที่นำเข้าไปเป็นข้อมูลแรก
การ Deletion
เป็นการนำข้อมูลที่เก็บอยู่ในคิวออกจากคิว โดยการเมื่อทำการ Deletion ข้อมูลนั้นออกจากคิวแล้ว จะต้องมีการจัดการให้ตัวชี้คิว F ชี้ไปยังช่องหรือตำแหน่งต่อจากข้อมูลที่จะได้ทำการ Deletion ไปแล้ว ส่วนพอยน์เตอร์ R ชี้ไปยังช่องข้อมูลสุดท้ายเหมือนเดิมการ Deletion ข้อมูลนี้จะทำการนำข้อมูลในส่วนของข้อมูลตัวแรกสุดที่เข้าสู่คิวออกไปทำงานตามต้องการ แต่การ Deletion ข้อมูลนี้จะไม่สามารถ Deletion ข้อมูลออกจากคิวที่ว่างเปล่าหรือไม่มีข้อมูลได้ (F = 0) ถ้าเกิดกรณีเช่นนี้จะเกิด Error ที่เรียกว่า Underflow ขึ้น ฉะนั้นก่อนที่จะทำการ Deletion ควรที่จะต้องมีการตรวจสอบว่าคิวว่างหรือไม่ เพื่อไม่ให้เกิด Error นี้ขึ้น
การประยุกต์ใช้งานคิวในการจำลองแบบการจำลองแบบ (Simulation) หมายถึง การใช้ระบบหนึ่งเพื่อเลียนแบบพฤติกรรมของอีกระบบหนึ่ง ใช้งานเมื่อการทดลองด้วยระบบจริงๆ มีค่าใช้จ่ายสูง หรือเสี่ยงต่ออันตราย การจำลองแบบของคอมพิวเตอร์ จะใช้ขั้นตอนการทำงานของโปรแกรม เพื่อการเลียนแบบพฤติกรรมของระบบที่เราต้องการศึกษาการจำลองแบบของระบบแบ่งกันใช้เวลาระบบคอมพิวเตอร์ที่มีการทำงานแบบแบ่งกันใช้เวลา เป็นระบบที่มีผู้ใช้เครื่องคอมพิวเตอร์พร้อมกันในเวลาเดียวกัน โดยระบบมีหน่วยผลกลาง (ซีพียู) และหน่วยความจำหลักเพียงอย่างละ 1 เท่านั้น ผู้ใช้หลายๆ คนนี้ จะต้องมีการใช้หน่วยความจำหลักและหน่วยประมวลผลกลางร่วมกัน ซึ่งอนุญาติให้ผู้ใช้แต่ละคนประมวลผลโปรแกรม (ใช้ทรัพยากรของระบบ) ในเวลาหนึ่งๆ แล้วก็จะให้ผู้ใช้คนต่อไปใช้จนกว่าจะวนกลับมายังผู้ใช้คนแรกอีก วิธีการประมวลผลร่วมกันระหว่างผู้ใช้หลายๆ คน เราเรียกว่า ระบบแบ่งกันใช้เวลา (Time sharing) ซึ่งลักษณะการใช้ซีพียูจะเป็นไปตามลำดับคือ “มาก่อนได้ก่อน” (first – come – first – serve) และมีลำดับการทำงานดังนี้1. เมื่อโปรแกรมขอใช้เวลาซีพียู โปรแกรมนั้นจะถูกนำไปต่อท้ายคิวประมวลผล2. โปรแกรมที่อยู่ต้นคิวจะถูกส่งไปทำงาน และยังคงอยู่ที่ต้นคิวจนกว่าจะใช้ซีพียูเสร็จ3. เมื่อรันโปรแกรมทำงานเสร็จตามเวลาการขอใช้ซีพียู ก็จะถูกนำออกจากคิว และจะไม่ถูกนำกลับมาอีก จนกว่าจะมีการขอใช้ซีพียูครั้งใหม่ (จึงจะกลับไปที่ข้อ 1. อีก)การจำลองแบบสนามบินการเขียนโปรแกรมเพื่อจำลองแบบของสนามบิน จะใช้โครงสร้างข้อมูลแบบคิว แทนคิวของเครื่องบินที่จะรอขึ้นหรือรอลง แต่คอนข้างเป็นโปรแกรมที่ซับซ้อน ดังสภาพความเป็นจริงที่ว่า สนามบินมีขนาดเล็กแต่มีเครื่องบินขึ้นลงจำนวนมาก มีทางวิ่ง (runway) เพียงทางเดียว ดังนั้น ณ เวลาใด ๆ เครื่องบิน จะต้องขึ้นหรือลงอย่างใดอย่างหนึ่งเท่านั้น และเพียงเครื่องเดียวด้วย ในเวลาที่เครื่องบินซึ่งพร้อมจะขึ้นหรือลงมาถึงสนามบิน สนามบินนั้นอาจจะว่างหรือมีเครื่องบินอื่นกำลังขึ้นหรือลงอยู่ก็ได้ และอาจจะมีเครื่องบินหลายลำที่รอขึ้นและรอลง จึงมีคิว 2 คิวเกิดขึ้น คือ คิวขึ้น (takeoff) และคิวลง ( landing) ในการรอนั้นบนพื้นจะดีกว่าบนอากาศ ดังนั้นจึงให้เครื่องบินขึ้นได้ก็ต่อเมื่อไม่มีเครื่องบินลง หลักจากได้รับสัญญาณร้องขอจากเครื่องบินลำใหม่เพื่อจะลงหรือขึ้น โปรแกรมการจำลองแบบจะให้บริการเครื่องบินที่อยู่ในตำแหน่งหัวคิวของคิวลงก่อน และถ้าคิวลงว่าง จึงอนุญาตให้เครื่องบินในคิวขึ้นขึ้นได้ โปรแกรมจำลองแบบนี้สามารถจะทำงานได้ตลอดเวลา
ไม่มีความคิดเห็น:
แสดงความคิดเห็น