เรื่อง Queue

เนื้อหา
- โครงสร้างข้อมูลแบบคิว
- การทำงานของคิว
- การแทนที่ข้อมูลของคิว
- การประยุกต์ใช้คิว

จุดประสงค์การเรียนรู้
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
2. Enqueue
3. Dequeue
4. Queue Front
5. Queue Rear
6. Empty Queue
7. Full Queue
8. Queue Count
9. Destroy Queue
Algorithm CreateQueue
Pre Nothing
Post Head has been allocated and initialized
Return Head’s address if successful, null if overflow
1. if (memory available)

allocate (newPrt)
2 newPtr->front = null pointer
3 newPtr->rear = null pointer
4 newPtr->count = 0
5 return newPtr
2. Else1 return null pointer
End CreateQueue

Algorithm EnQueue
Queue has been create
Post Item data have been inserted
Return Boolean; True: if successful, False ifoverflow
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 else1 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 userthrough item and front element deleted and recycled
Return Boolean; True: if successful, False ifunderflow
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 ifunderflow

5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
Algorithm QueueRearPre
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 queuehead node
Return Boolean; True: if empty, False if queuehas 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 anothernode
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 queuehead 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 pointer1.
End DestroyCount

การแทนที่ข้อมูลของคิวแบบอะเรย์

การนำข้อมูลเข้าสู่คิว จะไม่สามารถนำเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่าง ถ้าพยายาม นำเข้าจะทำให้เกิดความผิดพลาดที่เรียกว่า overflow การนำข้อมูลออกจากคิว จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่าได้ถ้าพยายามจะทำให้เกิดความผิดพลาดที่เรียกว่า underflow ในการใส่สมาชิกลงในคิวจะต้องตรวจสอบ ก่อนว่าคิวเต็ม หรือไม่

จากตัวอย่าง จะเห็นได้ว่าอาจจะมีปัญหาในการนำเข้าข้อมูลในกรณีที่คิวเต็มแต่สภาพความเป็นจริงแล้ว front ไม้ได้อยู่ในช่องแรก ของคิว จะไม่สามารถนำที่ว่างในส่วนหน้ามาใช้ได้อีก
วิธีการแก้ปัญา ดั้งกล่าว จะใช้คิวที่เป็น แบบคิววงกลม(Circular Queue)ซึ่งคิวช่องสุดท้ายนั้นต่อกับคิวช่องแรกสุด

จากตัวอย่าง จะเห็นได้ว่าอาจจะมีปัญหาในการนำเข้าข้อมูลในกรณีที่คิวเต็มแต่สภาพความเป็นจริงแล้ว front ไม้ได้อยู่ในช่องแรก ของคิว จะไม่สามารถนำที่ว่างในส่วนหน้ามาใช้ได้อีกวิธีการแก้ปัญา ดั้งกล่าว จะใช้คิวที่เป็น แบบคิววงกลม(Circular Queue)ซึ่งคิวช่องสุดท้ายนั้นต่อกับคิวช่องแรกสุด

แบบฝึกหัด
1. อธิบายหลักการทำงานของ Queue
2. การแทนที่ของข้อมูลในคิวมีกี่ประเภทอะไร้บาง อธิบายพร้อมยกตวอย่างประกอบ
3. การประยกตใช คว ในชวตประจาวนทเกดขน