当前位置： 首页 > news >正文

视频网站开发是什么,wordpress适合中文主题,wordpress google字体删除,网站的运营模式文章目录 #x1f4dd;队列的概念及结构#x1f320; 队列的顺序实现#x1f309;初始化#x1f320;入队#x1f309;出队#x1f320;获取队列首元素#x1f309;获取队列尾部元素#x1f320;获取队列中有效元素个数#x1f309; 队列是否为空#x1f320;查看队列… 文章目录 队列的概念及结构 队列的顺序实现初始化入队出队获取队列首元素获取队列尾部元素获取队列中有效元素个数 队列是否为空查看队列是否为满销毁队列 测试 顺序队列的假溢出循环队列概念循环队列的初始化循环队列的入队操作 循环队列的出队操作 查看队首元素查看队尾元素查看队列是否为空查看队列是否已满 测试下循环队列 总结 队列的概念及结构 队列的概念 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头 队列特征如下: 入队(Enqueue):通过尾指针添加元素到队列尾部,即向队列中插入元素。 出队(Dequeue):通过头指针删除队列头部元素,即从队列中移除元素。 空队列:当头指针和尾指针相同时,表示队列为空。 满队列:当尾指针指向队列容量最大位置时,表示队列已满。 常用的队列结构包括数组和链表实现: 数组实现队列:使用一维数组存储元素,头指针和尾指针分别指向数组的下标位置。 链表实现队列:每个元素使用一个节点存储,头节点和尾节点通过指针链接实现队列。 队列的顺序实现 头文件Queue_order.h

define _CRT_SECURE_NO_WARNINGS 1

#include stdio.h #include stdlib.h#define MAX_SIZE 100typedef int QDataType;typedef struct Queue {QDataType data[MAX_SIZE];int front;int rear;int size;//记录队列中元素数量 }Queue;//初始化队列 void InitQueue(Queue* pq); //入队操作 void EnQueue(Queue* pq,int value); //出队 QDataType DeQueue(Queue* pq); //获取队首元素 QDataType FrontQueue(Queue* pq); //获取队尾元素 QDataType RearQueue(Queue* pq);//获取队列中有效元素个数 QDataType SizeQueue(Queue* pq); //队列是否为空 QDataType IsEmpty(Queue* pq); //队列是否为满 QDataType IsFull(Queue* pq); //销毁队列 void DestroyQueue(Queue* pq);初始化 //初始化队列 void InitQueue(Queue* pq) {pq-front -1;pq-rear -1;pq-size 0; }front和rear都指向-1,表示队列中没有数据。size为0,表示队列中没有元素。 入队 //入队 void EnQueue(Queue* pq, int value) {if (pq-front MAX_SIZE - 1){printf(队列满了入队操作失败);//检查队列是否已满,如果front指针指向的下一个位置就是MAX_SIZE-1,表示队列已满,打印错误信息并返回。return;}if (pq-front -1){//如果front为-1,表示队列为空,将front指针置0。pq-front 0;}pq-rear;//如果front为-1pq-data[pq-rear] value;//表示队列为空pq-size;//加完了别忘了size }出队 //出队 QDataType DeQueue(Queue* pq) {if (-1 IsEmpty){printf(队列为空);return -1;//返回一个特定的值表示队列为空}int value pq-data[pq-front];pq-front;pq-size–;return value; }检查满是为了防止入队越界,front为-1时,表示队列为空,需要将front置0,rear后移一位指向新的元素位置将元素值写入data数组size计数增加。 获取队列首元素 //获取队首元素 QDataType FrontQueue(Queue* pq) {if (-1 IsEmpty){printf(队列为空);return -1;//返回一个特定的值表示队列为空}return pq-data[pq-front]; }获取队列尾部元素 //获取队列尾部元素 QDataType RearQueue(Queue* pq) {if (0 IsEmpty){printf(队列为空);return -1;//返回一个特定的值表示队列为空}return pq-data[pq-rear]; }获取队列中有效元素个数 //获取队列中有效元素个数 QDataType SizeQueue(Queue* pq) {return pq-size; }队列是否为空 //队列是否为空 QDataType IsEmpty(Queue* pq) {if (pq-front -1 || (pq-front pq-rear)){//队列为空return -1;}else{//队列不为空return 1;}}注意在队列中如果 front 指针大于 rear 指针表示队列为空。这是因为 front 指针指向队列的第一个元素而 rear 指针指向队列的最后一个元素。如果 front 指针大于 rear 指针意味着队列中没有元素或者已经出队了所有的元素。 考虑一个队列中有一个元素的情况。初始时 front 和 rear 都指向该元素而当该元素出队时front 指针会被移动到下一个位置这时 front 指针就比 rear 指针大表示队列已经为空。 查看队列是否为满 //查看队列是否为满 QDataType IsFull(Queue* pq) {return (pq-rear MAX_SIZE - 1); }销毁队列 //销毁队列 void DestroyQueue(Queue* pq) {InitQueue(pq);//重新初始化队列清空元素并释放内存 }测试 源文件Test.c

define _CRT_SECURE_NO_WARNINGS 1

#includeQueue_order.hint main() {Queue Pq;InitQueue(Pq);EnQueue(Pq, 10);EnQueue(Pq, 20);EnQueue(Pq, 30);printf(Front element: %d\n, FrontQueue(Pq));printf(Rear element: %d\n, RearQueue(Pq));printf(Front element: %d\n, SizeQueue(Pq));printf(Front element: %d\n, FrontQueue(Pq));printf(Dequeued element: %d\n, DeQueue(Pq));printf(Dequeued element: %d\n, DeQueue(Pq));printf(Dequeued element: %d\n, DeQueue(Pq));printf(Dequeued element: %d\n, DeQueue(Pq)); // 尝试从空队列中出队printf(Queue size: %d\n, SizeQueue(Pq));printf(Is queue empty? %s\n, IsEmpty(Pq) ? Yes : No); }顺序队列的假溢出 顺序队列的假溢出指的是队列在结构上没有真正满溢但是在逻辑上已经无法再插入新元素了。 在队尾指针已经指向数组的最后一个位置但数组中仍然有空闲空间时确实是队列溢出的情况而不是假溢出。这种情况通常是由于没有充分利用队列所分配的存储空间所导致的因此会造成队列操作的限制。 “假溢出” 通常用于表示队列中还有空闲空间但因某种原因无法继续插入元素的情况这可能是由于某些限制条件或错误的队列操作所导致的。例如可能存在对队列的错误管理使得无法正确地判断队列是否已满导致了插入元素失败的情况。 举个例子
在一个顺序队列中队列大小为5已包含四个元素 value1-2-3-4rear在队尾4的位置。 当出队两个元素value1-2时队列前面多出来了两位置 当你想再插入来两个数据时队列确只能插入一个数据但是队列其实不能插入数据了。 这是队列在结构上没有真正满溢,但是在逻辑上已经无法再插入新元素了。 怎么优化这个假溢出呢两种常见的方法 循环队列: 循环队列是一种特殊的顺序队列通过将队列的数组视为一个循环的环形结构使得在队列尾部插入元素时可以利用数组头部的空闲空间从而解决了假溢出的问题。循环队列中当队尾指针指向数组的末尾时再插入元素时将其指向数组的起始位置这样就形成了一个循环。通过这种方式可以充分利用数组空间避免了假溢出。动态扩容: 动态扩容是在顺序队列满时自动增加数组的大小以容纳更多元素。当队列满时分配一个更大的数组并将原有的元素复制到新数组中然后释放原来的数组。这样可以确保队列始终有足够的空间来插入新的元素从而避免假溢出。动态扩容的关键是选择适当的扩容策略以及控制扩容时机以避免频繁的扩容操作带来的性能开销。 循环队列概念 循环队列是一种基于数组实现的队列数据结构其特点是通过循环利用数组空间来实现队列的操作。循环队列的数组通常被看作一个环形的结构队列的头部和尾部指针在数组中循环移动使得当尾部指针到达数组末尾时可以将其“循环”到数组的起始位置从而避免了溢出或假溢出的情况。
循环队列看似循环其实是固定数组不断往复的过程我们可以模拟普通数组来实现 如图data 表示一个数据域int 为类型当然你也可以修改为任意自定义的类型也可以是复杂的结构体类型。 MAX_SIZE 表示循环最大容量可进行放数据的操作空间 rear代表尾指针入队时移动。 front代表头指针出队时移动。 size记录当前有效数据的多少 代码 #define MAX_SIZE 5typedef struct {int data[MAX_SIZE];int front; // 队列头指针int rear; // 队列尾指针int size; // 队列当前元素个数 } Cir_Queue;循环队列的初始化 对于循环队列来说,front从0开始是合理的,因为数据数组是环状结构,front从0开始可以实现队列元素的循环利用。 rear从0开始表示队列此时为空,front和rear指针都指向数组第一个位置。 将队列当前元素个数size清零,表示队列为空。 // 初始化队列 void initQueue(Cir_Queue* queue) {queue-front 0;将队列头指针front设置为0。queue-rear 0;将队列尾指针rear也设置为0。queue-size 0; }循环队列的入队操作 入队操作与顺序队列相同只需将rear向后移动。但要注意如果rear达到队列的上限需从头开始移动。建议使用余数法确保操作在队列空间内进行避免一次错误导致整体崩溃。 要进行入队操作得先判断队列是不是满了rearfront来判断队空也可以用size。 // 入队操作 void enqueue(Cir_Queue* queue, int value) {if (queue-size MAX_SIZE) {printf(Queue is full. Enqueue operation failed.\n);return;}queue-data[queue-rear] value;queue-rear (queue-rear 1) % MAX_SIZE; // 使用(rear1)%MAX_SIZE更新rear指针循环移动queue-size; }检查队列是否已满可通过判断size是否等于MAX_SIZE来确定。如果已满则打印提示信息并返回将数值value赋给data数组的rear索引位置并使用(rear1)%MAX_SIZE更新rear指针。这里使用模运算来实现rear指针的循环移动。当rear指向最后一个位置时利用模运算使其指向第一个位置实现循环利用数组。然后将size增加1表示元素个数加1。 循环队列的出队操作 // 出队操作 int dequeue(Cir_Queue* queue){if (queue-size 0){printf(Queue is empty. Dequeue operation failed.\n);return -1;}int value queue-data[queue-front];queue-front (queue-front 1) % MAX_SIZE; // 循环移动queue-size–;return value; }使用(front1)%MAX_SIZE更新front指针这里也使用模运算实现front指针的循环移动。当front指向最后一个位置时,利用模运算让它指向第一个位置。 查看队首元素 // 查看队首元素 int front(Cir_Queue* queue) {if (queue-size 0) {printf(Queue is empty. Front operation failed.\n);return -1;}return queue-data[queue-front]; }查看队尾元素 // 查看队尾元素 int rear(Cir_Queue* queue) {if (queue-size 0) {printf(Queue is empty. Rear operation failed.\n);return -1;}return queue-data[(queue-rear - 1 MAX_SIZE) % MAX_SIZE]; }查看队列是否为空 // 查看队列是否为空 int isEmpty(Cir_Queue* queue) {return (queue-size 0); }查看队列是否已满 // 查看队列是否已满 int isFull(Cir_Queue* queue) {return (queue-size MAX_SIZE); }测试下循环队列 int main() {Cir_Queue queue;initQueue(queue);enqueue(queue, 10);enqueue(queue, 20);enqueue(queue, 30);enqueue(queue, 40);printf(Front element: %d\n, front(queue));printf(Dequeued element: %d\n, dequeue(queue));printf(Dequeued element: %d\n, dequeue(queue));printf(Dequeued element: %d\n, dequeue(queue));enqueue(queue, 80);enqueue(queue, 90);printf(Front element: %d\n, front(queue));printf(rear element: %d\n, rear(queue));return 0; }总结 感谢你的收看如果文章有错误可以指出我不胜感激让我们一起学习交流如果文章可以给你一个小小帮助可以给博主点一个小小的赞