如何理解“栈”？

image.png

如何实现一个“栈”？

  • 用数组实现: 顺序栈
  • 用链表实现: 链式栈

复杂度:

  • 空间 O(1)
  • 时间, 入栈, 出栈都是 O(1)

支持动态扩容的顺序栈

如果要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。

image.png

image.png

往后均摊.

虽说均摊是 O(1), 但是实际情况是总在栈满了的情况下 “停一下”, 在高并发情况下需要渐进时, 这里指广泛情况, 不是说栈要渐进扩容.

栈在函数调用中的应用

  1. int main() {
  2.    int a = 1; 
  3.    int ret = 0;
  4.    int res = 0;
  5.    ret = add(3, 5);
  6.    res = a + ret;
  7.    printf("%d", res);
  8.    reuturn 0;
  9. }
  11. int add(int x, int y) {
  12.    int sum = 0;
  13.    sum = x + y;
  14.    return sum;
  15. }

image.png

栈在表达式求值中的应用

  • 操作数栈
  • 运算符栈

image.png

栈在括号匹配中的应用

我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

解答开篇

使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

  1. 顺序查看了 a，b，c 三个页面，我们就依次把 a，b，c 压入栈

image.png

  1. 当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，我们就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y

image.png

  1. 这个时候你又想看页面 b，于是你又点击前进按钮回到 b 页面，我们就把 b 再从栈 Y 中出栈，放入栈 X 中

image.png

  1. 这个时候，你通过页面 b 又跳转到新的页面 d 了，页面 c 就无法再通过前进、后退按钮重复查看了，所以需要清空栈 Y

image.png