队列----数据结构

news/2024/4/29 5:50:50/文章来源:https://blog.csdn.net/T2697142573/article/details/129713927

在这里插入图片描述

队列

🔆队列的概念
🔆队列的结构
🔆队列的实现
🔆设计循环队列
- 🔆循环队列的结构
- 🔆循环队列的实现
🔆结语

🔆队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

🔆队列的结构

在这里插入图片描述

🔆队列的实现

链式队列gitt代码链接

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

在这里插入图片描述

🔆设计循环队列

🔆循环队列的结构

我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

在这里插入图片描述

通常空出来一个节点，不用来存放数据，用于判断队列的空和满。

🔆循环队列的实现

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>typedef struct {int* a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));cq->a = (int*)malloc(sizeof(int) * (k + 1));cq->front = cq->rear = 0;cq->k = k;return cq;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);return (obj->front == obj->rear);
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);return ((obj->rear + 1) % (obj->k + 1) == (obj->front));
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if (myCircularQueueIsFull(obj)) {return false;}obj->a[obj->rear++] = value;obj->rear %= (obj->k + 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)) {return false;}obj->front++;obj->front %= (obj->k + 1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)) {return -1;}else {return obj->a[obj->front];}
}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if (myCircularQueueIsEmpty(obj)) {return -1;}else {return obj->a[((obj->rear) + (obj->k)) % ((obj->k) + 1)];}
}void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj->a);obj->a = NULL;free(obj);
}