โครงสร้างข้อมูล Queue แบบเส้นตรง (Linear Queue) ในภาษา C

โครงสร้างข้อมูล (Data Structure) คือการจัดเก็บข้อมูลอย่างเป็นระบบ แบ่งเป็น 2 ประเภทหลัก:

• Linear Data Structure - จัดเรียงแบบเส้นตรง เช่น Array, Stack, Queue, Linked List
• Non-linear Data Structure - จัดเรียงแบบลำดับชั้น เช่น Tree, Graph

Queue (คิว) คืออะไร?

Queue เป็น Linear Data Structure ที่:

• การเพิ่มข้อมูล (Insert/Enqueue) ทำที่ปลายหลัง (Rear)
• การลบข้อมูล (Delete/Dequeue) ทำที่ปลายหน้า (Front)
• ทำงานแบบ FIFO (First In First Out) - เข้าก่อน ออกก่อน

การดำเนินการหลัก

• Enqueue (Insert) - เพิ่มข้อมูลเข้า Queue
• Dequeue (Delete) - นำข้อมูลออกจาก Queue

เงื่อนไขข้อผิดพลาด

• Queue Overflow - พยายามเพิ่มข้อมูลใน Queue ที่เต็ม
• Queue Underflow - พยายามลบข้อมูลจาก Queue ที่ว่าง

อัลกอริทึม

Enqueue (Insertion)

if (rear == MAX_SIZE - 1) printf("Queue overflow");
else { q[rear] = item; rear++; }

Dequeue (Deletion)

if (front == rear) printf("Queue underflow");
else { item = q[front]; front++; }

Display

if (front == rear) printf("Queue is empty");
else { for(i=front; i<rear; i++) printf("%d ", q[i]); }

โปรแกรมตัวอย่าง: Queue แบบ Circular Array

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct Queue {
    int front, rear, size;
    unsigned capacity;
    int *array;
};

struct Queue* createQueue(unsigned capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

int isFull(struct Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

void enqueue(struct Queue* queue, int item) {
    if (isFull(queue)) return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size++;
    printf("%d entered into queue\n", item);
}

int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    return item;
}

int front(struct Queue* queue) {
    if (isEmpty(queue)) return INT_MIN;
    return queue->array[queue->front];
}

int rear(struct Queue* queue) {
    if (isEmpty(queue)) return INT_MIN;
    return queue->array[queue->rear];
}

int main() {
    struct Queue* queue = createQueue(1000);
    enqueue(queue, 100);
    enqueue(queue, 200);
    enqueue(queue, 300);
    enqueue(queue, 400);
    printf("%d is deleted element from queue\n", dequeue(queue));
    printf("Front item is %d\n", front(queue));
    printf("Rear item is %d\n", rear(queue));
    return 0;
}

ผลลัพธ์

100 entered into queue
200 entered into queue
300 entered into queue
400 entered into queue
100 is deleted element from queue
Front item is 200
Rear item is 400