- โครงสร้างข้อมูลแบบคิว
- การทำงานของคิว
- การแทนที่ข้อมูลของคิว
- การประยุกต์ใช้คิว
จุดประสงค์การเรียนรู้
1. เพี่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบคิว และการทำงาน
2. เพื่อให้ทราบวิธีการแทนที่ข้อมูลแบบคิว
3. เพื่อให้นักศึกษาทราบวิธีการประยุกต์ใช้สแตก
คิว(Queue)เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสตซึ่งการเพิ่มข้อมูลจะกระทำทีปลายข้างหนึ่งซึ่งเรียกว่าสวนท้ายหรือเรียร์ (rear)และการนำข้อมูลออกจะ กระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกวา ส่วนหน้า หรือฟรอนต์(front)ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อน ออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
การใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue ซึ่งมีรูปแบบคือ
enqueue (queue, newElement) หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์
แสดงการเพิ่มข้อมูลเข้าไปในคิว
การนำสมาชิกออกจากคิว เรียกว่า Dequeue ซึ่งมีรูปแบบคือ
dequeue (queue, element)
หมายถึง การนำออกจากส่วนหน้า ของคิวและให้ ข้อมูลนั้นกับ element
แสดงการนำข้อมูลออกจากคิว
การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะ เรียกว่า Queue Frontแต่จะไม่ทำการเอาข้อมูลออกจากคิว
แสดงการนำข้อมูลตอนต้นของคิวมาแสดง
การนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดงจะ เรียกว่าQueue Rear แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว
แสดงการนำข้อมูลตอนท้ายของคิวมาแสดง
การแทนที่ข้อมูลของคิว
การแทนที่ข้อมูลของคิวสามารถทาได 2 วิธ๊ คอ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสค์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 3 ส่วนคือ พอยเตอร์จำนวน 2 ตัว คือ Front และ rear กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับคิว
การดำเนินการเกี่ยวกับคิว ได้แก่
1. Create Queue 6. Empty Queue
2. Enqueue 7. Full Queue
3. Dequeue 8. Queue Count
4. Queue Front 9. Destroy Queue
5. Queue Rear
Algorithm CreateQueue
Pre Nothing
Post Head has been allocated and initialized
Return Head’s address if successful, null if overflow 1.
if (memory available)
1 allocate (newPrt)
2 newPtr->front = null pointer
3 newPtr->rear = null pointer
4 newPtr->count = 0
5 return newPtr
2. Else
1 return null pointer
End CreateQueue
Algorithm EnQueue
Queue has been create
Post Item data have been inserted
Return Boolean; True: if successful, False if
overflow
1. if (queue full)
1 return false
1 allocate(newPtr)
2 newPtr->data = item
3 newPtr->next = null pointer
4 if (queue->count zero)
1 queue->front = newPtr
5 else
1 queue->rear->next = newPtr 6 queue->rear = newPtr
7 queue->count = queue->count+1 8 return true
End EnQueue
Algorithm DeQueue
Queue has been create
Data at front of queue returned to user
through item and front element deleted and recycled
Return Boolean; True: if successful, False if
underflow
1. if (queue->count is 0)
1 return false
1 item = queue->front->data
2 deleteLoc = queue->front
3 if (queue->count 1)
1 queue->rear = null pointer
4 queue->front = queue->front->next
5 queue->count = queue->count-1
6 recycle(deleteLoc)
7 return true
End Dequeue
4.Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมา
Algorithm QueueFront
Queue is a pointer to an initialized queue
Post Data pass back to caller
Return Boolean; True: successful, False if
underflow
5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
Algorithm QueueRear
Pre Queue is a pointer to an initialized queue
Post Data pass back to caller
Return Boolean; True: successful, False if underflow
6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
Algorithm EmptyQueue
Queue is a pointer to a queue
head node
Return Boolean; True: if empty, False if queue
has data
1. Return (queue->count equal 0)
End EmptyQueue
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
Algorithm FullQueue
Pre Queue is a pointer to a queue head node
Return Boolean; True: if full, False if room for another
node
1. allocate (tempPtr)
2. if (allocation successful)
1 release (tempPtr)
2 return false
3. else
1 return true
End FullQueue
8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
Algorithm QueueCount
Queue is a pointer to the queue
head node
Return Queue count
1. Return queue->count
End QueueCount
9. Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว
Algorithm DestroyQueue
Queue is valid queue
All data have been deleted and recycled
Return null pointer
1. pWalker = queue->front
2. Loop(pWalker not null)
1 deletePtr = pWalker
2 pWalker = pWalker->next
3 recycle (deletePtr)
4 recycle (queue)
5 return null pointer
1. End DestroyCount
การแทนที่ข้อมูลของคิวแบบอะเรย์
การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้าพยายาม นำเข้าจะทำให้เกิดความผิดพลาดที่
เรียกว่า overflow การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ถ้าพยายามจะทำให้เกิดความผิดพลาดที่เรียกว่า underflow ในการใส่สมาชิกลงในคิวจะต้องตรวจสอบ ก่อนว่าคิวเต็ม หรือไม่
จากตัวอย่าง จะเห็นได้ว่าอาจจะมีปัญหาในการนำเข้าข้อมูลในกรณีที่คิวเต็มแต่สภาพความเป็นจริงแล้ว front ไม้ได้อยู่ในช่องแรก
ของคิว จะไม่สามารถนำที่ว่างในส่วนหน้ามาใช้ได้อีก
วิธีการแก้ปัญา ดั้งกล่าว จะใช้คิวที่เป็น แบบคิววงกลม(Circular Queue)ซึ่งคิวช่องสุดท้ายนั้นต่อกับคิวช่องแรกสุด
ในกรณีที่เป็นคิวแบบวงกลมคิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อย ๆ จนกระทั่ง rearมีค่าน้อยกว่า front อยู่หนึ่งค่า
คือ rear = front - 1
การประยุกต์ใช้คิว
คิวถูกประยุกต์ใช้มากในการจำลองระบบงาน ธูรกิจ เช่น การให้บริการลูกค้า ต้องวิเคราะห์จำนวน ลูกค้าในคิวที่เหมาะสมว่าควรเป็นจานวันเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อย ที่สุด ในด้านคอมพิวเตอร์ได้นำคิวเข้ามาใช้ คือในระบบปฏิบัตการ (OperationSystem)ในเรื่องของคิวของงานที่เข้ามาทำงาน (ขอใช้ทรัพยากระบบของ CPU)จะจัดให้งานที่เขามาได้ทำงานตามลำดับความคัญ
แบบฝึกหัด
1. อธิบายหลักการทำงานของ Queue
2. การแทนที่ของข้อมูลในคิวมีกี่ประเภทอะไร้บาง อธิบายพร้อมยกตวอย่างประกอบ
3. การประยกตใช คว ในชวตประจาวนทเกดขน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น