| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> 数据结构笔记3——栈和队列 -> 正文阅读 |
|
[数据结构与算法]数据结构笔记3——栈和队列 |
笔记中图片均来源于课堂PPT 正在学习中,如有错误欢迎指正! 一、栈的简介及性质栈是一种特殊的线性表,仅在表的一端进行插入或删除操作。 最令人关心的是栈的性质:栈中的元素遵循着后进先出,先进后出的规则(LIFO),出于这个性质,我们可以将栈类比于抽屉这样的存储结构,所有最先放入抽屉中的元素会被放到最深处,难以拿到,只有最后才能出栈。所以,我们大多数对栈的操作,实质上都是对栈顶元素、栈顶位置的操作。 ??附上PPT中辅助理解的一个例子:
此处插入到最下端的操作换成栈的语言就是:小陈想将最后的元素插入到栈底结果遭到阻止,违背了栈后进先出的规则(最后插入的作业却放到栈底想最后被批到),这显然是不可取的。? 二、栈的基本操作栈的基本操作有:创建,入栈,出栈,遍历,下面我们来一个一个拆解着分析。 1.栈的定义为了方便后续操作,在创建一个栈之前,我们先来定义栈的数据类型。前面已经提到,栈是特殊的线性表,所以栈的定义应该和线性表有相似之处,根据线性表的定义,可以知道:栈也应该有两种定义方式,它们是顺序栈和链栈,分别对应着顺序表和链表。接下来,我们也用这两种方式来定义栈。 ①顺序栈顺序栈和顺序表非常相似,它们都由一个int型单变量和一个int型数组构成,其中数组寄存着元素的数值;对于栈中的另一个int型元素,我们定义它为top,其意义为栈顶目前所处的位置。 如此一来,我们既有了栈当前元素(也就是栈顶元素)的值,又有了它在整个栈中的位置,就可以利用数组和数组下标top来实现栈的其他基本操作了。 不过这里要注意的是,虽然在大多数情况下我们都把top作为栈数组下标来完成操作,但stack->top却是从-1开始的,也就是说,当栈空时的stack->top=-1,这点理解起来确实很别扭,遇到变下标的问题时,要和数组区分好。 顺序栈定义的代码如下:
②链栈链栈理解起来更容易一点,它和链表比较相似,但是在栈的定义中,我们不需要定义头结点(后面会详细介绍原因),只需要定义一个data指向元素域,*next指针指向下一个元素,以及栈的长度length即可完成栈的操作。 链栈的定义如下:
2.入栈操作在已经学过顺序表的插入之后,对于入栈来说,我们唯一需要再仔细思考的就是栈满条件,对于顺序栈和链栈,栈满条件并不相同,下面我们逐个分析。 ?①顺序栈在顺序栈中没有length的属性,所以为了定义栈满的状态,在全局中定义了一个maxnum作为栈的最大长度(其实这就是变相的定义length),此刻,栈满的条件也显而易见的浮出水面:因为stack->top从-1开始,所以栈满时必有stack->top == (maxnum - 1)。 谈完了栈满,再来看常规操作:在每一次元素入栈时,首先为这个元素腾出一个新的位置(top++),然后在这个空位置放入元素(elem[stack->top] = x),就完成了入栈操作。 代码如下:
②链栈链栈元素的入栈方式与链表比较像,它们大体上都是通过动态分配内存、data赋值、next变化来完成插入或入栈操作的。特殊的是,在栈中,为了维护栈“后入先出”的特性,我们需要对插入的顺序进行一定的变化:将插入元素放在第一位,然后接原来的stack。(例如:插入元素为4,原来的栈中元素为3、2、1,令4->next=stack,可以得到新栈4、3、2、1)这样就做到了新插入的元素放在表的第一位。 代码如下:
需要说明的是:该代码没有限制长度对入栈的限制,如果需要通过输入元素的个数来决定是否继续进行入栈,可以加入一个条件判断语句判定是否栈满。? 3.出栈操作出栈的意思为:将栈中最顶层的元素弹出,并返回该元素的值,所以应该用一个int型函数来完成该操作。 ①顺序栈有了前面的数据结构作为铺垫以及我们日渐准确的直觉( ̄▽ ̄)~*?要想弹出元素,首先要判断栈是否非空,根据前面介绍的栈空条件(stack->top=-1)可以很简单的完成。 弹出元素和插入元素很相似,唯一需要注意的就是:在出栈过程中,需要先弹出元素,再改变top的位置,否则元素弹出的位置会错误(例如:栈的元素为4、3、2、1,若先改变top的位置,那么stack->top=3,弹出时得到的栈顶元素是错误的。)
②链栈链栈的出栈也很简单,和链表一样,它最核心的一步在于stack=stack->next,比较容易,就不细说啦,直接放代码:
4.栈的遍历①顺序栈顺序栈的思路比较简单,我们需要做的只有:判空,循环,输出,和数组的遍历比较类似,代码如下:
②链栈链栈相对来说就复杂一些,但万变不离其宗,它的核心仍然是:print stack->data,stack=stack->next,只需要在变化过程中维护栈的性质不变。 首先,由于栈的不断遍历,stack变成stack->next,又变成stack->next->next......,这就导致了在执行完遍历函数回到main函数后,栈的top已经发生了变化,所以,要想正确的完成之下来的操作,需要将栈的top变为原来的top。在函数开头未进入循环时记录top值,在最后重新赋值就可以实现该过程。
三、队列的简介及性质队列也是一种特殊的线性表,类比于栈,它和栈有着截然相反的性质。 如其名,队列的性质像“队列”一样:先排队、就先出队。也就是说,队列中的元素符合“先进先出,后进后出”(FIFO)的准则。根据这个性质,队列可被比作为钟摆:每次插入元素只在钟摆的一端(队尾)进行,删除元素在钟摆的另一端(队首)进行。所以,我们对队列的操作,也大多数是对队首元素和队尾元素的操作。 ?四、队列的基本操作队列的基本操作有:创建,入队,出队,遍历,下面我们来一个一个拆解着分析。 1.队列的定义首先,我们来用数组实现队列。 设想一下,在这个定义队列的结构体中,必须要有一个储存队列每个元素值的数组,来存放数据的值;其次,为了方便后续对队首队尾的元素进行操作,我们定义两个指向队首队尾的“指针”变量。由于这是用数组实现的队列,所以指向位置的变量不必用真正的指针变量,用数组下标即可代替。 这样一来,就有了储存元素值的储存结构,还有指向位置的“指针”用来进行位置的移动,这样就完成了队列的定义。
2.队列的初始化我们在定义队列时,定义了两个int型变量,它们分别为rear和front,现在我们用这两个int型变量作为“指针”,在之后的操作中,我们将用这两个变量控制队尾和队首的元素。 当初始化队列时,队列中没有数据,只需将队首和队尾的“指针”归为同一值(且为零)即可
3.入队操作有了两个“指针”变量后,我们就可以随心所以的对队首和队尾元素进行操作了,插入新元素、更新队列自然是不在话下,所以我们重点要关注的就是队列满的条件,当队列满后,禁止对头尾元素进行操作。 但是仔细一想,用数组实现的队列好像有点儿难找出它的队满条件,因为如果用动态内存分配+队尾指针不停向后挪的话,它会一直向后延伸,似乎这个队列永远不会到达尽头。 为了节省空间复杂度,优化算法,在真正介绍入队操作之前,先引入一个常用(也常考)的用循环数组实现的队列,先来看两幅图: ? 这就是循环数组实现队列的特性:当rear指针指向当前队列最后一个元素且队列未满时,再次入队的元素会进入数组第一个元素中去,也就是说,rear和front指针不停的在[0—n-1]之间游走,每当走到最后一个位置,下一次再向前时,就返回到队列第一个位置,这就是循环数组定义的队列。还需要注意的是:作为编程的习惯,rear为指向队尾下一个可存放节点的位置,而不是当前队尾元素,这么说可能有点别扭,但在之后的例子中将深化对它的表述和理解。接下来,我们的操作都是基于这种队列。 好了,那么我们来真正的判断队满的条件,注意一下:我们现在定义的队列满,不是真正意义上的全满,而是队列仍然有一个可以放元素的位置时,就判断它已经满。现在直接给出结论: 当 (rear +1) % MAXNUM = = front时,队列满。 ?来解读一下这个判断式,rear指向下一个可放元素位置。根据图中可知,当rear和front成为邻居时,队伍可判满,而后面的对maxnum取余则是因为在循环数组中下标逐渐递增,当循环一圈会再次回头,所以要取余来变成物理意义上的位置。 比如说:maxnum=7,front=2,rear=1,带入队满条件后队列已满,所以该队满条件成立。
3.出队操作?和入队相反的是,在出队过程中,我们首先要判断队列是否非空,非空则会得到错误输出,那么现在来寻找队空条件。 现在我们可以放心大胆的说:当rear==front的时候,队伍为空了,因为如果队列是空的,下一个放元素位置的指针rear和队首指针将会重合(如果它们不是一个位置的话,可以设想插入一个元素之后的情景,将会发生错误) ?出队代码如下,其中要注意移动front的位置以起到出队的效果。
4.队列的遍历其实队列的遍历和线性表比较相似,只要每次输出元素后,rear向后挪动一格,直到rear和front相遇(即每个元素都遍历到,队空),就结束遍历,比较简单,直接放代码了。
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 | -2025/1/10 3:24:49- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |