数据结构与算法系列--栈的精讲

冷不防 2022-02-22 09:59 230阅读 0赞

浏览器的前进后退功能，大家都很熟悉吧？你知道这是如何实现的吗？没错，就是用栈 这种数据结构。如何理解“栈”？就**像一摞叠在一起的盘子**。从下往上放，从上往下取。**后进先出，先进后出**，这就是典型的“栈”结构。其实，计算机世界的思想并非石头缝里蹦出来的，现实世界都有它们的影子。  
  
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。相比数组和链表，栈带给我们的只有限制，那为什么要设计这种数据结构呢？  
因为，在特定场景下，数组或链表暴露了太多的操作接口，虽然灵活，但安全性降低了。

应用场景：当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出，先进后出的特性，我们就应该首选“栈”。

1,如何实现一个栈？

数据结构开篇讲线性表，学到后面才发现，线性表是线性数据结构的基础。所以，对于栈这种线性结构，用数组或链表都可，分别称为顺序栈，链式栈。

// 基于数组实现的顺序栈
    public 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) {
        // 数组空间不够了，直接返回 false，入栈失败。
        if (count == n) return false;
        // 将 item 放到下标为 count 的位置，并且 count 加一
        items[count] = item;
        ++count;
        return true;
      }
      
      // 出栈操作
      public String pop() {
        // 栈为空，则直接返回 null
        if (count == 0) return null;
        // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
        String tmp = items[count-1];
        --count;
        return tmp;
      }
    }

复杂度分析：存储数据只需要大小为n的数组就够了，在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度为O(1)。  
入栈，出栈只涉及栈顶个别数据的操作，所以时间复杂度为O(1).。

2,支持动态扩容的顺序栈

尽管链式栈的大小不受限，但要存储next指针，内存消耗相对较多。那么我们如何基于数组实现一个可以支持动态扩容的栈呢？

这里你可以想到，支持动态扩容的数组吗？当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据统统拷贝过去。这样就实现了一个支持动态扩容的数组。  
所以，如果我们要实现一个支持动态扩容的栈，我们只需要底层依赖一个支持动态扩容的数组就可以了。  
时间复杂度分析：因为涉及到了扩容，拷贝数组，所以时间复杂度为O(n)。但只有个别时候扩容，大部分时候都为O(1)，所以平摊分析，平均情况下的数据复杂度O(1)。

3,栈在函数调用中的应用

我们知道，操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

演示代码：

public class FunctionTest {
    
    	public static void main(String[] args) {
    		int a = 1;
    		a = add(3,5);
    		System.out.println(a);
    		
    	}
    	public static int add(int x,int y){
    		int sum = 0;
    		sum = x + y;
    		return sum;
    	}
    }

反编译，查看字节码

public static void main(java.lang.String[]);
        Code:
           0: iconst_1			    //1(int)值入栈。
           1: istore_1			    //出栈：将栈顶int类型值保存到局部变量1中
           2: iconst_3			    //3(int)值入栈。
           3: iconst_5			    //5(int)值入栈。
           4: invokestatic  #2                  // Method add:(II)I
           7: istore_1			    //将栈顶int类型值保存到局部变量1中
           8: getstatic     #3                  // Field java/lang/System.out:Ljava/io/PrintStream;
          11: iload_1			    //从局部变量0中装载int类型值入栈。
          12: invokevirtual #4                  // Method java/io/PrintStream.println:(I)V
          15: return
    
      public static int add(int, int);
        Code:
           0: iconst_0			    //0(int)值入栈
           1: istore_2		            //将栈顶int类型值保存到局部变量1中
           2: iload_0			    //从局部变量0中装载int类型值入栈。
           3: iload_1			    //从局部变量1中装载int类型值入栈。
           4: iadd				    //将栈顶两int类型数相加，结果入栈。
           5: istore_2			    //将栈顶int类型值保存到局部变量2中
           6: iload_2
           7: ireturn
    }

对字节码有兴趣的请看：[https://blog.csdn.net/chegy218/article/details/86654990][https_blog.csdn.net_chegy218_article_details_86654990]  
![在这里插入图片描述][2019040910222186.png]

4，栈在表达式求值中的应用

算法：通过两个栈来实现，其中一个保存操作数的栈，另一个是保存运算符的栈，我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶运算进行比较。  
如果比运算符栈顶元素的优先级高，就将当期运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

5，栈在括号匹配的应用  算法：我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。  6，栈如何实现浏览器的前进，后退功能  算法：我们使用两个栈，X和Y，我们把首次浏览的页面依次压入栈X，当点击后退按钮时，再依次从栈X中取出数据，放入栈Y中。当我们点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，那说明没有页面可以继续后退浏览了。当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。

[https_blog.csdn.net_chegy218_article_details_86654990]: https://blog.csdn.net/chegy218/article/details/86654990
[2019040910222186.png]: /images/20220222/1ffcc6889bc7418f81f2f97255e338c0.png