Press "Enter" to skip to content

数据结构之栈

栈Stack

栈(stack),它是一种运算受限的线性表,后进先出(LIFO)

  • LIFO(last in first out)表示就是后进入的元素, 第一个弹出栈空间. 类似于自动餐托盘, 最后放上的托盘, 往往先把拿出去使用.
  • 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。
  • 向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;
  • 从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

就好比有很多辆车进了一个死胡同,第一进去的,总是最后一个出来。下面图来演示一下:

(上图来自简书 https://www.jianshu.com/p/eade026ffaf5

栈对应的操作是数组的子集;只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)

添加元素和取出元素都只能从栈顶位置开始存取。
栈是一种后进先出的数据结构。Last ln First Out (LIFO);
在计算机的世界里,栈拥有着不可思议的作用

栈的应用: 无处不在的Undo操作(撤销)

  • 比如你打字: 沉迷学习无法自拔,然后将无法打成不法。

撤销就是将这个不法出栈,然后将后续的正确字都入栈。
程序调用的系统栈(对于理解递归有作用)

函数A运行到一半,调用函数B; B运行到一半,调用函数C;


A2指函数A运行到了第二行,B2指函数B运行到了第二行。当函数C顺序执行完毕之后,该执行哪一个函数呢,拿出栈顶B2继续执行。
当B函数执行完毕之后,拿出栈顶A2,执行A函数,执行完之后,发现栈为空,整个程序执行完毕。

子过程,子逻辑的调用,对于理解递归有作用。

栈的操作

  • 栈常见有哪些操作呢?
    • push(element): 添加一个新元素到栈顶位置.
    • pop():移除栈顶的元素,同时返回被移除的元素。
    • peek():返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)。
    • isEmpty():如果栈里没有任何元素就返回true,否则返回false
    • clear():移除栈里的所有元素。
    • size():返回栈里的元素个数。这个方法和数组的length属性很类似。

栈的应用

undo操作-编辑器;

系统调用栈-操作系统;

括号匹配 ;

关于数据结构的代码 个人的php实现都在github中:https://github.com/htmax/Play-with-Data-Structures

Leave a Reply

Your email address will not be published. Required fields are marked *