找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

队列c++

admin 2020-7-13 05:58 87人围观 C++相关

循环队列与链队



总算把你给盼来了

现在才关注我 确实是晚了点

但没关系 来了就好




工具:vs code 、ppt

操作系统:Linux







SUMMER




目录

1.队列的概念

    1.1、定义

    1.2、其它概念

2.顺序队列的一些弊端及解决

    2.1、弊端

    2.2、解决

3.循环队列与链队的实现

    3.1、循环队列的顺序存储结构与链队的链式存储结构

    3.2、循环队列与链队的初始化与清空操作

    3.3、循环队列与链队的进队与出队操作

    3.4、循环队列与链队的判断队列是否为空与求队列长度的操作

    3.5、循环队列与链队的获取队头与队尾的操作

    3.6、循环队列与链队的遍历



1.队列的概念


 1.1、定义

队列(Queue):

    是允许在一端进行插入操作,而在另一端进行删除操作的线性表。

 1.2、其它概念

队列是一种先进先出(First In First Out,FIFO)的线性表,在一端进行元素插入是队头(front),在另一端进行删除元素是队尾(rear)。




2.顺序队列的一些弊端及解决
2.1、弊端

实现顺序队列时,可能出现下述三种"溢出"的现象:

a.“下溢”:  队列为空时进行出队;

b.“真上溢”:队列已满时进行入队;

c.“假上溢”:对于顺序队列来说,由于删除元素时队首指针增加,造成空间闲置,此时队列的存储元素数量总是小于实际容量;

2.2、解决

A.解决“假溢出”问题——循环队列

循环队列的定义:首尾相连的顺序存储结构称为循环队列。

循环队列的一些操作:


  1. 初始队列:front=rear=0(或1)

  2. 空队列:front==rear

  3. 队满条件:(rear+1)%Queuesize

  4. 进队操作:rear=(rear+1)%Queuesize

  5. 出队操作:front=(front+1)%Queuesize


  6. 求队列长度:

    (rear-front+Queuesize)%Queuesize



B.解决“溢出”问题——链队

若使用链式存储结构则不存在“溢出”现象,因为链表的节点创建和删除都是动态进行的,即在链表的一端进行插入,另一端进行删除,只要允许链表不断申请内存空间即可。











3.循环队列与链队的实现



3.1、循环队列的顺序存储结构与链队的链式存储结构



循环队列的顺序存储结构




链队的链式存储结构






3.2、循环队列与链队的初始化与清空操作


循环队列初始化与清空操作




链队初始化与清空操作






3.3、循环队列与链队的进队与出队操作


 

循环队列进队与出队操作




链队的进队与出队操作






3.4、循环队列与链队的判断队列是否为空与求队列长度的操作

循环队列的判断队列是否为空与求队列长度的操作



链队的判断队列是否为空与求队列长度的操作



3.5、循环队列与链队的获取队头与队尾的操作

循环队列的获取队头与队尾的操作



链队的获取队头与队尾的操作



3.6、循环队列与链队的遍历

循环队列的遍历




链队的遍历











栈++







部分图片来源网络
侵删致歉




转载需经同意并引用出处






----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:榣山下,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......