Google         youtube            psv            สพม.11

คิววงกลม

แทนที่จะใช้คิวเป็นเชิงเส้นแบบแนวตรงดังที่ผ่านมา ก็มาใช้เป็นคิววงกลม (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];

            intmaxSize;

            int front;

            int rear;

};

typedefstruct queue Queue;

typedef Queue* priorityQueues;

priorityQueuescreatePriorityQueue(){

            priorityQueuesnewQueue = malloc(sizeof(Queue));

            newQueue->maxSize = 50;

            newQueue->front = 0;

            newQueue->rear = -1;

            return newQueue;

}

intisEmpty(priorityQueue q){

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

                        return TRUE;

 

            return FALSE;

}

void Insert(char val,intpr,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(){

            priorityQueuespque;

            char choice, job;

            intpriority,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) มาช่วย จะเห็นว่าการลบงานออกจากคิวยังคงเหมือนเดิม

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s