Queue

Queue (แถว) เป็นโคงสร้างข้อมูลแบบ linear list ซึ่งข้อมูลจะถูกเพิ่มเข้าทางด้านท้ายของแถว (เรียกว่า rear) และจะลบข้อมูลออกจากด้านหัวแถว (เรียกว่า front) มีชื่อเรียกเรีกกระบวนการนี้ว่า first in – first out (FIFO)

1. Queue Operations
Queue มีคำสังพื้นฐานอยู่ 2 คำสั่งคือ

• ใส่ข้อมูลลงใน queue ทางด้านท้ายแถว (enqueue)
• ลบข้อมูลออกจาก queue ทางด้านหัวแถว (dequeue)

Enqueue
เป็นคำสั่งใส่ข้อมูลลงใน queue หลังจากใส่ข้อมูลลงใน queue แล้วข้อมูลตัวใหม่นี้จะไปอยู่ท้ายแถว (rear) ถ้าไม่มีที่สำหรับข้อมูลใหม่แล้วจะเรียกว่า queue อยู่ในสถานะ overflow

Enqueue inserts an element at the rear of the queue.

Dequeue
เป็นคำสั่งลบข้อมูลออกจาก queue โดยข้อมูลที่อยู่ด้านหัวแถวจะถูก return ไปยังผู้ใช้และถูกลบออกจาก queue

Dequeue deletes an element at the front of the queue.

2. Queue Implementation

2.1 Queue Array Implementation
สำหรับการ implement queue array นั้นจะเขียนโค้ดฟังก์ชัน enqueue และ dequeue ในรูปแบบของภาษา C ก่อนอื่นเเรามาดูการประกาศ header ของฟังก์ชันพร้อมทั้งทำความเข้าใจกับ parameter ของฟังก์ชันทั้งสองกันครับ

//Prototype Declarations
void enqueue (int queue[], int* front, int* rear, int maxElement, int data);
void dequeue (int queue[], int* front, int* rear, int maxElement, int* data);

เรามาทำความรู้จัก parameter แต่ละตัวกันนะครับว่ามีอะไรบ้าง
queue เป็น array 1 มิติ แทน queue


front เป็นตัวระบุตำแหน่งหัวแถว


rear เป็นตัวระบุตำแหน่งท้ายแถว


maxElement เป็นจำนวนสมาชิกของตัวแปร queue


data เป็นข้อมูล


*สำหรับ queue ที่ว่างเราจะกำหนด front = -1, rear = -1

หลังจากที่เราทราบ parameter ของทั้งสองฟังก์ชัน ต่อมาเรามาดูการนิยามฟังก์ชันทั้งสองกันครับ

Program 2.1-1 Enqueue

/*============ enqueue ================
    This algorithm inserts data into a queue.
    Pre    queue has been created
    Post     data have been inserted
*/
void enqueue (int queue[], int* front, int* rear, int maxElement, int data)
{
    if(*rear <= maxElement - 1)
    {
        *rear = *rear + 1;     //Increment rear.
        queue[*rear] = data;    //Insert element.
        if(*front == -1)    
            *front = 0;        //First element.
    }
    else
        printf("\nQueue overflow\n");

    return ;
}// EnQueue

Program 2.1-1 Analysis


ในบรรทัดที่ 8 เราตรวจสอบว่า queue มีที่ว่างสำหรับใส่ข้อมูลใหม่หรือไม่ ถ้าไม่แสดงว่า queue เต็มหรือ overflow แต่ถ้ายังมีที่ว่าง เราจะชยับ rear ไปอีก 1 ตำแหน่งแล้ว insert ข้อมูลลงใน queue ต่อมาเรามาดูบรรทัดที่ 12 – 13 กันครับถ้า queue นี้ถูก insert ข้อมูลเป็นครั้งแรกเราจะต้องเปลี่ยน front จาก –1 เป็น 0 เพื่อบอกให้รู้ว่า queue นี้ไม่ใช่ queue ว่าง