顺序队列和链队列

news/2024/4/25 18:29:25

队列也是一种线性结构,不同于栈的是队列为先进先出的数据结构,遵循一边入队一边出队。

在这里插入图片描述

顺序队列的底层使用的是数组,因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外,为了满足顺序队列中数据从队尾进,队头出且先进先出的要求,我们还需要定义两个指针(top 和 rear)分别用于指向顺序队列中的队头元素和队尾元素。

数组中一直存储着入栈数据,只是读数据的时候从记录的队首元素读取。

在这里插入图片描述
在添加(入队)时,元素被添加到队位(rear)所在位置,对位加一,依次类推,这样在添加元素时元素依次填充数组的位置。

#include<stdio.h>
#define MAXSIZE 5
typedef struct Queue{int datas[MAXSIZE];int front;int rear;
}SqQueue;//入队
int Push(SqQueue *S,int e){if(S->rear == MAXSIZE) return 0;S->datas[S->rear] = e;S->rear++;return 1;
}//出队
int Pop(SqQueue *S){int e = S->datas[S->front];S->front++;return e;
}int main(){SqQueue S;S.front = S.rear =0;Push(&S,3);Push(&S,5);Push(&S,7);int e = Pop(&S);printf("%d\n",e);int e1 = Pop(&S);printf("%d\n",e1);int e2 = Pop(&S);printf("%d\n",e2);return 0;
}

在删除(出队)是,队头(top)指向的元素赋值个给临时变量,队头后移指向下一个元素。队头像游标一样持续记录当前位置,模拟元素的出队。

对于数组实现的会遇到假溢出问题,如下:
在这里插入图片描述
当rear指向最后一个元素时,rear无法在后移,于是队列满了,但是看top的位置却在第4个元素的位置,也是说前三个元素都出栈了,空出了三个元素的位置。为了解决该假溢出的问题,可以将队列变成一个循环队列

循环队列利用top,rear,MAXSIZE的关系巧妙模拟循环。rear在指向最后一个位置时再次添加就回到数组第一个位置,再一次向后移,top也是如此。

若是循环队列,则必是以MAXSIZE为进制的运算。所以rear只能在[1,MAXSIZE]的区间内。那么rear的运算就变成了:

S->rear = (S->rear+1)%MAXSIZE

注意如果以mAXSIZE定义数组那么数组为[MAXSIZE-1],因为数组是从0开始的。

如何判断队列是否满了呢?

  • 第一种情况

在这里插入图片描述

在这里插入图片描述

主要有以上两种情况表示队列满了。第一种S->rear = (S->rear+1)%MAXSIZE,注意是计算后的情况,满足Q.front = Q.rear。这种判断是不合理的,因为该判断条件也是判空的条件。

一般情况下可以少用一个元素空间, 即队列空间大小为m时,有m-1个元素就认为是队满。这样判断队空的条件不变, 即当头、 尾指针的值相同时, 则认为队空;而当尾指针在循环意义上加1后是等千头指针, 则认为队满。(在舍弃一个存储元素的空间情况下完美解决问题)。

在这里插入图片描述
在这里插入图片描述

途中rear都是入队计算后的rear值。

在少用一个元素的情况下,满足(S->rear+1)%MAXSIZE) == S->front 表示队满。

因此, 在循环队列中队空和队满的条件是:
队空的条件:Q.front = Q.rear
队满的条件:(Q rear+ 1)%MAXSIZE = Q.front

#include<stdio.h>
#define MAXSIZE 5
typedef struct Queue{int datas[MAXSIZE];int front;int rear;
}SqQueue;//入队
int Push(SqQueue *S,int e){if( (S->rear+1)%MAXSIZE ==S->front) return 0;S->datas[S->rear] = e;S->rear = (S->rear+1)%MAXSIZE;return 1;
}//出队
int Pop(SqQueue *S){int e = S->datas[S->front];S->front = (S->front+1)%MAXSIZE;return e;
}int main(){SqQueue S;S.front = S.rear =0;Push(&S,3);Push(&S,5);Push(&S,7);int e = Pop(&S);printf("%d\n",e);int e1 = Pop(&S);printf("%d\n",e1);int e2 = Pop(&S);printf("%d\n",e2);return 0;
}

链队是指采用链式存储结构实现的队列。和顺序队列一样链对也需要队头和队尾游标,并以链表为存储结构。链队就是后插法创建链表。


https://www.xjx100.cn/news/848168.html

相关文章

一些很有用的技术工具

前端工具 codyhouse,有很多的demo&#xff0c;使用起来非常的方便&#xff0c;CodyHouse的github。jqueryscript,很多优秀的js插件都可以在上面找到。 shell oh-my-zsh&#xff0c;文艺编程员必备的shell。 歌曲 搬砖怎么没有歌&#xff1f;awesome-music-for-programming p…

9秒学院-技术宅七夕示爱招数“高大上”赶快来看看

今天是七夕佳节&#xff0c;大家想好怎么过节了吗&#xff1f;单身的朋友是否想要借着牛郎织女鹊桥相会之日向心仪已久的Ta表白爱意&#xff1f;热恋中的情侣们是否也想要趁机玩一把浪漫&#xff0c;给彼此留下美好回忆呢&#xff1f; 9秒学院的程序猿们还在奋发图强吧&#xf…

Facebook广告投放需要多少费用?如何设置Facebook广告预算?(干货教程)

在Facebook上刊登广告需要多少费用&#xff1f;Facebook广告的平均CPC&#xff08;每次点击费用&#xff09;和CPM&#xff08;每千展费用&#xff09;是多少&#xff1f;如何设置您的Facebook广告预算&#xff1f; 本文将回答所有这些问题。但是首先&#xff0c;根据Revealbo…

大学计算机应用教程马秀麟,马秀麟

本书从信息处理与应用的视角入手&#xff0c;由5大模块组成&#xff0c;主要包括了计算机体系结构与信息表示&#xff0c;信息处理平台与信息获取、文本处理与信息呈现、数据管理与数据分析、媒体素材处理&#xff0c;分别以Word2013、PowerPoint2013、Excel2013、Prezi、Photo…

object-c iOS 教程 git for mac

本文转载至 http://blog.csdn.net/u011728347/article/details/10035191 http://rypress.com/tutorials/objective-c/index.html &#xff08;Object-C 教程&#xff09; http://www.raywenderlich.com/tutorials&#xff08;各种关于ios的教程&#xff09; http://prezi.com/8…

Impress.js教程

Impress.js是一款基于css3转 换和过渡、工作于现代浏览器(Google Chrome或Safari (或 Firefox 10 或 IE10))、并受prezi.com的理念启发的演示工具。如果你已经厌烦了使用PowerPoint制作PPT&#xff0c;那么impress.js是一个非常 好的选择&#xff0c;用它做的PPT更加直观&#…

Office 2019怎么下载?附学习视频教程

只能网络下载&#xff0c;仅支持Win10系统&#xff01;领&#xff01; 根据微软的说法&#xff0c;Office 2019不再提供MSI本地安装包&#xff0c;仅通过Click-to-Run网络安装包的方式发放。如此一来&#xff0c;每一次用户安装Office 2019的时候就只能下载数量庞大的组件&…

网盘资源库

Adobe CC 2018震撼来袭&#xff0c;全套安装包教程 链接&#xff1a; http://pan.baidu.com/s/1c2500xE 密码&#xff1a;3tcw PSCC一对一基础教程链接&#xff1a; https://pan.baidu.com/s/1eToScJg 密码&#xff1a;p0d7 100集PS高级强化班教程&#xff0c;是时候升级你的P…