โครงสร้างข้อมูลคือการเก็บรวบรวมข้อมูลที่จัดโครงสร้างในลักษณะที่มีโครงสร้าง แบ่งออกเป็นสองประเภทตามที่อธิบายไว้ด้านล่าง −
-
โครงสร้างข้อมูลเชิงเส้น − ข้อมูลถูกจัดระเบียบในลักษณะเชิงเส้น ตัวอย่างเช่น อาร์เรย์ โครงสร้าง สแตก คิว รายการเชื่อมโยง
-
โครงสร้างข้อมูลไม่เชิงเส้น - ข้อมูลถูกจัดระเบียบตามลำดับชั้น เช่น ต้นไม้ กราฟ ชุด ตาราง
คิว
เป็นโครงสร้างข้อมูลเชิงเส้นที่มีการแทรกที่ส่วนท้ายและการลบเสร็จสิ้นที่ส่วนหน้า
ลำดับของคิวคือ FIFO – เข้าก่อนออกก่อน
ปฏิบัติการ
- Insert – การแทรกองค์ประกอบลงในคิว
- Delete – การลบองค์ประกอบออกจากคิว
เงื่อนไข
-
คิวโอเวอร์โฟลว์ - พยายามแทรกองค์ประกอบลงในคิวเต็ม
-
คิวภายใต้โฟลว์ - พยายามลบองค์ประกอบออกจากคิวที่ว่างเปล่า
อัลกอริทึม
รับด้านล่างเป็นอัลกอริทึมสำหรับการแทรก ( ) −
- ตรวจสอบคิวล้น
if (r==n)
printf ("Queue overflow") - มิฉะนั้น ให้แทรกองค์ประกอบในคิว
q[r] = item r++
รับด้านล่างเป็นอัลกอริทึมสำหรับ การลบ ( ) −
- ตรวจสอบคิวภายใต้โฟลว์
if (f==r)
printf ("Queue under flow") - มิฉะนั้น ให้ลบองค์ประกอบออกจากคิว
item = q[f] f++
รับด้านล่างเป็นอัลกอริทึมสำหรับ การแสดงผล ( ) −
- ตรวจสอบว่าคิวว่างหรือไม่
if (f==r)
printf("Queue is empty") - มิฉะนั้น ให้พิมพ์องค์ประกอบทั้งหมดจาก 'f' ถึง 'r'
for(i=f; i<r; i++)
printf ("%d", q[i]); โปรแกรม
ต่อไปนี้เป็นโปรแกรม C สำหรับการใช้งานคิวโดยใช้อาร์เรย์ -
#include<limits.h>
#include<stdio.h>
#include <stdlib.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;
}
//if queue is full
int isFull(struct Queue* queue){
return (queue->size == queue->capacity);
}
// Queue is empty
int isEmpty(struct Queue* queue){
return (queue->size == 0);
}
void Equeue(struct Queue* queue, int item){
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)
% queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf("%d entered into queue\n", item);
}
int Dqueue(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
int main(){
struct Queue* queue = createQueue(1000);
Equeue(queue, 100);
Equeue(queue, 200);
Equeue(queue, 300);
Equeue(queue, 400);
printf("%d is deleted element from queue\n\n",
Dqueue(queue));
printf("1st item in queue is %d\n", front(queue));
printf("last item in queue %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 1st item in queue is 200 last item in queue 400
