Cấu trúc dữ liệu là tập hợp dữ liệu được tổ chức theo một cách có cấu trúc. Nó được chia thành hai loại như được giải thích bên dưới -
-
Cấu trúc dữ liệu tuyến tính - Dữ liệu được tổ chức theo kiểu tuyến tính. Ví dụ:mảng, cấu trúc, ngăn xếp, hàng đợi, danh sách được liên kết.
-
Cấu trúc dữ liệu phi tuyến - Dữ liệu được tổ chức một cách phân cấp. Ví dụ:Cây, đồ thị, tập hợp, bảng.
Hàng đợi
Đây là một cấu trúc dữ liệu tuyến tính, trong đó việc chèn được thực hiện ở phía sau và việc xóa được thực hiện ở phía trước.
Thứ tự hàng đợi là FIFO - Nhập trước ra trước
Hoạt động
- Chèn - Chèn một phần tử vào hàng đợi.
- Xóa - Xóa một phần tử khỏi hàng đợi.
Điều kiện
-
Xếp hàng qua luồng - Cố gắng chèn một phần tử vào một hàng đợi đầy đủ.
-
Hàng đợi trong luồng - Đang cố gắng xóa một phần tử khỏi hàng đợi trống.
Thuật toán
Dưới đây là một thuật toán cho insert () -
- Kiểm tra lỗi tràn hàng đợi.
if (r==n)
printf ("Queue overflow") - Nếu không, hãy chèn một phần tử vào hàng đợi.
q[r] = item r++
Dưới đây là một thuật toán cho xóa () -
- Kiểm tra hàng đợi theo quy trình.
if (f==r)
printf ("Queue under flow") - Nếu không, hãy xóa một phần tử khỏi hàng đợi.
item = q[f] f++
Dưới đây là một thuật toán cho display () -
- Kiểm tra xem hàng đợi có trống hay không.
if (f==r)
printf("Queue is empty") - Nếu không, hãy in tất cả các phần tử từ ‘f’ đến ‘r’.
for(i=f; i<r; i++)
printf ("%d", q[i]); Chương trình
Sau đây là chương trình C để thực hiện hàng đợi bằng cách sử dụng mảng -
#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;
} Đầu ra
Khi chương trình trên được thực thi, nó tạo ra kết quả sau -
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