Tuesday, April 16, 2019

如何理解栈

  • 后进先出,先进后出,这就是栈结构
  • 栈是一种操作受限的线性表
  • 数组实现的栈叫顺序栈
  • 链表实现的栈叫做链式栈
  • 栈的各类操作时间复杂度都是O(1)

支持动态扩容的顺序栈

链式栈自不用说,本身支持动态扩容,顺序栈动态扩容的实现,只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了以后,申请一个更大的数组,并将原来的数据迁移过去。

时间复杂度

  • 出栈一直都是O(1)
  • 入栈涉及到一个满栈的时候,需要迁移。这时最好的时间复杂度是O(1),最坏是O(n)
  • 我们降扩容时需要的O(n)时间复杂度均摊给入栈操作,所以入栈的均摊时间复杂度是O(1)

file

栈的常见应用

  • 栈在函数调用中的应用
  • 栈在表达式求值中的应用
  • 栈在括号匹配中的应用
  • 栈在浏览器中的应用

在浏览器中,使用两个栈,浏览的页面依次压入栈X,后退的时候,从栈X出栈,并依次压入到栈Y,前进的时候,从栈Y出栈回到栈X,当X栈中没有数据时,说明没有后退的页面了,当Y栈中没有数据时,说明没有前进的页面了。

数据结构-算法

队列(上)

链表(下)