0

Image Description

荆文征

Zhidu Inc.


你好,再见

大话数据结构 - 栈与队列 4

  • 小酒馆老板
  • /
  • 2018/1/2 13:12:0


H2

栈与队列


H3

栈的定义

栈(Stack)是限定尽在表为进行插头和删除操作的线性表

我们把允许插入和删除的一段称为栈顶(top),另一端称为栈底(bottom),不含有任何元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表,建成LIFO结构。
理解栈的定义需要注意:
首先它是一个线性表,也就是说,栈元素具有线性关系,继前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表为进行插入和删除操作,这里表为是指栈顶,而不是栈底。
栈的插入操作,叫做进栈,也称压栈,入栈。类似子弹入弹夹。
栈的删除操作,也叫出栈,也有的叫做弹栈。如同弹夹中的子弹出夹。



Image Description
进栈与出栈示意图


H3

进栈出栈变化形式

现在我要问问大家,这个要最先进栈的元素,是不是就只能最后出栈呢?
答案是不一定的,要看什么元素。栈对线性表的掺入和删除的位置进行了限制,并没有对元素进出的时间进行限制,也就是说,在不是所有元素都见栈的情况下,事先进去的元素也可以出栈,只要保证栈顶元素出栈就可以了。
举例来说,如果我们现在是有3个整型数字元素1,2,3依次进栈,会有哪些出栈次序呢?

  • 第一种: 1,2,3进,再3,2,1出。这是最简单的最好理解的一种,出栈次序为 321.
  • 第二种: 1进,1出,2进,2出,3进,3出。也就是进一个就出一个,出栈次序为 123
  • 第三种: 1进,2进,2出,1出,3进,3出。出栈次序为213.
  • 第四种: 1进,1出,2进,3进,3出,2出。出栈次序132
  • 第五种: 1进,2进,2出,3进,3出,1出。出栈次序为231.
    有没有可能是312这样的出栈舒徐呢?答案是肯定不会。因为3先出栈就意味着,3曾经进栈,既然3都进栈了,那就意味着,3曾经进栈,既然3都进栈了,那也就意味着,1和2都已经进栈了。
    从这个简单的例子就可以看出,只是三个元素,就有5中可能的出栈次序,如果元素量大,其实出栈的次序将会更多的,这个知识点一定要弄明白


    H2

    栈的抽象数据类型

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

    protocol Stack{
    
      static func InitStack() -> Stack // 初始化操作,建立一个空栈
      func DestroyStack() // 若栈存在,则销毁它。
      func ClearStack() // 将栈清空
      func StackEmpty() -> Bool // 若栈为空,返回true,否则返回false
      func GetTop() -> Any // 如果存在非空,返回栈顶元素
      func Push(object:Any) // 若栈存在,插入新元素
      func Pop() -> Any // 删除栈顶元素,并返回其值
      func StackLength() -> Int // 获取栈的元素的个数
    }
    

    H2

    栈的顺序存储结构及实现


    H3

    栈的顺序存储结构

    既然展示线性表的特例,那么栈的顺序存储其实也是线性表顺序存储的简称,我们称为 顺序栈。线性表是用数组来实现的,想想看,对于栈这种只能一头插入和删除的线性表来说,用数组那一段作为栈顶和栈底比较好?
    没错,下标为0的一段作为栈顶比较好,因为首元素都存在栈底,变化最小,所以让它做栈底。
    我们来定一个Top变量来只是栈顶元素在数组中的位置,这top就如同我们中学物理学习到的游标卡尺的游标,他来回移动,意味着栈顶的top可以变大变小,但无论如何游标不能超过尺的长度。同理,入展的长度为StackSize,则栈的top碧霄小雨StackSize。当栈存在一个元素时,top等于0,因此我们通常把空栈的判定条件定位top等于-1。
    若现在有一个栈,StackSize是5,则栈普通情况,空栈和沾满的是情况示意图:


    Image Description
    普通空栈满栈示意图


H2

栈的链式存储结构及实现


H3

栈的链式存储结构

讲完了栈的顺序存储结构,我们来看看栈的链式存储结构,建成链栈。
想想看,栈只是栈顶来做插入和删除操作,栈顶放在链表的头部还是尾部呢?由于单链表头头指针,而栈顶指针也是必须的,那么干嘛不让他俩合二为一呢,所以比较好的办法是吧栈顶放在单链表的头部。另外,都已经有了孩子安定在头部了,单链表中比较畅通的头结点也就失去了意义,通常对于链栈连锁,是不徐耀头结点。


Image Description
链栈示意图


对于链栈来说,基本不存在栈满的情况,除非内存已经没有可以使用的空间,如果真的发生,那次是的计算机系统,已经面临司机崩溃的情况,而不是这个链栈溢出的问题。
但对于空栈来说,链表原定义是头指针指像空,那么链栈的空就是top=NULL的时候。


H2

顺序栈和链栈

对比一下,顺序栈和链栈,他们在时间复杂度上是一样的,均为O(1)。对于空间性能,顺序栈需要实现确认一个固定的长度,可能会存在内存空间浪费的问题。但他的优势存取是时定位很方便,而链栈则要求每个元素都有指针与,这同时也正价了一些嫩村开销,但对于栈的长度无限制,所以他们的区别和线性表中的讨论一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果他的变化在可控范围内,建议使用顺序栈会更好一些。


H2

栈的作用

有的同学可能会觉的,用数组和链表不直接实现不就行了吗?干嘛要引入栈这种的额数据结构呢?
其实这和我们明明有两只脚走路,干嘛还要成汽车或者飞机一样。理论上,陆地上的任何地方,你都是可以靠双脚走到的,可那徐耀多少时间和精力呢?我们更关注的是到达而不是如何去的过程。
栈的引入简化程序设计的问题,话费了不同关注层次,使得思考范围缩小,更加聚焦于我们要结局的问题。反之想数组等,因为要分散经理去考虑数组下标增减的等下接问题,范围掩盖了问题的本质。
所以现在很多高级语言,比入Java,C#等都有对栈结构的封装,你可以不用关注他的实现细节,就可以直接使用Stack的push和pop方法,非常方便。


H2

栈的应用-递归

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


Image Description
镜子递归现象示意图


我们先来看一个经典的递归例子:斐波那契数列(Fibonacci)。为了说明这个数列,这位斐老还举了一个很形象的例子。


H3

斐波纳切数列实现

说如果兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生一对小兔子。假设所有兔子都不死,那么一年以后可以繁殖多少对兔子呢?
我们那新出生的一对小兔子分析一下:第一个月小兔子每有繁殖能力,所以还是一对,第二个月,剩下一堆小兔子共有两对;三个月后老兔子又剩下一堆,因为小雨还每有繁殖能力,所以一共是3对…依次类推可以列出下表


Image Description
兔子月份和兔子对数示意图


表中数字1,1,2,3,5,8,13…构成了一些序列,这个数列有一个十分明显的特点,那是:前面相邻两项之和构成了后一项
假设我们要打印出前40为斐波纳切烈数。
先考虑下我们如何使用迭代的方式实现打印前40位斐波纳切列数。

var numbers:[Int] = [0,1]
for i in 1...40{
    numbers.append(numbers[i]+numbers[i-1])
}
print(numbers)

代码很简单,几乎不用做什么解释。但其实我们的代码,如果用递归来实现,还可以更简单。

func Fbi(i:Int) -> Int{

    if i < 2 {
        return  i == 0 ? 0 : 1
    }
    return Fbi(i: i-1) + Fbi(i: i-2)
}

for i in 0...40 {

    print(i,":",Fbi(i: i))
}

怎么样,相比较迭代的代码,是不是赶紧很多。嘿嘿,过要弄懂他得费点脑子。
函数怎么可能调用自己呢?听其实有些难以理解,不过你可以不要把递归函数中看作是在调用自己,而是把它当作在调另一个函数。只不过,这个函数和自己长的不一样而已。

ps: 不过这个迭代的执行,,次数也太夸张了?



Image Description
递归函数异常执行次数

我们来模拟代码中Fbi(i)函数i=5的执行函数过程。


Image Description
模拟迭代示意图


H3

递归定义

在高级语言中,调用自己和其他函数并没有本质的不同。我们把 一个直接调用自己或通过一系列的调用的语句简洁的调用自己的函数,成为递归函数。
当然,写递归函数最怕的就是陷入永不结束的无穷递归中,所以,每个递归必定义必须至少有一个条件,满足时递归不再进行,即不再引用自身而返回值推出。 比如刚才的例子会使得i<2的,这样就可以执行return爹语句而不用继续递归了。
对比了两种实现斐波纳切的代码。递归和迭代的区别是:迭代使用的是循环结构,递归使用的是选择结构,递归能使程序的解雇更清晰,更简洁,更容易让人理解,从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本,会消耗大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该是不同情况选择不同的实现方式。


H2

栈的应用–四则运算表达式求值


H3

后缀(逆波兰)表示法定义

栈的现实应用也很多,我们再来重点讲一个比较常用的应用:数学表达式的求值。
我们小学学数学的时候,有一句话是老师反复强调的,“先乘除,后加减,从左算到右,先括号内后括号外”。这个大家都不陌生。
那么如何使用代码的方式来实现数学表达式的求值呢?
这里面的困难在于乘除在加减的后面,却要先运算,而加入括号后,就变的更加的复杂。不知道该如何处理。
单仔细观察后发现,括号都是成对出现的,有左括号就定义会有右括号,对于多重括号,最终也是完全嵌套匹配的。这用栈结构正好合适,只要碰到左括号,就将此左括号进栈,不管多少表达式多少充括号,反正遇到左括号就进栈,而后面遇到的有括号,就让栈顶的左括号出栈,期间让数字运算,这样,最终又阔的表达式从左导游巡查一边,应该由空岛有元素,最终在印全部匹配成功后成为空栈的结果。
但对于四则元算,括号也只是当中的一部分,先乘除后加减是的问题依然复杂,如何有效的处理它们嗯?
20世纪50年代,波兰罗辑学家Jan Lukasiewicz,当时也和我们现在的同学们一样,困惑与如何才可以搞定这个四则运算,不知道他是否像牛顿被苹果砸到头而想到万有引力的原理,或者还是阿基米德在浴缸中洗澡想到判断皇冠是否纯碱的办法,总之他也是灵感凸显,想到了 一种不徐耀括号的后缀表达法,我们也把它称为逆波兰(Reverse Polish Nonation,RPN)表示。 我想可能他的名字太复杂了,所以后人只用它的国籍而不是姓名来命名,是在可惜。

我们先来看看,对于”9+(3-1)×3+10÷2”,如果要启用护椎表示法应该是什么样子:”9 3 1 - 3 * + 10 2 / +”,叫后缀的有原因在于所有的符号都要在运算数字的后面出现。显然这里没有了括号。对于从来没有接触过后缀表达式的同学来讲,这样的表述很难受。


H3

后缀表达式计算结果

为了解释后缀表达式的好处,我们先来看看,计算机如何应用后缀表达式计算出最终的结果20 的。
后缀表达式:9 3 1 - 3 * + 10 2 / +
规则:从左到右便利表达式的每个数字和符号,遇到数字就进栈,遇到是符号,就将栈顶的两个数字出栈,进行计算,运算结果进栈,长一智到最终获得结果

  1. 初始化一个空栈。此栈用来对要运算的数字进出使用
  2. 后缀表达式中的前三个都是数字,所以9,3,1进栈


    Image Description
    逆波兰运算第二步

  3. 接下来是“-”,所以将栈1出栈作为减数,3出栈作为被减数,并运算3-1得到2,再将2进栈


    Image Description
    逆波兰运算第三步

  4. 接着是数字3进栈


    Image Description
    逆波兰运算第四步

  5. 后面是 “* ”号,也就意味着占中的3和2出栈2与3相乘,得到6。再把6进栈
  6. 下面是“+”,所以占中的6和9出栈,9与6想家,得到15,将15进栈


    Image Description
    逆波兰运算第六步

  7. 接着是10与2两数字进栈
  8. 接下来是符号“/”,因此,栈顶的2与10出栈,10与2相处,得到5,将5进栈


    Image Description
    逆波兰运算第八步

  9. 最后一个符号是“+”,所以15与5出栈并想家,得到20,20进栈
  10. 计算结果20出栈,栈变为空


    Image Description
    逆波兰运算第十步

果然,后缀表达法可以很顺利的解决计算的问题。但是这个后缀表达式是如何出来的呢?就让我们来推导


H3

中缀表达式转后缀表达式

。。。。 略


H2

队列的定义

操作系统和客服系统中,都应用了一种疏解后来实现干柴的先进先出的排队功能,这就是队列。

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

队列是一种先进后出(First In First Out)的线性表,简称FIFO。允许插入的一段为队尾,允许删除的一段为队头。 假设队列是 q=(a1,a2,a3…an),那a1就是队头元素,而an就是队尾元素。这样我们就可以删除时,总是从a1开始,而插入式,总是在最后。这就符号我们通常生活的习惯,排在第一个的有限出列,最后来的当然要排在队伍后面。


Image Description
队列示意图


H3

队列的抽象数据类型

同样是线性表队列也有类似线性表的操作,不同的就是插入数据只能在队尾进行,删除数据只能在队头进行。


H3

循环队列

线性表有顺序存储和链式存储,栈是线性表,所以有两种存储方式。同样,队列作为一种特殊的线性表,也同样存在这两种存储方式。我们先来看队列的顺序存储结构。


H2

总结

栈(Stack)是限定在表尾进行插入和删除的线性表
队列(Queue)是只允许在一段进行插入操作,另一段进行删除操作的线性表
他们均可以用现新表的顺序存储结构来实现,但都存在着顺序结构的一些弊端。
因此他们有各自自由的技巧来解决这个问题。
对于栈来说,如果是两个相同类型的栈,则可以用数组的两端作为占地的方法来让两个栈共享数据,这就可以最大化的利用数组的空间。
对于列来说,为了避免数组插入和删除时需要移动数据,于是就引入了循环队列,使得对头和队尾可以在数组中循环变化。解决了移动数据的时间损耗,使得本来插入和删除是O(n)的时间复杂度变成了O(1).
他们都可以通过链式存储结构,实则上与线性表基本相同

专栏: 数据结构
标签: 数据结构 计算机基础