【数据结构】三、栈和队列：5.顺序队列(循环队列)（初始化，判空判满，入队，出队，实例）

embedded/2024/9/25 5:45:25/

文章目录

  • 队列Queue
    • 逻辑结构
    • 物理（存储）结构
    • 基本操作
    • 1.顺序队列（循环队列）
      • 1.1初始化
      • 1.2判空&判满
        • 1.2.1判空
        • 1.2.2判满
          • 方案一
          • 方案二
          • 方案三
      • 1.3入队
        • 循环队列
      • 1.4出队
      • 1.5获取队头元素
      • 1.6获取队列元素个数
      • ❗1.7循环队列c++实例

队列Queue

逻辑结构

队列（Queue）是只允许在一端进行插入，另一端进行删除操作的线性表。

重要术语：队头（可以出队（删除）的一段），队尾（放入（入队）的元素的一段），空队列。

  • 特点：先进先出（First in First out, FIFO）

物理（存储）结构

  1. 顺序队列（顺序存储）
  2. 链队列（链式存储）

基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队。若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x)：出队。若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x)：读队头元素。若队列Q非空，则将队头元素赋值给x。

1.顺序队列（循环队列）

用顺序存储，连续空间实现队列

循环队列的特点

  1. 顺序存储：循环队列使用数组作为底层数据结构，元素按顺序存储在数组中。这样可以简化队列的实现，并且通过使用循环来优化队列的操作。

  2. 固定容量：循环队列拥有固定的容量，即队列最多可以存储的元素数量是预先确定的。在使用数组作为底层数据结构时，需要初始化队列的最大容量。

  3. 头尾相连：循环队列将队列的头部和尾部连接起来形成一个环状结构，当队列的尾部指针达到数组的最末尾时，它将会绕回到数组的开头。这样可以充分利用数组的存储空间，避免浪费空间。

  4. 队空和队满判断：循环队列通过队头指针和队尾指针的位置关系来判断队列的状态。当队头指针和队尾指针相等时，表示队列为空；当队尾指针的下一个位置是队头指针时，表示队列已满。

  5. 入队和出队的复杂度：在循环队列中，入队和出队操作的时间复杂度都是O(1)，即常数时间复杂度。这是因为循环队列通过使用固定容量和记录队列元素个数的方式，避免了移动元素的成本。

#define MaxSize 10			//定义队列中元素的最大个数
typedef struct{ElemType data[MaxSize];	//用静态数组存放队列元素int front,rear;			//front队头指针和rear队尾指针
} SqQueue;			//Sq即sequence：顺序的意思

1.1初始化

InitQueue(&Q)：初始化队列，构造一个空队列Q。

//初始化队列
void InitQueue(SqQueue &Q){//初始时 队头、队尾指针指向0Q.rear=Q.front=0;
}

1.2判空&判满

1.2.1判空
//判断队列是否为空
bool QueueEmpty(SqQueue Q){if(Q.rear==Q.front)		//队空条件：队头指针==队尾指针return true;else return false;
}
1.2.2判满
方案一

从队头结点开始插入，一直插入到MaxSize放满。但其实现在并不一定是满队列，因为队头还可以出队元素，这时候rear还在MaxSize，但是front不在data[0]。

队列己满的条件：队尾指针的再下一个位置是队。这里就必须空出一个元素的位置，不能让Q.rear==Q.front，因为这样，就和判空的条件一样了。

请添加图片描述

//判断队列是否满
bool QueueFull(SqQueue Q){if( (Q.rear+1)%MaxSize==Q.front )	//队列将满return true;elsereturn false;
}
方案二

如果说不能浪费判满的那一个存储空间，就在定义的时候创建一个size表示队列的长度。

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;int size;
} SqQueue;

这样，初始化的时候，设置size=0。插入成功size++;删除成功size--;。

队满的条件就变成了size==MaxSize。

对空的条件：size==0。

方案三

定义一个tag，用来存储最近进行了删除和插入的操作，每次删除操作成功时，都令tag=0;每次插入操作成功时，都令tag=1;。

#define MaxSize 10
typedef struct{ElemType data[MaxSize];int front,rear;int tag;
} SqQueue;

队满的条件就变成了front==raer && tag==1。

对空的条件：front==raer && tag==0。

1.3入队

EnQueue(&Q,x)：入队。若队列Q未满，将x加入，使之成为新的队尾。

//入队
bool EnQueue(SqQueue &Q, ElemType x){if（队列已满）return false;		//队满则报错Q.data [Q.rear]=x;		//将×插入队尾Q.rear=(Q.rear+1)%MaxSize;		//队尾指针后移，但不能一直+1会溢出，所以这里需要模运算，取(Q.rear+1)%MaxSize的余数return true;
}
循环队列

如果rear队尾一直+1，那么就会溢出，通过模运算，将无限的整数域映射到有限的整数集合 {0, 1, 2,…, MaxSize} 上，将存储空间在逻辑上变成环状。

如此实现的队列，称为循环队列。

请添加图片描述

1.4出队

DeQueue(&Q,&x)：出队。若队列Q非空，删除队头元素，并用x返回。

//出队（删除一个队头元素，并用x返回)
bool DeQueue(SqQueue &Q, ElemType &x){ if(Q.rear==Q.front)return false;	//队空则报错x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;
}

1.5获取队头元素

GetHead(Q,&x)：读队头元素。若队列Q非空，则将队头元素赋值给x。

//获得队头元素的值，用x返回
bool GetHead(SqQueue Q, ElemType &x){ if(Q.rear==Q.front)return false;	//队空则报错x=Q.data[Q.front];return true;
}

返回为元素类型

//取队头元素
QElemType GetHead(SqQueue Q){if (!QueueEmpty(Q)) //队列不为空{return Q.data[Q.front];  //返回队头指针元素}return false;
}

1.6获取队列元素个数

length= (Q.rear + MaxSize - Q.front)%MaxSize;

//获取队列元素个数
int QueueLength(SqQueue Q){int length=(Q.rear + MaxSize - Q.front)%MaxSize;return length;
}

❗1.7循环队列c++实例

#include<iostream>
using namespace std;#define MaxSize 50  //最大队列长度
typedef int QElemType;//循环队列typedef struct
{QElemType* data;	//初始化的动态分配存储空间int front;				//头指针，若队列不空，指向队列头元素int rear;					//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;  					//普通类型用 '.' *SqQueue指针类型用 '->'bool InitQueue(SqQueue& Q);		//循环队列初始化
int  QueueLength(SqQueue Q);	//循环队列长度
bool QueueEmpty(SqQueue Q);			//判断队列是否为空
bool QueueFull(SqQueue Q);			//判断队列是否已满
bool EnQueue(SqQueue& Q, QElemType value);	//循环队列入队
bool DeQueue(SqQueue& Q, QElemType& value);	//循环队列出队
bool QueuePrint(SqQueue Q);			//打印输出队列
QElemType GetHead(SqQueue Q);		//获取队头元素int main()
{SqQueue Q;  //创建循环队列QInitQueue(Q); //队列初始化QElemType value = -1;int number = 0; //入队的元素个数cout<<"请输入要入队的元素个数："<<" ";cin>>number;int num = 0; //入队的数据元素while( (number--) > 0){EnQueue(Q, num); 	//将num入队num++;}cout << "队列输出顺序：";QueuePrint(Q); //遍历输出队列元素cout << "队头元素为：" << GetHead(Q) << endl;cout << "队列长度为：" << QueueLength(Q) << endl;cout << "---出队一个元素后---" << endl;DeQueue(Q, value);cout << "出队元素为：" << value << endl;QueuePrint(Q);cout << "出队后队头元素为：" << GetHead(Q) << endl;cout << "出队后队列长度为：" << QueueLength(Q) << endl;delete[] Q.data; //释放存储空间system("pause");return 0;
}//初始化队列，构造一个空队列Q。
bool InitQueue(SqQueue& Q){Q.data = new QElemType[MaxSize]; //分配数组空间//Q.data = (QElemType*)MaxSize * sizeof(QElemType);  C语言语法if (!Q.data){return false;  //存储分配失败}Q.front = Q.rear = 0; //头指针尾指针置为0， 队列为空return true; 
}//求循环队列的长度/元素个数
int QueueLength(SqQueue Q){//若rear指向大于队列长度后重新转一圈指向队头，假如rear=3，front= 4, 3-4=-1不合法。则通过（3-4+6)%6 = 5个元素return ((Q.rear - Q.front + MaxSize) % MaxSize);
}//判断队列是否为空。队空条件：队头指针==队尾指针
bool QueueEmpty(SqQueue Q){return (Q.front == Q.rear);
}//判断队列是否已满
bool QueueFull(SqQueue Q){return (Q.rear + 1) % MaxSize == Q.front;  //队列满
}//入队：若循环队列Q未满，将value加入，使之成为新的队尾。
bool EnQueue(SqQueue& Q, QElemType value){if (!QueueFull(Q)){   		//如果队列没满Q.data[Q.rear] = value; //将入队元素放入Q.rear所指向的空间中Q.rear = (Q.rear + 1) % MaxSize;	//队尾指针+1return true;}return false; 	//队列已满，入队失败
}//出队：若循环队列Q非空，删除队头元素，并用value返回。
bool DeQueue(SqQueue& Q, QElemType &value){if (!QueueEmpty(Q)){  			//如果队列非空value = Q.data[Q.front];	//将出栈元素保存到value中Q.front = (Q.front + 1) % MaxSize; //队头指针+1return true; }return false; //队列为空，出队失败
}//取队头元素
QElemType GetHead(SqQueue Q){if (!QueueEmpty(Q)){ 			//队列不为空return Q.data[Q.front];  //返回队头指针元素}return false;
}//遍历打印队列元素
bool QueuePrint(SqQueue Q) {//这里注意！！！ 如果要用这种方法，参数列表一定不能用'SqQueue &value'引用，//因为使用&会修改真正的Q.front和Q.rear空间地址,影响原函数的指针位置，和后面的函数调用。if (Q.front == Q.rear)		//空队列return false;while (Q.front != Q.rear){cout << Q.data[Q.front] << "  ";Q.front = (Q.front + 1) % MaxSize;}cout<<endl;return true;//方案二，由于额外创建了临时变量用来遍历队列，不管用不用'&Q'都不会影响原队列中front与rear的位置//if (!QueueEmpty(Q))   //队列非空//{//	QElemType temp = Q.front; //创建临时变量，位置与队头相同//	while (temp != Q.rear)//	{//		cout << Q.data[temp] << " ";  //输出temp所处位置的元素//		temp = (temp + 1) % MaxSize; //temp位置上移加 1 //	}//	cout << endl;//	return true;//}//return false;
}

请输入要入队的元素个数： 5
队列输出顺序：0 1 2 3 4
队头元素为：0
队列长度为：5
—出队一个元素后—
出队元素为：0
1 2 3 4
出队后队头元素为：1
出队后队列长度为：4
Press any key to continue . . .


http://www.ppmy.cn/embedded/22987.html

相关文章

debian和ubuntu的核心系统和系统命令的区别

debian和ubuntu的核心系统和系统命令的区别

Debian和Ubuntu虽然有很深的渊源&#xff0c;都是基于Debian的发行版&#xff0c;但它们在核心系统和系统命令上还是有一些差别的。以下是一些主要的不同之处&#xff1a; 1. 发布周期&#xff1a; - Debian&#xff1a; Debian项目采用滚动发布模型&#xff0c;持续更新&a…
阅读更多...
关于ListView的使用及其实现原理

关于ListView的使用及其实现原理

ListView的使用 ListView的使用主要分为以下几个步骤&#xff1a; 布局定义&#xff1a; 在XML布局文件中定义ListView控件&#xff0c;为其指定ID&#xff0c;并设置相关属性&#xff0c;如宽度、高度等。 <ListView android:id"id/list_view" android:layout…
阅读更多...
为什么分类问题不能使用mse损失函数，更容易理解版本

为什么分类问题不能使用mse损失函数，更容易理解版本

分类问题通常不适合使用均方误差&#xff08;Mean Squared Error&#xff0c;MSE&#xff09;损失函数&#xff0c;原因如下&#xff1a; 1.输出差异&#xff1a; 输出差异的度量不同&#xff1a;MSE损失函数是基于预测值和真实值之间的差异的平方和进行计算的&#xff0c;适…
阅读更多...
【迅投qmt系列】4、获取数据的方式

【迅投qmt系列】4、获取数据的方式

获取数据是进行策略回测、实时执行的前提&#xff0c;不同的场景下&#xff0c;有相对合适的数据获取方式。 1、只取历史数据 这个场景的内容一般是将历史数据下载下来后&#xff0c;再将数据用于其他用途。因为对效率没有多少要求&#xff0c;代码最简单&#xff0c;它将qmt…
阅读更多...
【Vue】通过Axios实现异步通信（简单案例）

【Vue】通过Axios实现异步通信（简单案例）

一、Axios介绍 1、是什么 Axios 是一个基于 promise 的 HTTP 库&#xff0c;简单的讲就是可以发送get、post请求。当然这些请求ajax和jquery也能做&#xff0c;但是由于Vue、React等框架的出现&#xff0c;促使了Axios轻量级库的出现&#xff0c;因为Vue等&#xff0c;不需要操…
阅读更多...
Games101-相机与透镜

Games101-相机与透镜

成像&#xff1a;光栅化成像(上图)和光线追踪成像(下图) 都是用合成的方法来成像。还可以用捕捉的方法来成像 利用小孔成像原理制作的相机就是针孔相机 如果一个相机没有针孔/透镜&#xff0c;是无法拍照的。 因为任何一个点都有可能收集到来自不同方向上的光。这个点本身作为…
阅读更多...
基于Flask的岗位就业可视化系统（一）

基于Flask的岗位就业可视化系统（一）

前言 本项目综合了基本数据分析的流程&#xff0c;包括数据采集&#xff08;爬虫&#xff09;、数据清洗、数据存储、数据前后端可视化等 推荐阅读顺序为&#xff1a;数据采集——>数据清洗——>数据库存储——>基于Flask的前后端交互&#xff0c;有问题的话可以留言…
阅读更多...
Gin+WebSocket实战——在线聊天室WebSocketDemo详细使用教程

Gin+WebSocket实战——在线聊天室WebSocketDemo详细使用教程

文章目录 仓库地址项目简介如何使用 仓库地址 Github&#xff1a;https://github.com/palp1tate/WebsocketDemo 欢迎star&#xff01;&#x1f60e; 项目简介 利用 GinWebSocket 实现的在线聊天室Demo项目&#xff0c;支持加入/离开聊天室广播、给其他用户发送消息等。 如何…
阅读更多...
最新文章

Copyright @ 2022~2023