【数据结构】详解队列和循环队列

news/2024/11/25 4:28:42/

目录

  • 一.队列
    • 1.队列的概念及结构
    • 2.队列的实现
      • Queue.h
      • Queue.c
  • 二.循环队列
    • 1.循环队列的实现
    • 2.设计循环队列
      • 解题思路
      • 代码

一.队列

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First in first out）的特性
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
在这里插入图片描述

2.队列的实现

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，在数组头部出队列，效率会很低。
在这里插入图片描述

  • 如果队列使用顺序表的结构实现，进行出队操作时，有两种方法，1是将对头指针指向下一个位置，这会造成空间上的浪费。
    2是将对头后的所有数据向前移动一个位置，出队操作的时间复杂度就会变大，所以使用顺序表实现队列是不可取的。
  • 因为队列要对对头和队尾进行操作，所以我们需要使用两个结构体指针，分别指向队头和队尾。

Queue.h

存放队列的所有函数的声明

#pragma once
#include<stdio.h>
#include<assert.h>typedef int QDataType;typedef struct QListNode
{struct QListNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* front;QNode* tail;int size;
}Queue;void QueueInit(Queue* q);//初始化队列void QueuePush(Queue* q, QDataType x);//队尾入队列void QueuePop(Queue* q);//对头出队列QDataType QueueFront(Queue* q);//获取队列头部元素QDataType QueueTail(Queue* q);//获取队队尾元素int QueueSize(Queue* q);//查看队列中有效元素的个数int QueueEmpty(Queue* q);//查看队列是否为空，若是非空返回非零结果，若是为空，返回0void QueueDestroy(Queue* q);//销毁队列void QueuePrint(Queue* p);//打印队列

Queue.c

存放所有函数的实现

1.初始化队列

//初始化队列
void QueueInit(Queue* q)
{q->front = NULL;q->tail = NULL;q->size = 0;
}

将对头和队尾全部置为空，当进行入队操作时，在使这两个指针分别指向对应的空间。

2.队尾入队列

//队尾入队列
void QueuePush(Queue* q, QDataType x)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (!newNode){perror("malloc fail");exit(-1);}newNode->data = x;newNode->next = NULL;if (!q->front){q->front = q->tail = newNode;}else{q->tail->next = newNode;q->tail = newNode;}q->size++;
}

向内存申请一个存放数据的空间，并向其存放数据。
判断此时队列中是否有数据，如果没有，对头和队尾都指向申请的空间，如果有，将队尾指向的空间的next赋值为新申请的空间，在将队尾指向新申请的空间。
最后将队列的大小加1，完成入队操作

3.队头出队列

//对头出队列
void QueuePop(Queue* q)
{assert(q);//当队列中没有元素时assert(q->front);if (q->front == q->tail){q->front = q->tail = NULL;}else{QNode* newNode = q->front;q->front = q->front->next;free(newNode);}q->size--;
}

首先判断，队列是否为空，若为空，无法进行出队列操作。
其次判断队列是否只要一个数据，若对头和队尾只写同一个空间，即只有一个数据，此时将两个指针都置为空，完成出队列操作。
如果，队列不为空，且队列中有多个数据，则队头进行操作，将对头指向的下一个位置变为对头，将之前的位置释放(队列中的空间是向内存申请的，需要释放，否则会造成内存泄漏)，完成出队操作。

4.获取对头数据

//获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);//查看队列是否为空assert(q->front);//查看队列头部是否为空return q->front->data;
}

当队列不为空时，返回对头指向的空间所存储的数据即可。

5.获取队尾数据

//获取队队尾元素
QDataType QueueTail(Queue* q)
{assert(q);assert(q->front);return q->tail->data;
}

若队列不为空，返回队尾指针指向的空间所存储的数据。

6.查看队列中有效元素的个数

//查看队列中有效元素的个数
int QueueSize(Queue* q)
{assert(q);assert(q->front);//QNode* cur = q->front;//int size = 0;//while (cur)//{//	size++;//	cur = cur->next;//}//return size;return q->size;
}

有两种方法，
方法1：我们在设置队列的结构体时，定义了队列的长度size，此时返回size的大小即可。
方法2：若没有定义，则需要我们遍历队列，判断队列的长度
在实际应用队列时，我们不知道队列的结构体是如何设置的，我们只能通过这个函数来获取队列的有效元素的个数。

7.查看队列是否为空

//查看队列是否为空，若是非空返回非零结果，若是为空，返回0
int QueueEmpty(Queue* q)
{assert(q);return q->front == NULL && q->tail == NULL;
}

8.销毁队列

//销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* temp = cur;cur = cur->next;free(temp);}q->front = q->tail = NULL;q->size = 0;
}

队列中的空间都是向内存申请的，需要自己主动去释放，将队头的地址赋给一个临时的指针，由该指针去释放，当该指针为空时，表示已释放完毕。
最后我们将对头和队尾置空，将队列的大小改为0即可。

9.Queue.c完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"//初始化队列
void QueueInit(Queue* q)
{q->front = NULL;q->tail = NULL;q->size = 0;
}//队尾入队列
void QueuePush(Queue* q, QDataType x)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (!newNode){perror("malloc fail");exit(-1);}newNode->data = x;newNode->next = NULL;if (!q->front){q->front = q->tail = newNode;}else{q->tail->next = newNode;q->tail = newNode;}q->size++;
}//对头出队列
void QueuePop(Queue* q)
{assert(q);//当队列中没有元素时assert(q->front);if (q->front == q->tail){q->front = q->tail = NULL;}else{QNode* newNode = q->front;q->front = q->front->next;free(newNode);}q->size--;
}//获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);//查看队列是否为空assert(q->front);//查看队列头部是否为空return q->front->data;
}//获取队队尾元素
QDataType QueueTail(Queue* q)
{assert(q);assert(q->front);return q->tail->data;
}//查看队列中有效元素的个数
int QueueSize(Queue* q)
{assert(q);assert(q->front);//QNode* cur = q->front;//int size = 0;//while (cur)//{//	size++;//	cur = cur->next;//}//return size;return q->size;
}//查看队列是否为空，若是非空返回非零结果，若是为空，返回0
int QueueEmpty(Queue* q)
{assert(q);return q->front == NULL && q->tail == NULL;
}//销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur = q->front;while (cur){QNode* temp = cur;cur = cur->next;free(temp);}q->front = q->tail = NULL;q->size = 0;
}//打印队列
void QueuePrint(Queue* p)
{assert(p);QNode* cur = p->front;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

二.循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模式时可以使用循环队列。
循环队列可以使用数组实现，也可以使用循环链表实现。
这里我们使用数组实现，因为一般循环队列的长度是固定的，数组可以很好的契合这一标准。
在这里插入图片描述

1.循环队列的实现

环形队列可以用数组实现，也可以用循环链表实现。
根据不同的情况，我们选择不同的实现方法：
当给定的循环链表的大小是固定时，使用数组更为简单，可以少掉链表的插入和删除，直接根据下标解决问题。
当给定的循环链表的大小不是固定时，可以试着使用循环链表，也可以少掉很多麻烦。

  • 这里我们根据Leetcode上的一道循环链表题来讲解这个知识点。

2.设计循环队列

设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

解题思路

该题中，循环队列给定了固定的大小，我们就可以使用顺序表实现它。
首先给出的数组大小为7个整形：
image.png
当队列为空时，我们将对头和队尾都指向下标为0的位置，
当插入元素时，我们将对头和队尾移动到下标为1~7的位置
image.png
这题的难点就是对队列入队和出队的操作，解决这两个问题，其他的在这两个的基础上也就迎刃而解。
这时我们就要分情况讨论了，

  • 当队列已满时，有这几种情况
    image.png
    所以当我们判断队列是否已满，或进行入队操作时，可以根据这两种情况判断
  • 当进行出队操作时，又有这两种特殊种情况
    image.png
    情况1：出队后队尾的位置加1等于对头的位置，表明此时队列为空，将对头和队尾置为0，表示此时队列为空
    情况2：出队后对头的位置大于所给出队列的大小，需将队头位置改为1
    其他出队情况直接将对头位置加1即可
    image.png

代码

typedef struct {int* arr;int head;int rear;int size;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));if(!obj){perror("malloc fail!");exit(-1);}obj->arr = (int*)malloc(sizeof(int)*(k+1));obj->head = obj->rear = 0;obj->size = k;return obj;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if(obj->head == 0){obj->arr[++obj->head] = value;obj->rear++;return true;}else if(obj->rear < obj->size && (obj->rear+1 < obj->head || obj->rear >= obj->head)){obj->arr[++obj->rear] = value;return true;}else if(obj->rear == obj->size && obj->head > 1){obj->arr[1] = value;obj->rear = 1;return true;}return false;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if(obj->head){obj->head++;if(obj->head == obj->rear+1)obj->head = obj->rear = 0;else if(obj->head > obj->size)obj->head = 1;return true;}return false;
}int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);if(!myCircularQueueIsEmpty(obj))return obj->arr[obj->head];return -1;
}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);if(!myCircularQueueIsEmpty(obj))return obj->arr[obj->rear];return -1;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);if(obj->head == 0)return true;return false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);if(obj->rear+1 == obj->head)return true;if(obj->rear == obj->size && obj->head == 1)return true;return false;
}void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj->arr);obj->arr = NULL;obj->head = obj->rear = obj->size = 0;
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

http://www.ppmy.cn/news/6119.html

相关文章

单商户商城系统功能拆解52—财务概况

单商户商城系统功能拆解52—财务概况

单商户商城系统&#xff0c;也称为B2C自营电商模式单店商城系统。可以快速帮助个人、机构和企业搭建自己的私域交易线上商城。 单商户商城系统完美契合私域流量变现闭环交易使用。通常拥有丰富的营销玩法&#xff0c;例如拼团&#xff0c;秒杀&#xff0c;砍价&#xff0c;包邮…
阅读更多...
10.1、Django框架简介、创建第一个应用

10.1、Django框架简介、创建第一个应用

文章目录预备知识MVC模式和MTV模式MVC模式MTV 模式Django框架Django框架简介Django框架的应用启动后台admin站点管理数据库迁移创建管理员用户管理界面本地化创建并使用一个应用bookapp项目的数据库模型创建数据库模型生成数据库表数据库上的基本操作启用后台admin站点管理自定…
阅读更多...
PID算法总结-从公式原理到参数整定解析

PID算法总结-从公式原理到参数整定解析

目录 一、控制系统 1.1控制系统的分类 1.2 性能指标 二、PID算法的起源及特点 三、PID应用 四、PID公式原理 五、PID源码 六、PID整定方法 6.1 经验法 6.2 衰减曲线法 6.3 响应曲线法 参考文献&#xff1a; 一、控制系统 1.1控制系统的分类 分为开环控制、闭环控制和复…
阅读更多...
Web API节点操作

Web API节点操作

1、节点概述 网页中的所有内容都是节点&#xff08;标签、属性、文本、注释等&#xff09;&#xff0c;在DOM 中&#xff0c;节点使用 node 来表示。HTML DOM 树中的所有节点均可通过 JavaScript 进行访问&#xff0c;所有 HTML 元素&#xff08;节点&#xff09;均可被修改&a…
阅读更多...
TCManager——中药房管理系统大作业

TCManager——中药房管理系统大作业

简介 由于最近一个月世界变化有点大&#xff0c;所以一直在同步自己的大脑&#xff0c;没有写博客。 上个月花了5天&#xff08;3天后端2天前端&#xff09;写了个经典的springbootvue2的中药房管理系统大作业——TCManager。项目已在gitee上&#xff08;校园网差&#xff0c;…
阅读更多...
SpringBoot整合RocketMQ

SpringBoot整合RocketMQ

SpringBoot整合RocketMQ 因为SpringBoot集成RocketMQ的starter依赖是由Spring社区提供的&#xff0c;目前正在快速迭代的过程当中&#xff0c;不同版本之间的差距非常大&#xff0c;甚至基础的底层对象都会经常有改动。 1.创建消息生产者 1.1生产者Pom <?xml version&q…
阅读更多...
cgo对go的性能影响

cgo对go的性能影响

cgo对go的性能影响 概述 做go封装给python和perl进行使用的时候&#xff0c;使用cgo->swig->python、perl流程&#xff0c;对整个流程的性能进行了粗略的性能比较。&#xff08;在deepin环境进行的测试&#xff09; cgo代码 package main //注意必须是main包// #inclu…
阅读更多...
如何在anaconda中配置graphviz包

如何在anaconda中配置graphviz包

文章目录GraphViz简介一&#xff1a;安装graphviz二&#xff1a;配置环境变量三&#xff1a;检测Graphviz是否配置成功。四&#xff1a;安装graphviz包GraphViz简介 graphviz是贝尔实验室开发的一个开源的工具包&#xff0c;它使用一个特定的DSL(领域特定语言):dot作为脚本语言…
阅读更多...
最新文章

Copyright @ 2022~2023