队列的定义、基本操作、顺序实现(初始化,入队,出队)

简介: 数据结构:队列的定义、基本操作、顺序实现(初始化,入队,出队)附有代码讲解

1.队列的定义

队列(Queue):是只允许在一端进行插入,在另一端删除的线性表;

网络异常,图片无法展示
|

  • 入队就是插入操作
  • 出队就是删除操作

特点: 先进先出(FIFO)

重要术语:队头、队尾、空队列

  • 队头:允许删除的一端
  • 队尾:允许插入的一端
  • 空队列:没有任何数据元素

2.队列的基本操作

  • InitQueue(&Q):初始化队列,构造一个空队列Q
  • DestoryQueue(&Q):销毁队列,销毁并释放队列Q所占用的内存空间
  • EnQueue(&Q,x):入队,若队列Q未满,将x加入,使之成为新的队尾
  • DeQueue(&Q,&x):出队,若队列Q非空,删除队头元素,并用x返回
  • GetHead(Q,&x):读对头元素,若队列Q非空,则将队头元素赋值给x

3.队列的顺序实现

用静态数组存放队列元素,在定义一个队头指针,一个队尾指针

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

3.1初始化操作

初始化队列:

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

判断队列是否为空:

bool QueueEmpty(SqQueue Q){
    Q.rear==Q.front
        return true
    return false;
}

3.2入队操作

入队操作只能从队尾入队;实现分析:需要先判断队列是否为满,然后将新元素插入队尾,然后修改队尾的指针后移。

bool EnQueue(SqQueue &Q,ElemType x){
    if(队列已经满)
        return false;
    Q.dara[Q.rear]=x;
    Q.rear=Q.rear+1;   
        return true;
}

3.2.1方案一(判空)

如果直接给队尾指针直接后移是会出问题的,当整个静态数组被存满的时候,rear指针就会指向MaxSize,如果依次让对头出队的时候,rear依然是指向MaxSize,所以rear==MaxSize的条件不能判断队列已经满了。所以需要修改为:让队尾指针+1后取模

Q.rear=(Q.rear+1)%MaxSize;

用模运算将储存空间在逻辑上变成了“环状”

网络异常,图片无法展示
|

3.2.2方案二(判空)

用size记录队列的当前长度,初始化size为0。

int size=0;  //初始化时候
size++;   //插入成功
size--;   //删除成功
队列空:size=0;
队列为满:size==MaxSize

3.2.3方案三(判空)

标记位,删除成功的时候tag=0,插入成功的时候tag=1;

  • 队列满:front==rear && tag==1
  • 队列空:front==rear && tag==0

3.3出队操作

删除一个队列头元素,并且用x返回

bool DeQueue(SqQueue &Q,ElemType &X){
    if(Q.rear==Q.front)   //判断队列是否为空
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+!)%MaxSize;  //队列头指针后移
}

3.4 查队头元素

获得队列头元素值并用x返回

bool GetQueue(SqQueue Q,ElemType &X){
    if(Q.rear==Q.front)   //判断队列是否为空
        return false;
    x=Q.data[Q.front];
    return true;
}
目录
相关文章
|
存储
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
12183 1
【数据结构】连通图、连通分量与强连通图、强连通分量—区别在于强,强强在哪里?
|
存储 缓存 固态存储
SSD的原理和结构简介
SSD如淡雅之兰花,寻求内外统一,内涵与外在俱佳,除了英俊潇洒的外表,内在的魅力同样不可抵挡。
|
算法 C++ 索引
【算法】——全排列算法讲解
【算法】——全排列算法讲解
1379 0
|
10月前
|
存储 弹性计算 人工智能
阿里云MC我的世界联机等游戏云服务器配置价格表
阿里云游戏服务器的年付费用,核心取决于游戏的玩家规模、类型(如小型联机、中型社群服、大型商业服)及是否需要高算力支持(如3D渲染、AI NPC)。2026年阿里云针对游戏场景推出了轻量应用服务器、ECS云服务器两类主力机型,覆盖从10人内小范围联机到50人以上高并发场景,同时搭配秒杀、续费同价等优惠,降低游戏运营成本。以下结合最新信息,按游戏场景拆解配置、年付价格及优惠规则,帮玩家和运营者精准核算费用。
3162 1
阿里云MC我的世界联机等游戏云服务器配置价格表
|
移动开发 网络协议 算法
TCP中的粘包、拆包问题产生原因及解决方法
TCP中的粘包、拆包问题产生原因及解决方法
2432 0
TCP中的粘包、拆包问题产生原因及解决方法
|
运维 供应链 安全
阿里云先知安全沙龙(武汉站) - 网络空间安全中的红蓝对抗实践
网络空间安全中的红蓝对抗场景通过模拟真实的攻防演练,帮助国家关键基础设施单位提升安全水平。具体案例包括快递单位、航空公司、一线城市及智能汽车品牌等,在演练中发现潜在攻击路径,有效识别和防范风险,确保系统稳定运行。演练涵盖情报收集、无差别攻击、针对性打击、稳固据点、横向渗透和控制目标等关键步骤,全面提升防护能力。
|
传感器 测试技术 芯片
在硬件连接时,如何确定 GPIO 引脚的功能和编号
在硬件连接中,确定GPIO引脚的功能和编号需查阅相关芯片或开发板的官方文档,了解引脚布局图,确认引脚的具体功能和编号,以确保正确连接和编程。
1832 3
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
1979 4
|
Java Linux 虚拟化
Docker 部署spring-boot项目(超详细 包括Docker详解、Docker常用指令整理等)
Docker 部署spring-boot项目(超详细 包括Docker详解、Docker常用指令整理等)
8670 2