以图明志

数据结构

接触后缀表达式(逆波兰表示法)

逆波兰表示法的起因
栈的现实应用也很多,我们再来重点讲一个比较常见的应用:数学表达式的求值。20世纪50年代,波兰逻辑学家Jan tukasiewicz想到了一种不需要括号的后缀表达法,我们也把它称为逆波兰(Reverse Polish Notation, RPN)表示。这样的表达式称为后缀表达式,叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

数据结构

栈是如何实现递归的

递归与栈一些不得不说的事
在高级语言中,调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称做递归函数。迭代和递归的区别是:迭代使用的是循环结构,递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。

数据结构

递归,栈的重要应用之一

了解递归的一些细节
栈有一个很重要的应用:在程序设计语言中实现了递归。那么什么是递归呢?当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果A、B两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个 “化身”。一连串的“像中像” 这是一种递归现象。

数据结构

为什么要使用栈这种数据结构

缩小思考范围,聚焦问题核心
栈的引入简化了程序设计的问题,划分了不同关注层次,使得思考范围缩小,更加聚焦于我们要解决的问题核心。反之,像数组等,因为要分散精力去考虑数组的下标增减等细节问题,反而掩盖了问题的本质。所以现在的许多高级语言,比如Java、C#等都有对栈结构的封装,你可以不用关注它的实现细节,就可以直接使用Stack的push和pop方法,非常方便。

数据结构

链栈的置空操作与判断链栈是否为空

与单链表的置空操作相同
判断链栈是否为空很简单,还记得结构体定义时的那个 count 吗?如果那个 count 为0,就说明链栈为空。置空链栈就没有置空顺序栈那么简单了。置空顺序栈只要一步 S->top=-1; 即可,但是对于链栈却不是那么回事了。方法是设置两个工作结点,开始循环。在释放p之前,让q成为p的后继。还是那个比喻,在皇帝死之前,册封皇子。free(p); 皇帝死了,p=q; 皇子就成了新皇帝。

数据结构

链栈的出栈操作

其实就是删除结点而已
前面讨论了链栈的进栈操作,这里接下来讨论链栈的出栈操作。至于链栈的出栈pop操作,也是很简单的三句操作。假设变量p用来存储要删除 的栈顶结点,将栈顶指针下移一位,最后释放p即可。首先设定一个工作结点 p,并且将栈顶结点赋值给它。然后将栈顶指针下移一位,指向下一结点。代码表示为 S->top=S->top->next;

数据结构

链栈的初始化与遍历

链栈的基本操作
我们在定义完一个数据结构的结构体之后,需要初始化才能使用。比如顺序栈的初始化,也就是构造一个空栈就行了。那么链栈如何初始化呢?链栈初始化的目标也是要构造一个空栈。根据结构体定义,空栈是什么一个状况呢?就是栈的count = 0,并且栈的 top 为 null。所以知道这两点,我们就可以写出链栈的初始化函数了。

数据结构

链栈的进栈操作

两个步骤即可完成
链栈的操作绝大部分都和单链表类似,只是在插入和删除上,特殊一些。假设元素值为e的新结点是s, top为桟顶指针……那么我分析下过程,首先开辟一个内存空间给 s,然后 s的data就是e,再将新结点s 的后继赋值为当前结点 S->top。最后将栈顶指针指向结点 s。

数据结构

链栈:栈的链式存储结构

链栈的结构体定义
前面讲完了栈的顺序存储结构,我们现在来看看栈的链式存储结构,简称为链栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。单链表有头指针,而栈顶指针也是必须的,那干吗不让它俩合二为一呢,所以比较好的办法是把栈顶放在单链表的头部。

数据结构

获取顺序栈的栈顶元素

判断栈是否为空与置空栈
根据前面定义的栈ADT,我们还有几个操作要完成。比如获取顺序栈的栈顶元素 GetTop (S,*e):若栈存在且非空,用e返回S的栈顶元素。这个操作的函数设计思路如何呢?参考之前线性表的话,就是设一个存储栈顶的变量 e,然后通过地址传递,用 *e 来保存指针为 top 的数组元素。

数据结构

顺序栈的出栈操作

与进栈相反的操作
昨天我们讲了顺序栈的进栈操作,那么今天我们来看一下与进栈相对应的出栈操作吧。进栈是先自增再赋值,出栈则反过来。先把要出栈的元素获取到,然后再指针自减,把空间释放出来。

数据结构

顺序栈的进栈操作

外加栈的初始化与遍历
对于栈来说,最重要的操作之一就是进栈。我们今天来看看如何实现顺序栈的进栈操作。进栈操作push大概分为两步。栈顶指针 S->top 先自增1,给需要进栈的元素腾出内存空间。再赋值。就是给对应的数组元素赋值:S->data[S->top]=e

数据结构

顺序栈:栈的顺序存储结构

栈的结构体定义
既然栈是线性表的特例,那么栈的顺序存储其实也是线性表顺序存储的简化,我们将其简称为顺序栈。线性表是用数组来实现的,对于栈这种只能一头插入删除的线性表来说,用数组哪一端来作为栈顶和栈底比较好?下标为0的一端作为栈底比较好,因为首元素都存在栈底,变化最小,所以让它作栈底。

数据结构

栈的抽象数据类型ADT

定义我们需要实现的栈的操作
对于栈来讲,理论上线性表的操作特性它都具备,可由于它的特殊性,所以针对它在操作上会有些变化。特别是插入和删除操作,我们改名为push和pop,英文直译的话是压和弹,更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了,我们一般叫进栈和出栈。

数据结构

栈的定义与大概理解

什么是栈
栈是限定仅在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。栈又称为后进先出(Last In First Out)的线性表,简称LIF0结构。定义中说是在线性表的表尾进行插入和删除操作,这里表尾是指找顶,而不是栈底。
2 / 2 首页 < Prev 1 2 Next > 尾页 页码: