以图明志

数据结构

循环队列与链队列的优劣势

循环队列、链队列分别什么时候用
从时间上,其实它们的基本操作都是常数时间,即都为0(1)的,不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存在一些时间开销,如果入队出队频繁,则两者还是有细微差异。对于空间上来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。

数据结构

补完链队列的其它常见操作

置空、求长度、判断空等
返回队头元素:若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR。求队列的长度:求链队列的长度,用一个工作指针遍历队列然后记录长度即可。判断队列是否为空:判断链队列是否为空很简单,比较队头指针与队尾指针是否重合即可,Q.front==Q.rear 。

数据结构

链队列的出队操作

删除首元结点的算法步骤
出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear指向头结点。要删除掉a1结点,思路很简单,就是让头结点Q->front的后继next直接指向a2。但是a2如何标识呢?假设a1结点为p结点,那么a2就是p->next了。如何让a1结点存到p呢?

数据结构

链队列的入队操作

与链表插入大致相同
入队操作时,其实就是在链队列(链表)的尾部插入结点。根据这个图,我们就可以大概知道入队操作的步骤了。根据图,我们先创建一个结点s,QueuePtr s=(QueuePtr)malloc(sizeof(QNode));然后给s的data域赋值e,指针域next赋值null。s->data=e;s->next=NULL; 目的就是让它成为新任队尾元素。

数据结构

链队列的初始化操作

还有return和exit有区别
链队列的初始化应该怎么写呢?要初始化一个链队列,我们这么这么做:产生头结点 (QueuePtr)malloc(sizeof(QNode)),然后让队头指针(头指针)与队尾指针都指向头结点。置空头结点 Q->front 的指针域 Q->front->next=NULL;

数据结构

链队列:队列的链式存储结构

链队列的结构体定义
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。当队列为空时,front和rear都指向头结点。与链栈一样,我们分两步定义链队列的结构体,首先是按链表来定义链队列的结点。

数据结构

关于循环队列的一些讲解

循环队列的长度与队满情况
前面讲到了队列的“假溢出”,解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。比如昨天的例子,rear可以改为指向下标为0的位置,这样就不会造成指针指向不明的问题了。

数据结构

队列顺序存储结构的不足

引入循环队列的概念
所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为0(1)。与栈不同的是,队列元素的出列是在队头,即下标为0的位置,那也就意味着,队列中的所有元素都得向前移动,以保证队列的队头(也就是下标为0的位置)不为空,此时的时间复杂度为0(n)。

数据结构

顺序队列置空与判断操作

判断空队列
关于顺序队列,还有些ADT里的操作没有实现,今天实现下吧。比如置空顺序队列。置空顺序队列操作比较简单,只要让队头指针与队尾指针相等即可。判断队列是否为空,可以借鉴上面的函数。如果队头指针与队尾指针相等,那么队列就是为空。注意函数里传入的是实体对象,实体对象需要用实心点来指向成员,所以判断条件写成 Q.front==Q.rear。

数据结构

顺序队列的出队操作

将队头指针向后移动一位即可
昨天我们谈论了顺序队列的入队操作,那么今天我们就看看如何出队吧。出队其实就是删除队列(线性表)的队头元素咯。貌似只要将队头指针向后移动一位就可以完成出队了 Q->front=(Q->front+1)%MAXSIZE; ,哦,在这之前需要用 e 来保存出队的元素。

数据结构

顺序队列的入队操作

可以假想军训的时候理解
昨天我们定义了顺序队列的ADT,还写了顺序队列的初始化函数。那么现在我们马上来看队列的一个重要的基础操作:入队。想想,入队的算法应该怎么写?如何判断一个队列是否满的?假设我们在军训中排队,每个人报数。一个队列只能站10个人,从1报到10,队就满了。

数据结构

顺序队列:队列的顺序存储结构

顺序队列的结构体定义和初始化
线性表分为顺序存储和链式存储,栈是线性表,所以也有这两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。我们先来看队列的顺序存储结构。要用程序来了解队列,先要定义队列的结构体。那么如何设计队列的结构体呢?我们一直都是用数组来实现顺序存储的,顺序队列也不例外。

数据结构

队列的抽象数据类型ADT

定义我们需要实现的队列的操作
因为队列同样是线性表,所以队列也有类似线性表的各种操作,不同的就是插入数据只能在队尾进行,删除数据只能在队头进行。简单来说,队列就是后面装入数据,前面取出数据。用途:保障时间的顺序,比如用户事务操作。链队列:链式存储的队列,长度没限制啊。顺序队列:顺序存储的队列。

数据结构

开始学习队列这个数据结构

队列的基本认识
你在用电脑时有没有经历过这样的事?机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算reset时。突然它像酒醒了一样,把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。

数据结构

将中缀表达式转化为后缀表达式

也是使用栈这个数据结构
规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分;若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于找顶符号(乘除优先加减)则栈顶元素依次出找并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

数据结构

图解后缀表达式的计算过程

了解后缀表达式的工作原理
为了解释后缀表达式的好处,我们先来看看,计算机如何应用后缀表达式计算出最终的结果20的。后缀表达式:9 3 1-3*+ 10 2/+,规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。
1 / 2 首页 < Prev 1 2 Next > 尾页 页码: