Queues Structure

บทที่ 4

คิว

Queues Structure

                โครงสร้างการทำงานแบบคิวคือการมีการจัดลำดับการเข้าและออกข้อมูลอย่างเป็นลำดับ ข้อมูลใดเข้ามาก่อนก็จะดำเนินการก่อน  หากข้อมูลใดเข้ามาทีหลังก็จะดำเนินการทีหลัง เรียกลักษณะของการดำเนินการแบบนี้ว่า  First In First Out (FIFO) หรือเข้าก่อนออกก่อน

ลักษณะของคิว

•                    โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้นและไม่เชิงเส้น

•                     มีทางเข้าและออก 2  ทาง

•                    มีการทำงานแบบลำดับ

•                    สามารถนำข้อมูลเข้าและนำข้อมูลออกสลับกันได้

•                    มีลำดับการทำงานแบบเข้าก่อนออกก่อน (FIFO)

ประเภทของคิว มี 3 ประเภท

•                    คิวธรรมดา (Queue)

•                    คิววงกลม (Circular Queue)

•                    คิวที่เรียงลำดับตามความสำคัญ (Priority Queue)

การดำเนินการของคิว

     เมื่อนำเข้าข้อมูลจะต้องจัดเรียงในลักษณะการต่อท้ายกัน

•                    ข้อมูลที่อยู่ส่วนท้ายของการเก็บข้อมูล เรียกว่า  Rear

•                    ข้อมูลที่อยู่ส่วนหัวของการเก็บข้อมูล ซึ่งจะเรียกว่า  Front

•                    การนำข้อมูลเข้าไปในคิว  เรียกว่า Insert (Enqueue)

•                    การนำข้อมูลออกจากคิว เรียกว่า Remove (Dequeue)

•                    คิวธรรมดา (Queue)

•                    คิวธรรมดา หมายถึง คิวที่มีการนำข้อมูลเข้าทางท้ายคิว (Rear) และนำข้อมูลออกหางคิว (Front) โดยถ้าท้ายคิวไปอยู่ที่ตำแหน่งท้ายสุดของคิวแล้ว ถึงแม้จะมีช่องว่างเหลือที่หัวคิวก็ไม่สามารถนำข้อมูลใหม่ไปเก็บได้ จนกว่าจะนำข้อมูลในคิวออกให้หมดก่อนจึงเริ่มนำข้อมูลใหม่ไปเก็บได้

 

การนำข้อมูลเข้า Enqueue

ž             ก่อนนำสมาชิกเข้าคิว ต้องตรวจสอบว่าคิวเต็มหรือไม่ โดยที่ ถ้า rear = maxQ แสดงว่าคิวเต็ม (เมื่อ maxQ คือขนาดของคิว)

•                    การนำข้อมูลใหม่เข้ามาแถวคอย จะเพิ่มเข้ามาด้านหลัง

•                    และจะนำเข้ามาเรื่อย ๆ จนเต็ม หรือเรียกว่า แถวคอยเต็ม (Queue Overflow)

•                    ดังนั้นการนำสมาชิกเข้าคิว จึง เป็นการเพิ่มค่าพอยน์เตอร์ rear

•                    หากมีสมาชิกในคิวเพียงค่าเดียวพอยน์เตอร์ rear และ front จะเท่ากัน

•                    Queue : Array Implementation

•                    INSERT-Q Algorithm

•                     

                front = rear = 0

                if( rear == maxQ)

                                write “Overflow”

                else

                                if(front==0)

                                                front  ← 1

                                                rear ← 1

                                                Q[rear] ← Item

                                Else

                                                rear  ←  rear + 1

                                                 Q[rear] ← Item

การนำข้อมูลออก  Dequeue

ž             ก่อนนำสมาชิกออกจากคิว ต้องตรวจสอบดูก่อนว่าคิวว่างเปล่าหรือไม่ โดยเงื่อนไขการตรวจสอบคือ front = rear = 0

•                    ข้อมูลที่จะนำออกก่อนจะเป็นข้อมูลที่อยู่ ด้านหน้า

•                    สามารถนำข้อมูลออกเรื่อย ๆ จนไม่มีข้อมูล หรือเรียกว่า แถวคอยว่าง  (Queue Underflow)

•                    ดังนั้นการนำสมาชิกออกจากคิวจึง เป็นการเพิ่มค่าพอยน์เตอร์ front

คิววงกลม (Circular Queue)

•                    คิววงกลม หมายถึง คิวที่ถูกออกแบบมาให้มีลักษณะเป็นวงกลมเพื่อให้สามารถนำข้อมูลใหม่ไปเก็บไว้ที่ช่องว่างด้านหน้าคิวได้ คิววงกลมออกแบบมาเพื่อแก้ปัญหาคิวธรรมดา

คิววงกลม (Circular Queue)

•                    ลักษณะของคิวแบบวงกลม

•                    เหมือนคิวธรรมดาคือมีตัวชี้ 2 ตัวคือ front และ rear สำหรับแสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ

•                    แตกต่างจากคิวธรรมดา คือ คิวธรรมดาเมื่อ rear ชี้อยู่ที่ตำแหน่งสุดท้ายของคิว จะทำให้ไม่สามารถเพิ่มข้อมูลเข้าไปในคิวได้อีก ทั้งที่บางครั้งยังมีที่ว่างเหลืออยู่ก็ตาม

Circular Queue

•                    ลักษณะของคิวแบบวงกลม (ต่อ)

•                    คิววงกลมจัดการปัญหานี้โดย กรณี rear ชี้อยู่ที่ตำแหน่งสุดท้ายของคิว ถ้าหากมีการเพิ่มข้อมูล ค่าของ rear จะสามารถวนกลับมาชี้ยังตำแหน่งแรกสุดของคิวได้

•                    ดังนั้นคิววงกลมจะสามารถเพิ่มข้อมูลเข้าไปในคิวได้ จนกว่าคิวจะเต็มจริง ๆ

คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ
(Priority Queue)

        บางครั้งเราพบว่า การเข้ารับบริการ ไม่เป็นไปตามกฎของคิว  เนื่องจากได้รับอภิสิทธิ์ (priority) ให้สามารถเข้ารับบริการก่อนได้ เช่น  ลูกค้าประจำจะได้รับการบริการก่อน ถึงแม้จะเข้ามาทีหลังลูกค้าจรคนอื่นที่คอยอยู่ก็ตาม  หรือในร้านถ่ายเอกสาร ถ้าพนักงานกำลังถ่ายเอกสารให้ลูกค้าคนหนึ่งจำนวน 100 หน้า แล้วมีลูกค้าใหม่มาขอถ่ายเพียงแค่ 2 หน้า พนักงานก็บริการให้ลูกค้าคนใหม่นั้นทันที

คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ
(Priority Queue)

•                    ใน คิวธรรมดา ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน (First In First  Out:FIFO) อย่างไรก็ตาม มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่น การให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท

•                    คิวลำดับความสำคัญทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน ส่งผลให้เราสามารถจัดเรียงคิวได้ใหม่ให้เหมาะสมกับการทำงานได้ เราใช้คิวลำดับความสำคัญในการจัดการทำงานการตรวจนับ

คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ
(Priority Queue)

	คิวลำดับความสำคัญ หรือ แถวคอยเชิงบุริมภาพ (Priority Queue)

Priority Queue

                ในการทำงานกับคิวแบบนี้ ต้องมีค่าอภิสิทธิ์ของแต่ละสมาชิกเก็บไว้ด้วย เพื่อใช้หาตำแหน่งที่อยู่ก่อนหน้าสมาชิกที่มีอภิสิทธิ์ต่ำกว่าและตามหลังสมาชิกที่มีอภิสิทธิ์เท่ากันหรือสูงกว่า

• typedef struct {   int    priority;

                                 char data;

                             }  Queue;

     Queue    priority_queue[15];

การประยุกต์ใช้ Queue

ตัวอย่างการประยุกต์คิวมาใช้งานบนคอมพิวเตอร์

-  การเข้าคิวของโปรเซสหรืองานต่าง ๆ เพื่อรอการประมวลผลจากซีพียูตามลำดับ

-  การแบ่งเวลา (Time Sharing) ด้วยการจำกัดตารางเวลาการประมวลผลของแต่ละโปรเซส ส่งผลให้สามารถหมุนเวียนการประมวลผลในแต่ละโปรเซสสลับไปมาได้ ทำให้ดูเหมือนกับการประมวลผลงานหลาย ๆ อย่างได้ในเวลาเดียวกัน (Multitasking)

- การเข้าคิวเพื่อรอผลลัพธ์จากเครื่องพิมพ์