คิว (QUEUE)

 

            คิวเป็นลิสต์ของอิลิเมนท์ที่เก็บอย่างต่อเนื่องกัน  ซึ่งการลบจะทำได้ที่ปลายด้านหนึ่ง  ซึ่งเรียกว่าส่วนหน้า (FRONT)  ข้อมูลที่ใส่เข้ามาในคิวจะเข้ามาอีกปลายข้างหนึ่งที่เรียกว่าส่วนท้าย (END)

            คิวอาจเรียกว่าเป็นส่วนลิสต์แบบเข้าก่อนออกก่อน (FIFO)  เนื่องจากข้อมูลที่เข้ามาก่อนจะถูกนำออกไปก่อนตามลำดับก่อนหลัง  ซึ่งแตกต่างกับสแตกที่เป็นแบบเข้าก่อนออกหลัง

            คิวเป็นโครงสร้างข้อมูลลิสท์ของอิลิเมนท์ที่ทำการเพิ่มข้อมูลเข้า  ที่ปลายข้างหนึ่งที่เรียกว่า REAR  และทำการนำข้อมูลออกที่ปลายข้างหนึ่งที่เรียกว่า FRONT  คิวมีคุณสมบัติเป็น ไฟโฟลิสต์ (FIFO List)  คือสมาชิกตัวแรก  และ REAR  ชี้สมาชิกสุดท้ายของคิว

 

เข้า

 

ออก

 
A

B

C

 

 

FRONT=1

 

REAR=3

 

 

 


รูปที่  1

 

คิวว่าง

                คิวว่าง  คือ  คิวที่ไม่มีข้อมูลบรรจุอยู่เลย  นั่นคือ

                FRONT := NULL และ REAR := NULL

 

โอเปอร์เรชันในคิว

            โครงสร้างข้อมูลคิวมีโอเปอร์เรชัน  พื้นฐานเช่นเดียวกับลิสต์อื่น ๆ  คือมีการเพิ่มข้อมูล (insertion) เข้าคิว  และมีการดึงข้อมูล (deletion) จากคิว  แต่การกระทำการนี้มีขั้นตอนที่ซับซ้อนการลิสต์และสแตก  เนื่องจากต้องจัดการกับตัวชี้  FRONT และ REAR ให้ถูกต้อง  ดังนั้นจึงขอแสดงหน้าตาและค่าของ FRONT และ REAR  ในแต่ละกรณีเสียก่อน  โดยสมมติว่าคิวนี้สามารถบรรจุสมาชิกได้  3  สมาชิก

 

                1. เมื่อคิวว่าง (Empty Queue)

           0                     1                    2                      3

 

 

 

                                                                FRONT=0  REAR=0

 

                2. เมื่อคิวมีสมาชิกเดียว

 

 


FRONT   REAR                                            FRONT   REAR                                                 FRONT   REAR

 

3.เมื่อคิวเต็ม (Full Queue)

 

 


     FRONT                      REAR                            FRONT      REAR                                      FRONT   REAR

 

การเพิ่มข้อมูลเข้าไปในคิว  มีขั้นตอน ดังนี้

                                1.  ตรวจสอบว่าคิวเต็มหรือไม่ ?

-          ถ้าคิวเต็ม  ให้บอกว่า  ‘Queue Overflow’

-          ออกจากกระบวนคำสั่งนี้

                                2.  เลื่อนตัวชี้ที่ท้ายคิวไปอีก 1 ตำแหน่ง

                                3.  นำข้อมูลเข้าไปเก็บในคิว

                                4.  ตรวจสอบดูว่า  ข้อมูลที่นำเข้าไปเก็บเป็นข้อมูลตัวสุดท้ายในคิวหรือไม่ ?

-          ถ้าใช่  ก็ให้เลื่อนตัวชี้ที่หัวคิวไปชี้ที่ 1

-          ออกจากกระบวนคำสั่งนี้

 

                ถ้ากำหนดให้ …

-          QUEUE (1..n)  เป็นคิวของอักขระ

-          N  เป็นตัวชี้ในคิว

-          FRONT  เป็นตัวชี้ที่หัวคิว

-          REAR  เป็นตัวชี้ที่ท้ายคิว

-          ITEM  เป็นอักขระที่จะนำไปเก็บในคิวหรือลบออกจากคิว

                การประกาศตัวแปรในภาษาปาสคาล …

 

 

 

Type  Que = array (1..n) of Char;

           Index = Integer;

Var  QUEUE : Que;

         N, FRONT, REAR : Index;

         ITEM : Char;

           

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

                       

Procedure : QINSERT (QUEUE, N, FRONT, REAR, ITEM)

                    {This procedure inserts an element ITEM into a queue.}

                                1. if  REAR = N, then : Print : Queue Overflow, and return

                                    {Queue already filled ?}

                                2. Set REAR := REAR + 1

                                3. Set QUEUE(REAR) := ITEM

                                    {This insert new element.}

                                4. if  FRONT = 0, then : Set FRONT = 1

                            5. Return

 

                การลบข้อมูลออกจากคิว  มีขั้นตอน ดังนี้

                                1.  ตรวจสอบว่าคิวว่างหรือไม่ ?

-          ถ้าคิวว่าง ให้บอกว่า ‘Queue Underflow’

-          ออกจากกระบวนคำสั่งนี้

                                2.  นำข้อมูลที่หัวคิวออก

                                3.  ตรวจสอบดูว่า ข้อมูลที่ลบออกนั้นเป็นข้อมูลตัวสุดท้ายในคิวหรือไม่ ?

-          ถ้าใช่  ให้ตัวชี้ที่หัวคิวและท้ายคิวไปชี้ที่ 0

-          ออกจากกระบวนคำสั่งนี้

                                4.  เลื่อนตัวชี้ที่หัวคิวไปอีก 1 ตำแหน่ง

 

                จากขั้นตอนของการลบข้อมูลออกจากคิว  สามารถนำมาเขียนเป็นกระบวนคำสั่งได้  ดังนี้

 

Procedure : QDELETE (QUEUE, FRONT, REAR, ITEM)

                         {This procedure deletes an element from a queue and

                       assigns it to the variable ITEM.}

                     1. if  FRONT = 0, then : Print : Queue Underflow, and return

                                {Queue already empty ?}

                     2. Set ITEM := QUEUE(FRONT)

                     3. if  FRONT = REAR, then : Set FRONT = 0 and REAR = 0

                                {Queue has only one element to start.}

                                Else : Set FRONT := FRONT + 1

                     4. Return

 

                ถ้าให้ insert (Q,X) เป็นฟังก์ชันทำการเพิ่มข้อมูล X เข้าคิว Q และ delete (Q) เป็นฟังก์ชันนำข้อมูลจากคิว Q ต่อไปนี้เป็นการแสดงการเพิ่มข้อมูลเข้าและนำออกจากคิวเริ่มต้นจากเมื่อคิวว่างมี FRONT และ REAR ชี้จุดเริ่มต้นของเนื้อที่ที่จบไว้คือศูนย์  และให้คิวนี้จองเนื้อที่ไว้ทั้งหมด (N) เท่ากับ  3

1. .      0              1               2              3     

 


      FRONT = 0  REAR = 0

 

2. insert (Q,A)

 

 

A

 

 

 
             0            1              2               3

 

 


    FRONT = 1   REAR = 1

 

 

 

3. insert (Q,B)

 

 

A

 

B

 
              0           1              2               3

 

 


              FRONT = 1  REAR = 2

 

4. insert (Q,C)

C

 

B

 

A

 
             0            1               2              3

 

 


             FRONT = 1                 REAR = 3

                หลังจากนี้จะเพิ่มข้อมูลเข้าคิว  อีกไม่ได้  เนื่องจากคิวเต็มคือ REAR = 3

 

5. delete (Q)

          0            1               2              3

C

 

 

 

B

 

 

         

                           FRONT = 2   REAR = 3

 

6. delete (Q)

        0               1              2               3

 


                 

                                         FRONT = REAR = 3

 

7. delete (Q)

        0              1               2              3

 

 

 

 

 

 

 

     FRONT = REAR = 0

 

                หลังจากนี้จะทำ  delete (Q) อีกไม่ได้เนื่องจาก Q ว่าง  คือ FRONT = 0  พิจารณาจากขั้นตอนทั้ง 7 ข้างต้น  สรุปได้ว่า

                1.  การเพิ่มข้อมูลเข้า  ซึ่งต้องเข้าที่ REAR ของคิวก่อน  ต้องเพิ่มค่า REAR ที่เป็นตัวชี้สมาชิกสุดท้ายของคิวอีก 1 เพื่อให้ชี้เนื้อที่ถัดไป  สำหรับเตรียมข้อมูลมาใช้

                2.  การนำข้อมูลออกจากคิว  ทำที่ FRONT ของคิว  ซึ่ง FRONT ชี้สมาชิกตัวแรกของคิวอยู่แล้วดังนั้น  จึงนำข้อมูลที่ FRONT ชี้อยู่ออกได้เลย  หลังจากนั้นเปลี่ยนให้ FRONT ไปชี้สมาชิกตัวถัดไป  โดยเพิ่มค่า FRONT อีก 1

                3.  (ให้พิจารณาขั้นตอนที่  1  และ  2)  คือเมื่อเพิ่มข้อมูลเข้าคิวที่ว่างอยู่ต้องเซตค่า FRONT ที่แต่เดิมชี้ที่ศูนย์  ให้ชี้ที่  1  ด้วย  เพื่อให้ FRONT  ชี้ที่สมาชิกแรกของคิว

                4.  (ให้พิจารณาขั้นตอนที่ 6 และ 7) คือเมื่อทำการนำข้อมูลออกจากคิวขณะที่ในคิวมีสมาชิกเดียวหลังจากนำข้อมูลออกมาแล้วก็หมายความว่าคิวต้องว่างดังนั้นจึงต้องเซตค่า FRONT ให้ไปชี้ที่ 0

 

การสร้างคิว

                เราสามารถสร้างคิวโดยใช้อาเรย์เป็นตัวคิวพร้อมกันได้นั้น  ต้องใช้พอยน์เตอร์อีก 2 ตัว  ชื่อ F (front pointer) และ R (rear pointer)  โดยข้อมูลจะนำเข้าไปทาง rear และออกจากคิวทาง front ในตอนแรก  ตัวพอยน์เตอร์ F จะไปยังหัวแถว(ตัวแรก) และพอยน์เตอร์ R จะชี้ไปที่หางแถว(ตัวสุดท้าย)

 

โครงสร้างคิวซึ่งมี  12  ช่อง

 

 

6

3

2

1

9

2

4

 

 

 

                                   F                                                                                             R

 

                ในตอนแรกซึ่งคิวยังว่างเปล่าอยู่นั้น F และ R  มีค่าเท่ากับ 0 ทั้งคู่  สิ่งที่เราต้องการกระทำกับคิวคือการเข้าสู่คิว (insertion) และการออกจากคิว (deletion) ลำดับเหตุการณ์เข้าสู่คิวและออกจากคิวของคิวที่ชื่อ Q(4) ดังรูป

 

   F =R=0                        F=R=1                                    F   R                              F           R

 

 

 

 

 

 

 


5

 

 

 

 

 

5

3

 

 

 

 

5

3

2

 

      Insert  5                        Insert  3                          Insert  2                            Delete

 

         F       R                              F          R                          F           R                         F           R

 

 


3

2

 

 

 

 

3

2

8

 

 

 

3

2

8

 

 

 

3

2

8

      Insert  8                        Insert  4                           *1 Overflow                           Delete

 

                  F    R                                 F  R                  F = R =0                        

 

 

 


2

8

 

 

 

 

 

8

 

 

 

 

 

 

 

 

 

 

 

 

               Delete                       Delete                        Delete                                *2 underflow

 

*1 ข้อมูล 4 ไม่สามารถเข้าสู่คิวได้                   *2 ไม่สามารถ  delete   เพราะคิวว่าง

 

การเรียงลำดับข้อมูลในคิว

                โครงสร้างข้อมูลชนิดนี้ให้ความสำคัญต่อข้อมูลแบบ  “เข้าก่อน  ออกก่อน”  หรือ “first in first out”

                รูปแบบของโครงสร้างแบบแถวคิวจะคล้ายรูปแบบของโครงสร้างแบบ stack แต่ส่วนที่เป็นตัวชี้จะมี 2 ค่า  คือ  ส่วนที่ชี้ค่าแรกของแถวคิวและส่วนที่ชี้ค่าหลังสุดของแถวคิว  นอกจากนี้แล้วการสร้างโครงสร้างข้อมูลแบบแถวคิวนี้  จะเป็นการสร้างข้อมูลแบบ dynamic allocation เช่นเดียวกับการสร้างโครงสร้างข้อมูลแบบ stack คือจะทำการสร้างเนื้อที่เก็บข้อมูลทีละ 1 ข้อมูลเมื่อมีข้อมูลใหม่เกิดขึ้น

 

คิววงกลม (circular queue)

                คิววงกลม (circular queue)  คือ  คิวที่มีการทำงานในลักษณะที่เมื่อคิวมีข้อมูลเต็มแล้วไม่สามารถใส่ข้อมูลเข้าไปทางปลายคิวได้อีกแต่ถ้าตรวจสอบพบว่าต้นคิวว่างเนื่องจากข้อมูลที่ต้นคิวถูก

ลบออกไป  จะสามารถใส่ข้อมูลเข้าไปทางต้นคิวที่ว่างนั้นได้อีก  จึงทำให้คิวมีลักษณะวนเวียนไปไม่มีที่สิ้นสุด

                ในการสร้างคิววงกลมจะกำหนดให้ Q(1)  ตามหลัง Q(n)  ดังรูป

 

 

 

 

 

 

 


จากรูปที่  1  ในคิวมีเพียงสมาชิกเดียว  แต่ REAR ชี้เนื้อที่สุดท้ายของคิว  ในลักษณะนี้ถ้าจะทำการเพิ่มข้อมูลเข้าในคิวอีกย่อมทำไม่ได้  เนื่องจากอัลกอริทึมที่เขียนใน Insert (Q,X) ตรวจสอบว่า  ถ้า REAR มีค่าเท่ากับ N เนื้อที่ทั้งหมดที่จองไว้  ก็หมายความว่าคิวเต็ม  แม้ว่ายังมีเนื้อที่เหลือด้านหน้าก็ตามทำให้การใช้เนื้อที่ไม่เต็มที่  ทางแก้ไขก็ให้เนื้อที่ส่วนหน้าถูกใช้บรรจุข้อมูลได้  หรือถือเสมือนว่าคิวนี้เป็นวงกลม  รูปที่  2  แสดงคิวเมื่อเพิ่มข้อมูลเข้าไปอีกหนึ่งข้อมูล REAR เปลี่ยนไปชี้ที่ 1  เพื่อแสดงตำแหน่งสมาชิกสุดท้ายของคิว

 

 
                                                                                                      N

 

 


                                                                           FRONT   REAR

                                                                  รูปที่  1

 

 

 


                                       REAR                                          FRONT

                                                                รูปที่ 2

 

                จากรูปที่  2  เซอร์คิวลาคิวนี้สามารถเพิ่มข้อมูลเข้าได้เรื่อย ๆ จนเป็นดังรูปที่ 3 จึงไม่สามารถเพิ่มได้อีก  ซึ่งหมายความว่าคิวเต็ม

                                          1        2             ….…….                       N-1     N

 


                                                                                           

                                                                                           REAR   FRONT                

                                                         รูปที่  3  

                                                             


                อัลกอริทึม             InsertcirQ (Q,K)  ทำการเพิ่มข้อมูล X ในเซอร์คิวลาคิวเป็นดังนี้

                                                Procedure insertcirQ (Var Q : Queue; X : itemtype);

                                                BEGIN

                                                                IF Rear = N          THEN Rear := 1

                                                                ELSE Rear := Rear + 1;

                                                                IF Front = Rear  THEN WRITELN(‘FULL QUEUE’)

                                                                ELSE Q[Rear] := X;

                                                                IF Front = 0  THEN Front := 1;

                                                END.

 

           

ในกรณีที่นำข้อมูลออกจากเซอร์คิวลาคิว  จุดที่ต้องพิจารณาคือขณะที่ FRONT ชี้ที่ N (เนื้อที่สุดท้ายของคิว)  โดยที่คิวมีสมาชิกมากกว่าหนึ่ง  หรือ FRONT กับ REAR ไม่ได้ชี้ตำแหน่งเดียวกัน  ดังแสดงในรูปที่ 4

                                    

                                            0        1         2        3                                        N

 

 

 

 

 

 
                                           

 


                                                               REAR                               FRONT

                                                                              รูปที่  4

 

ในกรณีนี้หลังจากนำข้อมูลที่ FRONT ออกต้องเซตค่า FRONT ให้ชี้ที่สมาชิกตัวแรกของคิว คือ FRONT ชี้ที่ตำแหน่งที่ 1  และถ้าก่อนนำข้อมูลออกในคิวมีสมาชิกเพียงสมาชิกเดียว  ดังรูปที่ 5  หลังจากนำข้อมูลออกไปแล้ว  ให้เซตค่า FRONT และ REAR ให้เป็นศูนย์เพื่อแสดงว่าคิวว่าง

                                                           1                                                            N

 

 

 


                                              FRONT    REAR

รูปที่  5

 

           

อัลกอริทึม             DelcirQ(Q,X)  ทำการนำข้อมูลออกจากเซอร์คิวลาคิว  เป็นดังนี้

Procedure delcirQ (var Q : queue ; var X : itemtype);

                                                BEGIN                                 

                                                                IF front = 0  THEN WRITELN(‘EMPTY QUEUE’)

                                                                ELSE  BEGIN

                                                                                X := Q[front];

                                                                                IF front = rear  THEN

                                                                                (*case figure 5.7 or 5.11*)

                                                                                                BEGIN

                                                                                                                Front := 0;

                                                                                                                Rear := 0;

                                                                                                END;

                                                                                ELSE

                                                                                                IF front = N

                                                                                                                THEN front := 1 (*case of figre 5.10*)

                                                                                                ELSE front := front + 1;

                                                                                END;

                                                END.

 

 

เดค(DEQUE)

                เดค (Deque : Double-End Queue)  เป็นโครงสร้างข้อมูลคิวที่สามารถทำการเพิ่มข้อมูลหรือนำข้อมูลออกที่ปลายทั้งสองของคิว  คือปลายไม่ว่าเป็นด้าน  FRONT  หรือ  REAR  สามารถเพิ่มหรือนำข้อมูลออกได้  เดคมาจาก  double – ended queue

                การเก็บข้อมูลของเดคในคอมพิวเตอร์ทำได้หลายแบบ  หากไม่มีการกำหนดเป็นอย่างอื่น  เดคจะเก็บอยู่ในอาเรย์แบบวงกลม  DEQUE  ที่มีตัวชี้  LEFT  และ  RIGHT  ชี้ปลายทั้งสองของเดค  สมมติการเก็บข้อมูลเริ่มจากซ้ายไปขวา  และ DEQUE [1]  ต่อจาก DEQUE [N]  รูปด้านล่างนี้  เป็นรูปแสดงเดค  2  เดคที่มีข้อมูล  4  อิลิเมนท์  เก็บอยู่ในอาเรย์ขนาด  N = 8  ช่อง  เดคที่ไม่มีข้อมูลจะแสดงด้วย  LEFT  =  NULL

                เดคแบ่งออกเป็น  2  แบบ  คือ 

-       แบบจำกัดทางเข้า (Input – restricted Deque)  แบบนี้จะยอมให้เพิ่มข้อมูลเข้าได้ทางด้านใดด้านหนึ่งเพียงด้านเดียวเท่านั้น  แต่ให้ลบข้อมูลออกได้ทั้งสองทาง

-       แบบจำกัดทางออก (Output – restricted Deque)  แบบนี้จะยอมให้ลบข้อมูลออกทางด้านใดด้านหนึ่งเพียงด้านเดียวเท่านั้น  แต่ให้เพิ่มข้อมูลเข้าได้ทั้งสองทาง

 

                DEQUE

 

                       LEFT : 4  RIGHT : 7

 

 

 

AAA

BBB

CCC

DDD

 

                           1             2            3            4            5           6              7               8

 

                       LEFT : 7  RIGHT : 2

YYY

ZZZ

 

 

 

 

WWW

XXX

                           1             2            3            4            5           6              7               8

 

 

สรุป

                คิวเป็นลิสต์ที่มีคุณสมบัติเป็นไฟโฟลิสต์  (FIFO  Lists)  ซึ่งเป็นโครงสร้างข้อมูลที่มนุษย์คุ้นเคยมากกว่าโครงสร้างอื่น  คิวมีความสำคัญไม่น้อยทีเดียวในระบบที่เกี่ยวข้องกับการบริการให้กับสิ่งที่อยู่ในคิว  เช่นในระบบคอมพิวเตอร์ที่เป็น  Multiprogramming  คิวของงานของยูสเซอร์ในระบบที่รอซีพียู  คิวของงานพิมพ์ที่รอเครื่องพิมพ์  ในระบบธุระกิจเช่นคิวของลูกค้าธนาคารที่รอบริการ  ถ้าพิจารณาด้านความต้องการที่จะให้ระบบคอมพิวเตอร์ใช้ทรัพยากรที่มีอยู่ให้มีประสิทธิภาพที่สุด  จะมีนโยบายในการเลือกงานที่รอในคิว เช่น  อาจมีนโยบายเลือกเอางานที่ทำเสร็จเร็วที่สุดก่อน  หรือเลือกงานที่ใช้อุปกรณ์ที่ต่างไปจากงานที่ทำอยู่ เช่น  เลือกทำงาน  I/O Bound  คู่กับงาน  CPU Bound เป็นต้น  ในส่วนการบริการในธุรกิจความต้องการคือการลงทุนในหน่วยบริการให้เหมาะสมกับคิวมากที่สุด  เช่น ต้องการให้มีจำนวนหน่วยที่บริการที่น้อยที่สุด (เพื่อต้นทุนต่ำสุด)  ที่สามารถบริการได้ในเวลาที่ลูกค้าพอใจ  สิ่งที่เกี่ยวข้องกับการพิจารณาคืออัตราที่ลูกค้าเข้ามาในคิว  และความสามารถของการให้บริการของแต่ละหน่วยบริการ