สรุป Queue
โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้นที่มีลักษณะของการทำงานตรงกันข้ามกับสแตกคือ หากมีการนำเข้าข้อมูลใดก่อนเมื่อต้องการเรียนใช้ก็จะเรียกใช้ข้อมูลที่เข้ามาก่อน ถือเป็นรูปแบบของการทำงานที่สามารถพบเห็นได้ในปัจจุบันมากที่สุดในลักษณะของการเรียงต่อแถวหากใครที่มาต่อแถวเพื่อทำกิจกรรมใดก่อนก็จะมีสิทธิ์ได้ทำกิจกรรมนั้น ๆ ก่อน คนที่มาทีหลังเป็นเช่นนี้ไปจนกว่าจะถึงลำดับสุดท้าย
โครงสร้างของคิว
- ข้อมูลใดเข้ามาก่อน ก็จะดำเนินการก่อน หากเข้ามาทีหลังก็จะดำเนินการทีหลังเราเรียกว่า First in first out (FIFO) หรือเข้าก่อนออกก่อน
สำหรับการที่มีข้อมูลเข้ามาให่ในคิวและต่อด้าน rear จะเรียกการดำเนินการในลักษณะนี้ว่าEnqueue และสำหรับการนำเอาข้อมูลในส่วน Front ออกไปจากคิวจะเรียกการดำเนินการในลักษณะนี้ว่า Dequeue
พื้นฐานการดำเนินการกับคิว
1. Enqueue หรือ การนำเข้าข้อมูลของคิวนั้นแรกเริ่มหากมีการนำเข้าข้อมูลแรกเข้าสู่คิวแล้วข้อมูลนี้จะเป็นข้อมูลอันดับแรกและเมื่อมีการเพิ่มข้อมูลเข้ามาอีกข้อมูลที่เพิ่มเข้ามาใหม่ก็จะต่อท้ายในส่วนของ rear นั่นก็คือ การต่อท้ายข้อมูลแรกนั่นเอง
ดังภาพ
2. Dequeue หรือ การนำข้อมูลออก ถือเป็นการดำเนินการพื้นฐานอีกประการของโครงสร้างคิวที่จะนำออกข้อมูลซึ่งถือเป็นสมาชิกของคิวโดย จะกระทำเฉพาะส่วนหัวหรือ Front ของโครงสร้างเท่านั้น
ดังภาพ
ทฤษฏีด้านการดำเนินการ
1. การดำเนินการสร้างคิว (Queue Create)การดำเนินการนี้เป็นขั้นแรกเริ่มของการจองพื้นที่บนหน่วยความจำเพื่อให้คิวนั้นสามารถที่จะเข้าใช้งานในการเก็บข้อมูลได้และค่าเริ่มต้นของคิวจะเป็นคิวที่ไม่มีข้อมูลหรือคิวว่าง
2. การดำเนินการ Enqueueการดำเนินการ Enqueue เป็นขั้นตอนของการนำเข้าข้อมูลเข้าสู่โครงสร้างคิว โดยการนำเข้าข้อมูลนั้นจะต้องทำงานเป็นกลไกที่ลำดับตามการมาก่อน หลัง สำหรับชนิดของข้อมูลนั้นต้องเป็นข้อมูลมาตรฐาน
3. การดำเนินการ Dequeueการ Dequeue จะดำเนินการดึงข้อมูลออกจากโครงสร้างซึ่งจะกระทำเฉพาะส่วนหัวของข้อมูลเท่านั้น
4. การดำเนินการตรวจสอบคิวว่างการตรวจสอบคิวว่างเพื่อที่จะไม่ให้เกิดข้อผิดพลาดในกรณีที่ต้องการนำเอาข้อมูลออกจากคิวซึ่งจะต้องมีการตรวจสอบก่อนทุกครั้ง เพราะถ้าหากคิวนั้นไม่มีข้อมูลอยู่แล้วพยายามดึงข้อมูลออกก็จะเกิดข้อผิดพลาด
5. การดำเนินการตรวจสอบคิวเต็มกรณีที่ต้องการนำเอาข้อมูลเข้าสู่โครงสร้างคิวจะต้องมีการตรวจสอบก่อนเสมอว่าคิวมีข้อมูลเต็มพื้นที่ที่จองไว้หรือยังหากข้อมูลนั้นเต็มพื้นที่ที่ไว้ก็จะไม่สามารถนำเข้าข้อมูลได้อีก
6. การดำเนินการล้างคิวการคิวเป็นการล้างข้อมูลที่ถูกจัดเก็บในโครงสร้าง
สรุป Queue (ต่อ)
การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ด้วยลิงค์ลิสต์ (Link List Implemention Of Queue)
สำหรับการแทนคิด้วยโครงสร้างลิงค์ลิสต์นั้นมีลักษณะเช่นเดียวกันกับการแทนสแตกด้วยลิงค์ลิสต์ คือต้องการปรับโครงสร้างให้สามารถเพิ่มหรือลดได้แบบไม่ตายตัว(Dynamic) ซึ่งลักษณะของโครงสร้างก็ยังคงประกอบไปด้วยพอยน์เตอร์ในการชี้ตำแหน่งfront และ rear ส่วนการลิงค์ของข้อมูลแต่ละโหนดก็จะใช้พอยน์เตอร์ของแต่ละโหนดเชื่อมโยงกัน
จากภาพ เป็นรูปแบบของโครงสร้างคิวที่แทนด้วยลิงค์ลิสต์ คิวนี้จะประกอบด้วยโหนดต่างๆซึ่งก็คือเรคอร์คที่จัดเก็บข้อมูลและลิงค์ไปยังโหนดต่อไป การชี้ของพอยน์เตอร์ frontและ rear นั้นจะถูกเก็บเป็นโฆนดเช่นเดียวกันโดย front จะเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดตัวแรก ส่วน rear จะเป็นพอยน์เตอร์ที่ชี้ไปยังโหนดสุดท้า้ย เมื่อมีการดำเนินการกับคิว ก็จะดำเนินการตามการทำงานคือการ Enqueue และ Dequeue การ Enqueue จะดำเนินการนำข้อมูลเพิ่มในส่วน rear ส่วนการ Dequeue จะดำเนินการในส่วนของ front
การดำเนินการกับคิวที่แทนด้วยโครงสร้างลิงค์ลิสต์สำหรับการดำเนินการที่สำคัญนั้นคือการดำเนินการ Enqueue การดำเนินการ Dequeue และการตรวจสอบคิวว่าง
1, การดำเนินการ Enqueueการดำเนินการ Enqueue ทำงานเช่นเดียวกันกับการแทรกโหนดในส่วนท้ายของลิสต์คือเมื่อมีการ Enqueue ข้อมูลใหม่เข้ามาก็จะเซตค่าของพอยน์เตอร์ให้ชี้มายังโหนด rear และกำหนดค่าการเชื่อมโยง = nil จากนั้นเซตพอยน์เตอร์ rear ให้ชี้มายังโหนดสุดท้ายแสดงได้ดังภาพ
2. การดำเนินการ Dequeueการดำเนินการ Dequeue จะดำเนินการในส่วน front หรือที่โหนดตัวแรกของโครงสร้างโดยเซตค่าพอยนเตอร์ที่ชี้ไปยังโหนดตัวแรกเปลี่ยนเป็นชี้ไปยังโหนดตัวถัดไป ทำให้โหนดตัวแรกถูกลบออกและโฆนดที่เป็นตัวแรกคือโหนดที่พอยน์เตอร์ front ชี้อยู่ปัจจุบัน ดังภาพ
3. การดำเนินการตรวจสอบคิวว่างการดำเนินการตรวจสอบคิวว่างเป็นการตรวสอบคิวว่ามีข้อมูลหรือไม่ เพื่อที่จะสามารถทราบได้ว่าหากในโครงสร้างนั้นมีข้อมูลอยู่ ก็สามารถที่จะทำการ Dequeu ข้อมูลออกไปได้ แต่ในกรณีที่คิวไม่มีข้อมูลก็จะมีการเซตค่าของโหนดที่จัดเก็บพอยน์เตอร์ front และ rear ให้มีค่าเป็น nil
การแทนที่ด้วยอาร์เรย์ (Array Implemention Of Queue)
การแทนโครงสร้างคิวด้วยอาร์เรย์นั้นจะทำให้สามารถกำหนดจำนวนของการจองพื้นที่บนหน่วยความจำได้และโดยเฉพาะอย่างยิ่งลักษณะการทำงานของคิวที่มีการทำงานของคิวที่มีการทำงานแบบเชิงเส้นจึงมีการใช้อาร์เรย์ในการนำข้อมูลเข้าด้านท้ายและนำข้อมูลออกในส่วนหัว
โครงสร้างของการแทนคิวด้วยอาร์เรย์
ในการแทนคิวด้วยอาร์เรย์นั้น จะต้องมีการระบุจำนวนสูงสุดของพื้นที่เก็บข้อมูล (Maxsize)พร้อมกันกับกำหนดพอยน์เตอร์ขึ้นมาอีก 2 ตัวคือ front และ rear เพื่อใช้นการชี้ค่าข้อมูลที่อยู่ส่วนหัวและส่วนท้ายดังภาพ
ส่วนการ Enqueue นั้นจะกระทำที่ส่วนของ Rear ทำให้ Rear มีการเพิ่มตำแหน่งขึ้นมา
ส่วนการ Dequeue นั้นจะกระทำที่ส่วนของ Front คือเลื่อน front จาก 0 ไปเป็น 1 ดังภาพ
การประยุกค์การใช้งานในระบบปฏิบัติการ
ตัวอย่างเช่น การทำบัฟเฟอร์ (Buffering)การทำบัฟเฟอร์จะใช้ในกรณีที่อัตราความเร็วในการทำงานของอุปกรณ์คอมพิวเตอร์มีการทำงานด้วยความเร็วที่แตกต่างกันยกตัวอย่างเช่น การทำงานของเครื่องพิมพ์กับ CPUซึ่งถือว่ามีการทำงานในอัตราความเร็วที่แตกต่างกันมาก แต่เมื่อต้องการส่งผ่านข้อมูลหากัน CPU ซึ่งมีการทำงานด้วยความเร็วจะทำการเก็บการประมวลผลส่งไปยังบัฟเฟอร์ก่อน เมื่อทำงานใดเสร็จบัฟเฟอร์ก็จะส่งต่อการทำงานให้เครื่องพิมพ์ทำงานจนกว่าจะหมดข้อมูลในบัฟเฟอร์สำหรับกาทำงานของ CPU และการของเครื่องพิมพ์
ไม่มีความคิดเห็น:
แสดงความคิดเห็น