บทที่ 5

 โครงสร้างข้อมูลคิว

วัตถุประสงค์เชิงพฤติกรรม(Behavioral Objectives)
หลังจอกศึกษาจบบทเรียนนี้แล้ว นักศึกษาจะมีความสามารถดังนี้
(After studying this chapter, you will be able to)
                        1.ศึกษาการปฏิบัติการของคิว
                        2.แสดงตัวอย่างคิววงกลม
                        3.ยกตัวอย่างคิวลำดับความสำคัญ
                        4.แสดงตัวอย่างการใช้คิวลำดับความสำคัญ
                        5.จัดบอร์ดเชิงปฏิบัติการ “โครงสร้างข้อมูลคิว”
                        6.สนทนาเชิงปฏิบัติการ “ตัวอย่างการใช้คิวลำดับความสำคัญ”
                        7.อธิบายคำศัพท์ได้ 8 คำ


บทที่ 5
โครงสร้างข้อมูลคิว
               
คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับสแตก (Stack) และมีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) เช่นกัน มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่าส่วนหน้า (Front) ซึ่งกำหนดคิวเป็นรูปแบบดังนี้
    Q = [Q1, Q2, . . .  , QT]
                โดย Front (Q) คือ Q1 และ Rear (Q) คือ QT มีจำนานสมาชิกในคิวเท่ากับ T ดังในรูปที่ 5.1 โดยลักษณะมีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ด้านท้ายอยู่ด้านขวา และอาจกลับด้านกันก็ได้ให้ตัวชี้ส่วนหน้าอยู่ด้านขวาและตัวชี้ส่วนท้ายอยู่ด้านซ้าย
              
 

 

 

 

 

 


                       Front                                                                                                 Rear
รูปที่ 5.1 ตัวอย่างลักษณะของคิวที่มีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ส่วนท้ายอยู่ด้านขวา

                สมาชิก Q1 จะเข้ามาก่อนสมาชิก QJ สำหรับ I < J   และ QI ซึ่งอยู่ในคิวนานที่สุดและถูกลบออกจากคิวก่อนสมาชิกที่เข้ามาหลัง
                ลักษณะของคิวถูกนำมาใช้แก้ไขปัญหาต่างๆในแอปพลิเคชั่นต่างๆ เช่น จำลอง (Simulation) การทำงานของระบบจริงในกิจกรรมแบบเข้าก่อนออกก่อน เช่น การเข้าแถวเพื่อนซื้อของหรือชำระเงินเพื่อตรวจสอบการให้บริการเพียงพอหรือไม่ การนำคิวไปใช้ในการสำรวจพิจารณา (Observation) ตามปริมาณรถติดเพื่อควบคุมไฟจราจรตามทางแยก การนำหลักการของคิว (Queuing Theory) มาใช้ เช่น การส่งข้อมูลข่าวสารในเครือข่าย การส่งแฟ้มข้อมูลไปยังพริ้นเตอร์เพื่อพิมพ์งานตามลำดับคิว หรือรูปแบบการสลับตู้รถไฟบนราง ดังในรูปที่ 5.2
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


รูปที่ 5.2 ตัวอย่างการใช้คิวแก้ปัญหาการสลับตู้รถไฟบนราง
                ปัญหาต่างๆเหล่านี้สามารถแก้ไขโดยใช้โครงสร้างคิวที่มีลักษณะการทำงานในรูปแบบที่เรียกว่าเข้าก่อนออกก่อน (First-In-First-Out, FIFO) หรือเข้ามาก่อนได้บริการก่อน (First-Come-First-Served, FCFS) เมื่อค่าใหม่เข้ามาก็จะไปต่อเป็นส่วนท้ายแทนค่าเดิมที่เก็บอยู่ส่วนท้ายก่อนหน้านี้ไปเรื่อยๆ ถ้าเป็นการดึงค่าออกจากคิวก็จะนำค่าแรกสุดที่อยู่ในคิวดึงออกมาให้ก่อนสมาชิกตัวถัดไปส่วนหน้าแทน
การปฏิบัติการของคิว
                จากลักษณะของคิวจะมีการปฏิบัติการเข้ามาช่วยการทำงานและจัดการกับคิวให้มีความถูกต้อง โดยมีชุดปฏิบัติการพื้นฐาน ดังต่อไปนี้
                1.CreateQueue () ใช้สร้างคิวใหม่ขึ้นมาใช้งานและกำหนดค่าเริ่มต้นต่างๆ
                2.Insert (value, queue) ใช้เพิ่มค่าใหม่เก็บลงในคิวที่ใช้งานอยู่ และขยับตำแหน่งใหม่ให้กับส่วนท้าย
                3.Remove (queue) ใช้ดึงค่าออกจากคิวที่ใช้งานอยู่และส่งค่า value กลับมาให้และขยับไปยังตำแหน่งถัดไปให้เป็นส่วนหน้า
                4. isEmpty(stack) ใช้ตรวจสอบว่าคิวที่ใช้งานอยู่ว่างหรือไม่ ถ้าไม่มีค่าเก็บไว้เลยจะส่งค่าจริงกลับมาให้
                การนำคิวมาใช้งานเป็นไปตามลำดับดังในรูป (a) ถึง (g) มีการทำงานโดยใช้ชุดปฏิบัติการดังนี้
(a) เริ่มต้นสร้างคิว Qขึ้นมาทำงาน Create Queue (Q) ได้เป็นคิวว่างไม่มีสมาชิกโดยตัวชี้ส่วนหน้าและส่วนท้ายยังไม่มีค่า
 

 

 

 


                                          

                (b) นำค่า A เข้ามาเก็บเป็นตัวแรกโดยใช้ Insert (A) ได้คิว Q = [A] ตัวชี้Front = A,
 Rear =A
 

 


                                                                                                           

 

                                        Front             Rear     
                                     
                (c) นำค่า B เก็บต่อโดยใช้ Insert (B) ได้คิว Q = [A,B] ตัวชี้ Front=A, Rear =B 

B

  

 


A

 

 

  
            

 

                                                  Front                            Rear          
             
                (d) นำค่า C เก็บต่อโดยใช้ Insert (C) ได้คิว Q = [A, B, C] ตัวชี้ Front=A, Rear =C 
 

 


B

 

 

A

 

 

              

 

                                        Front                                     Rear          
                               

                 (e) ต้องการดึงค่าออกมาโดยใช้ Remove () ได้คิว Q = [ B, C] ตัวชี้ Front=B, Rear =C 

C

  

 


B

 

 

 

Front                                    Rear          
                                                                                                                           
(f) นำค่า D, E เก็บต่อโดยใช้ Insert (D) และ Insert (E) ได้คิว Q = [B, C, D, E] ตัวชี้ Front=B,

B            C

 

 

C

 

 

D

 

 

E

 

 

Rear =E               

 

 

            Front                                                        Rear          

(g) ดึงค่าออกมา 3 ค่า โดยใช้ Remove () 3 ครั้งและเก็บค่า F โดยใช้ Insert (F) ได้คิว Q = [ E, F] ตัวชี้ Front=E, Rear =F

F

  

 


E

 

 

 
                                 
 
Front                                 Rear          
              การทำงานของคิวเมื่อมีค่าใดส่งเข้ามาเก็บเป็นตัวแรกก็จะอยู่ส่วนหน้า ค่าถัดมาก็จะต่อท้ายไปเรื่อยๆ จนตัวสุดท้ายคือส่วนหลัง หากมีการดึงค่าออกมาใช้ ค่าที่อยู่ส่วนหน้าจะถูกดึงออกมาก่อน ลักษณะที่ได้จึงเป็นลำดับการใช้งานทั่วไปและเรียกว่าเข้าก่อนออกก่อน
                ในการสร้างคิวมาใช้งานโดยพื้นฐานจะใช้อาร์เรย์เก็บค่าสมาชิก มีตัวแปร Front และ Rear เป็นตัวชี้ตำแหน่งส่วนหน้าและส่วนท้ายคิว จึงเกิดความลำบากเมื่อการเก็บค่าเข้ามาจนถึงสมาชิกตัวสุดท้ายของอาร์เรย์ ทำให้เพิ่มค่าใหม่เข้ามาอีกไม่ได้ ถ้าหากมีการเพิ่มเข้ามาอีกจะเกิดลักษณะการล้นของข้อมูลในคิว (Queue Overflow) และเมื่อใดมีการดึงค่าในส่วนหน้าออกมาก็ทำให้พื้นที่ส่วนหน้าของอาร์เรย์เกิดว่างและใช้งานไม่ได้ ทำให้ต้องปรับปรุงโดยย้ายค่าที่มีอยู่ส่วนท้ายกลับไปไว้ส่วนหน้าของอาร์เรย์เพื่อนำพื้นที่ว่างกลับมาใช้งานได้ แต่เป็นค่าใช้จ่ายที่ต้องทำงานเพิ่มโดยเฉพาะคิวที่มีขนาดใหญ่ ดังในรูปที่ 5.3 เป็นตัวอย่างคิวที่ใช้อาร์เรย์ขนาดเท่ากับ 5 โดยเพิ่มค่า Insert(70),Insert(80) และ Insert(50) ตามลำดับในรูป (a) จากนั้นดึงออกมา 2 ค่าโดยใช้ Remove() 2 ครั้งได้เป็นรูป (b) และเพิ่มค่า Insert(90) Insert(60) ในรูป (c) เนื่องจากไม่สามารถเพิ่มค่าใหม่ได้อีกจึงต้องขยับค่าที่เก็บอยู่ไปทางซ้ายในรูป (d) พร้อมกับกำหนดค่าตำแหน่งใหม่ให้กับ ตัวแปร Front และ Rear
 

 

 

 


                                                                                                                                                                    (a)
 

 

 

 

 

 

 

 

 


     Front                                    Rear          
 

 

 

 


                                                                                                                           (b)

         Front          Rear          
 

 

 

 


                                                                                                                           (c)
 



         Front                                        Rear          
 

 

 

 


                                                                                                                            (d)
                         
   Front                                        Rear       
รูปที่ 5.3 เป็นตัวอย่างคิวที่ใช้อาร์เรย์ในการเก็บค่ากับปัญหาที่เกิดขึ้น
คิววงกลม
                แทนที่จะใช้คิวเป็นเชิงเส้นแบบแนวตรงดังที่ผ่านมา ก็มาใช้เป็นคิววงกลม (Circular Queue) ในลักษณะของเส้นรูปวงแหวนเพื่อแก้ไขปัญหาดังกล่าว โดยสมมุติให้อาร์เรย์เป็นวงกลมที่สมาชิกตัวแรกต่อจากสมาชิกตัวสุดท้าย เมื่อเก็บค่าถึงสมาชิกตัวสุดท้ายก็จะเก็บวนต่อไปยังสมาชิกตัวแรก ดังนั้น ในการเพิ่มค่าให้กับ Front และ Rear จะอยู่ในขอบเขตขนาดของอาร์เรย์และให้สมาชิกที่เข้ามาต่อจากตำแหน่งสุดท้ายของอาร์เรย์วนกลับไปยังตำแหน่งแรกโดยการหารเหลือเศษ (Modulo) ด้วย maxSize ดังในรูปที่ 5.4 เป็นตัวอย่างจากรูปที่ 5.3 ที่เปลี่ยนเป็นคิววงกลม ทำให้เพิ่มค่าต่อไปได้และไม่ต้องขยับถอยกลับมา

 Front     
          0                      4                      0                                             4                           0                             4
               70                                                                                                                              60
                                                               
         1   80                                    3            1                                           3              1                                  90   3
                  50                                                                 50                                                           50
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


                                        2    Rear                            Front 2 Rear                                          Front 2
                     (a)                                             (b)                                                        (c)

รูปที่ 5.4 ตัวอย่างคิววงกลมในการแก้ปัญหาที่เกิดขึ้นเมื่อใช้อาร์เรย์
                สิ่งที่ต้องพิจารณาเมื่อคิวว่างเปล่าสามารถทราบได้จาก Front กับ Rear มีค่าเท่ากัน เช่น เดียวกันเมื่อคิวเต็ม Rear จะวนกลับมาจนมีค่าเท่ากับ Front ทำให้เกิดความสับสนได้ว่าเมื่อ Front และ Rear มีค่าเท่ากันจะเป็นสถานะของคิวว่างหรือคิวเต็ม อย่างไรก็ตามก็สามารถหลีกเลี่ยงปัญหานี้ได้โดยให้สมาชิกที่อยู่ก่อนหน้าสมาชิกในตำแหน่ง Front เป็นตำแหน่งช่องว่างเสมอซึ่งทำให้ทราบว่าคิวเต็มก็ต่อเมื่อ (Rear+1) % maxSize = Front ดังในรูปที่ 5.5 อย่างไรตามทำให้จำนวนสมาชิกที่เก็บค่าได้เหลือเพียง maxSize -1

                                                                                0                        maxSize-1
                                                                     1
                                                                           .                             .
                                                                          

 

 

 

 

 

 

 

 

 


                                                                Front                                        Rear
รูปที่ 5.5 ลักษณะของคิวที่กำหนดให้สมาชิกที่อยู่ก่อนหน้า Front เป็นช่องว่างเสมอ
                ดังนั้น ชุดปฏิบัติการของคิววงกลมจึงมีการปรับปรุงการทำงานได้เป็นอัลกอริทึมดังในตารางที่ 5.1 สำหรับการเพิ่มค่าลงในคิวด้วย Insert และตารางที่ 5.2 สำหรับการดึงค่าออกจากคิวด้วย Remove ในการตรวจสอบคิวว่างยังคงใช้ isEmpty เหมือนเดิมเมื่อคิวว่างก็ต่อเมื่อค่าของ Front และ Rear เท่ากัน
 

 

 

ตารางที่ 5.1 อัลกอริทึมการเพิ่มค่าเก็บลงในคิว

1.กำหนดค่าให้กับ newRear เท่ากับ (Rear + 1) mod maxSize
2.ถ้าค่าของ newRear ไม่เท่ากับค่าของ Front ทำดังนี้
            2.1 ทำการนำค่าเก็บลงในคิวยังตำแหน่งที่ Rear + 1
            2.1 กำหนดค่าของ Rear ให้เท่ากับค่าของ newRear ไม่เช่นนั้น
                แจ้งกลับมาว่าคิวเต็ม

 

 

 

 

 

ตารางที่ 5.2 อัลกอริทึมการดึงค่าออกจากคิว

1. ถ้าคิวไม่ว่างทำดังนี้
                1.1 ทำการดึงค่าที่อยู่ในคิวยังตำแหน่งที่ Front ออกมาให้
                1.2 เพิ่มค่าให้กับ Front เท่ากับ (Front + 1) mod maxSize ไม่เช่นนั้น
                แจ้งกลับมาว่าคิวว่าง

 

 

 

 

 

คิวลำดับความสำคัญ
                คิวอาจมีการจัดลำดับความสำคัญของสมาชิกจึงมีการสร้างเป็นคิวลำดับความสำคัญ (Priority Queue) เช่น ในระบบปฏิบัติการจะให้โปรเซสที่มีความสำคัญที่สุดทำงานก่อน แต่เนื่องจากโปรเซสที่เข้ามาไม่ได้เรียงตามความสำคัญ ซึ่งการจัดลำดับมี 2 แบบ คือ ให้ความสำคัญ จากค่าน้อยไปหาค่ามาก (Ascending) และจากค่ามากไปหาค่าน้อย (Descending) โดยส่วนใหญ่ใช้ค่ามากมีความสำคัญมากกว่า ในการเพิ่มสมาชิกเข้ามาในคิวไม่จำเป็นต้องเข้ามาตามลำดับความสำคัญอาจสลับไปมาได้ แต่การนำออกมาจากคิวจะต้องตามลำดับความสำคัญ ดังนั้น ในการลบสมาชิกออกจากคิวจึงต้องมีการทำงาน 2 เรื่อง คือ ต้องหาสมาชิกที่มีความสำคัญมากที่สุด ทำให้ต้องเข้าไปเรียกใช้งานสมาชิกทุกตัว และเมื่อลบสมาชิกออกจากคิวในช่วงกลางจะต้องทำการขยับสมาชิกตัวถัดไปมาอยู่แทน
                ในการแก้ไขปัญหาทั้งสองเรื่องมีอยู่หลายวิธี เช่นกำหนดตัวแปรให้ชี้ไปยังตำแหน่งสมาชิกที่สำคัญที่สุด หลังจากที่ถูกลบออกไปก็เป็นตำแหน่งว่างทำให้ไม่ต้องขยับสมาชิกตัวอื่นเมื่อเพิ่มสมาชิกใหม่ก็เก็บไว้ตำแหน่งนี้แทน แต่มีข้อเสียก็คือต้องค้นหาสมาชิกที่สำคัญที่สุดทุกครั้งที่มีการลบเช่นเดิม การทำงานแบบนี้จะทำเมื่อมีการลบสมาชิกออกจากคิว แต่มีวิธีที่เหมาะสมกว่าคือการจัดให้สมาชิกทุกตัวเรียงในคิวตามลำดับ โดยสมาชิกในตำแหน่ง Front มีความสำคัญสูงที่สุดและลดหลั่นลงมาจนถึงตำแหน่ง Rear ที่มีความสำคัญน้อยที่สุดการทำงานจะทำเมื่อมีการเพิ่มสมาชิกใหม่เข้ามาในคิว ส่วนการลบสมาชิกในคิวไม่ต้องทำงานเพิ่มเติมดังที่ผ่านมาเพื่อหาสมาชิกที่สำคัญที่สุด เพราะสมาชิกที่ Front จะสำคัญที่สุดสามารถลบออกไปได้ทันที เมื่อใดที่มีสมาชิกใหม่เพิ่มเข้ามาจะทำการจัดเรียงตามลำดับโดยการหาตำแหน่งที่ถูกต้องให้กับสมาชิก
ตัวอย่างการใช้คิวลำดับความสำคัญ
                สมมุติให้ระบบคอมพิวเตอร์มีการรับงานเข้ามาเพื่อให้ทำงานโดยมีการกำหนดลำดับความสำคัญ (Priority) ให้แต่ละงานซึ่งมีค่าตั้งแต่ 0 ถึง 10 งานที่มีความสำคัญสูงสุดคือ 10 จะถูกเรียกให้ทำงานก่อน ถ้างานที่มีความสำคัญเท่ากัน งานที่เข้ามาก่อนจะถูกทำงานก่อน (First – Come First – Served, FCFS) โดยระบบปฏิบัติการจะใช้คิวลำดับความสำคัญเป็นตัวควบคุมงาน (Job Control Block) เมื่อเขียนเป็นโปรแกรมจะได้ดังในตารางที่ 5.3 คือโปรแกรม PrioQue.c
ตารางที่ 5.3 คือโปรแกรม PrioQue.c

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define TRUE 1

#define FALSE 0

struct queue {

            int Priority[50];

            char Item[50];

            int maxSize;

            int front;

            int rear;

};

typedef struct queue Queue;

typedef Queue* priorityQueues;

priorityQueues createPriorityQueue(){

            priorityQueues newQueue = malloc(sizeof(Queue));

            newQueue->maxSize = 50;

            newQueue->front = 0;

            newQueue->rear = -1;

            return newQueue;

}

int isEmpty(priorityQueue q){

            if (q->rear < q->front)

                        return TRUE;

            return FALSE;

}

void Insert(char val,int pr,priorityQueues q){

            int i;

            if (q->rear+1 < q->maxSize)

                        if (isEmpty(q)){

                                    q->front = 0;

                                    q->rear = 0;

                                    q->Priority[q->rear] = pr;

                                    q->Item[q->rear] = val;

                        }

                        else{

                                    q->rear++;

                                    for (i=q->rear; (i>q->front)&&(q->Priority[i-1]<pr);i--){

                                                q->Item[i]=q->Item[i-1];

                                                q->Priority[i] = q->Priority[i-1];

                                    }

                                    q->Item[i] = val;

                                    q->Priority[i] = pr;

                        }

           

  

 

 

 

 

 


               

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

else

                        printf("Queue is full !!!\n");

}

char Remove(priorityQueues q){

            char val;

            if(isEmpty(q)){

                        printf("Queue is empty !!!\n);

                        return -1;

            }

            val = q->Item[q->front];

            q->front++;

            return val;

main(){

            priorityQueues pque;

            char choice, job;

            int priority,cont =TRUE;

            pque = createPriorityQueue();

            while (cont){

                        printf("1. Add new job. | 2.Execution job. | other. Exit. : ");

                        scanf("%c",&choice); getchar();

                        switch(choice){

                                    case '1' : printf("New Job (A-Z): ");

                                                scanf("%c",&job);getchar();

                                                printf("Priority (1-10): ");

                                                scanf("%d",&priority); getchar();

                                                Insert(job,priority,pque);

                                    break;

                                    case '2' : if (! isEmpty(pque))

                                                printf("Execute job: %c\n",Remove(pque));

                                                else

                                                            printf("Empty queue\n");

                                                break;

                                    default : cont = FALSE;

                        }

            }

            free (pque);

            getch();

}

                                   

  

 

 


การสร้างคิวลำดับความสำคัญในตัวอย่างเป็นการทำงานของงานที่เข้ามาโดยขึ้นกับความสำคัญ แต่ละงานที่ชื่อกำหนดเป็นตัวอักษรตัวเดียวมีค่าได้ตั้งแต่ A ถึง Z และค่าความสำคัญมีได้ตั้งแต่ 0 น้อยที่สุดจนถึง 10 มากที่สุด การเพิ่มงานเข้ามาในคิวไม่ต้องเรียนตามความสำคัญ แต่เมื่อเก็บในคิวจะมีการจัดเรียงลำดับที่ใช้วิธีการจัดเรียงลำดับความสำคัญ แต่เมื่อเก็บในคิวจะมีการจัดเรียงลำดับที่ใช้วิธีการจัดเรียงลำดับข้อมูล (Sorting) มาช่วย จะเห็นว่าการลบงานออกจากคิวยังคงเหมือนเดิม

 

นายธีระทัศน์ เสียงอ่อน
5039011012