从浏览器到栈

 

从浏览器到栈

 

• 从浏览器到栈
  • 栈是什么？
  • 如何实现一个栈？
  • 栈的应用
    • 表达式
    • 括号匹配
    • 浏览器
  • 补充

---

栈是什么？

说到栈我们总是先想到 FILO(first in last out), 有没有什么更贴切一点的例子呢？

有了，洗盘子其实和栈很像，我们总是从盘子的顶部拿起盘子，第一个放的盘子是最后一个拿出来的，符合FILO, 这样我们就能很自然地理解栈(stack)，这种数据结构咯。

如何实现一个栈？

上面我们讲了什么是栈，那让我们动手实现一个吧。实现栈，我们既可以用数组，也可以用链表。前一种叫做顺序栈，后一种则是 链式栈.

• 代码

  // 基于数组实现的顺序栈
  class ArrayStack{
      private String[] items;
      private int count; // 栈中元素个数
      private int n;     // 栈的大小 
  
      // 初始化数组，申请一个大小为n的数组空间
      public ArrayStack(int n){
          this.items = new String[n];
          this.n = n;
          this.count = 0;
      }
  
      // 入栈
      public boolean push(String item){
          if(count==n) return false;
          items[count] = item;
          ++count;
          return true;
      }
  
      // 出栈
      public String pop(){
          // 栈为空，则直接返回 null
          if(count == 0) return null;
          // 返回下标为 count-1 的数组元素
          String tmp = items[count-1];
          --count;
          return tmp;
      }
  }
  
  // 基于链表实现的栈
  class StackBasedOnLinkedList {
      private Node top = null;
  
      public void push(int value) {
          Node newNode = new Node(value, null);
          if (top == null) {
              top = newNode;
          } else {
              newNode.next = top;
              top = newNode;
          }
      }
  
      // -1表示栈中没有数据
      public int pop() {
          if (top == null)
              return -1;
          int value = top.data;
          top = top.next;
          return value;
      }
  
      public void printAll() {
          Node p = top;
          while (p != null) {
              System.out.print(p.data + " ");
              p = p.next;
          }
          System.out.println();
      }
  
      private static class Node {
          private int data;
          private Node next;
  
          public Node(int data, Node next) {
              this.data = data;
              this.next = next;
          }
  
          public int getData() {
              return data;
          }
      }
  }

• 当然你还可以自己尝试实现一下顺序栈的扩容，它的摊还时间复杂度为O(1)。

栈的应用

表达式

关于表达式，我的第一反应是后缀表达式(逆波兰表示法), 不过我们今天不讨论这个，先来讲一讲简单的四则运算。如果我们要计算 3 + 5×8 -6 ,如何用栈实现呢？

• 图例
  图源 转载使用，如侵权则联系我删除！
  
• 分析
  如图，我们使用两个栈实现。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符的栈顶元素比较。如果比栈顶运算符的优先级高，就将当前运算符压入栈；如果比栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数的栈顶取2个操作数，然后计算，再把结果压入操作数栈，继续比较。

括号匹配

我们假设表达式中只包含三种括号，圆括号(), 方括号[] , 和花括号{}, 并且他们可以任意嵌套。那么如何检查他们是否合法呢？
我们可以用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫到左括号时，将其压入栈中当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则为非法格式。

浏览器

假如，我们打开了 a,b,c 三个页面，先从 c 回退到a, 再从 a 前进到 b，示意图如下，运用双栈实现。
图源 转载使用，如侵权则联系我删除！

补充

最后，我们思考两个问题：

• 我们在写程序时会发现，程序是用函数调用栈来保存临时变量的，为什么要用“栈”来保存临时变量呢？用其他的数据结构不行吗？
• 我们都知道，JVM内存管理中有个"堆栈"的概念。 栈内存用来存储局部变量和方法调用，堆内存用来存储Java中的对象。那么JVM里面的“栈“和我们这里说的栈是不是一回事呢？如果不是，那他为什么又叫做"栈"呢？