查看原文
其他

三分钟基础知识:什么是栈?

不甘平凡的码农 帅地玩编程 2022-06-18

作者 |  小鹿

来源 |  一个不甘平凡的码农



写在前边


对于栈的认识,相信每个学习数据结构的小伙伴多多少少有一定的认识和了解。很多刚刚学习的小伙伴说学习数据结构在实际中没怎么见到应用,那是因为你没有去仔细的观察,而且像栈这常用到的数据结构通常会使用在实际开发中,比如:表达式的运算、花括号的匹配以及浏览器的前进后退等等很多。


这些实际开发的实现如果不去研究,你永远不知道数据结构在实际中的应用,当你学习完今天的栈数据结构时,然后去研究下实际中已经使用到的应用,才能让你在今后的实际开发中用到栈这种数据结构,从而使你的开发更加灵活、多变。


思维导图


这篇文章将要学习到的内容。


1

基本常识


1.1 什么是栈


我们用一种最简单的生活常识描述一下,比如我们往柜子里放东西,先放的东西是需要放到柜子最里边,后放的东西在柜子的最外边;如果我们要取东西,先要取柜子最外边的东西,才能取到柜子最里边的东西。这种先进后出,后进先出的结构称为“栈”。


1.2 栈的特点


“先进后出,后进先出”。


1.3 栈的操作


栈的操作就两种,分别为出栈和入栈。那我们上边的例子,我们往柜子里放东西的过程称为入栈;我们在柜子里拿东西的过程称为出栈。

PS:柜子只有一个出口和入口,而且出口和入口是一样的。如果两端都有开口,就变成了队列,后期的文章会讲到。


2

栈的实现


我们前边的文章也讲过,所有的数据结构基本都是由数组和链表演化而来的,所以今天讲的栈这种数据结构也不例外。


栈的实现主要有两种,一种是数组的实现,叫做顺序栈,另外一种是链表的实现,叫做链式栈。如下:


2.1 顺序栈



2.2 链表栈




3.2 代码实现


顺序栈(Java)

1/**
2 * 功能:基于数组的顺序栈
3 * @author:小鹿
4 *
5 */

6public class ArrayStack {
7
8   private String[] items;  // 数组
9   private int count;       // 栈中元素个数
10   private int n;           // 栈的大小
11
12   // 初始化数组,申请一个大小为 n 的数组空间
13   public ArrayStack(int n) {
14     this.items = new String[n];
15     this.n = n;
16     this.count = 0;
17   }
18
19   /**
20    * 功能:入栈
21    * 说明:数组入栈的入口为数组尾部
22    * @param item :入栈数据元素
23    * @return:是否入栈成功
24    */

25   public boolean push(String item) {
26     // 数组空间不够了,直接返回 false,入栈失败。
27     if (count == n) return false;
28     // 将 item 放到下标为 count 的位置
29     items[count] = item;
30     //数组长度+1
31     ++count;
32     //入栈成功
33     return true;
34   }
35
36   /**
37    * 功能:出栈
38    * @return:返回出栈元素
39    */

40   public String pop() {
41     // 栈为空,则直接返回 null
42     if (count == 0return null;
43     // 返回下标为 count-1 的数组元素
44     String tmp = items[count-1];
45     //数组长度-1
46     --count;
47     //返回出栈数据元素
48     return tmp;
49   }
50}


链式栈(Java)

1/**
2 * 功能:基本链表实现栈,入栈、出栈、输出栈
3 * @author : 小鹿
4 *
5 */

6public class StackBasedLinkedList {
7    //定义栈顶指针
8    private Node top = null;
9
10    //定义栈结点
11    private static class Node {
12        //栈结点数据域
13        private int data;
14        //栈结点指针域
15        private Node next;
16        //构造函数
17        public Node(int data, Node next) {
18          this.data = data;
19          this.next = next;
20        }
21        //get 获取数据域方法
22        public int getData() {
23          return data;
24        }
25    }
26
27    /**
28     * 功能:入栈
29     * @param value:要入栈的数据元素
30     */

31    public void push(int value) {
32        //创建一个栈结点 
33        Node newNode = new Node(valuenull);
34        // 判断栈是否为空
35        if (top == null) {
36          //如果栈为空,就将入栈的值作为栈的第一个元素
37          top = newNode;
38        } else {
39          //否则插入到top栈结点前(所谓的就是单链表的头插法)
40          newNode.next = top;
41          top = newNode;
42        }
43    }
44
45    /**
46     * 功能 : 出栈
47     * @return: -1 为栈中没有数据
48     */

49    public int pop() {
50        // 如果栈的最顶层栈结点为null,栈为空
51        if (top == nullreturn -1;
52
53        //否则执行出栈操作,现将栈顶结点的数据元素赋值给 Value
54        int value = top.data;
55        //将 top 指针向下移动
56        top = top.next;
57        //返回出栈的值
58        return value;
59    }   
60
61    /**
62     * 功能:输出栈中所有元素
63     */

64    public void printAll() {
65        //将栈顶指针赋值给p
66        Node p = top;
67        //循环遍历栈(遍历单链表)
68        while (p != null) {
69          System.out.print(p.data + " ");
70          //指向下一个结点
71          p = p.next;
72        }
73        System.out.println();
74    }
75}


3

栈的性能


我们从上边学到了栈的基本结构和特点,还有栈的基本操作。如果我们学习一种数据结构,主要分析它的性能如何。还记得怎么分析数据结构性能吗?主要从两方面入手,第一,时间效率(时间复杂度);第二,空间上的消耗(空间复杂度)。我们就从以上两个方面分析一下栈这种数据结构的性能。


3.1 时间复杂度


时间上的消耗主要分析栈的操作所消耗的时间,我们共两种操作,入栈和出栈,其实在数组中中,我们操作尾部的数据就相当于入栈和出栈,直接根据下标取得相应的元素就好(JS 中数组的 pop 和 push 方法),所以时间复杂度是 O(1)。


3.2 空间复杂度


空间复杂度的判断是所需要开辟的临时空间,顺序栈和链式栈只需要大小为 n 的空间就可以,入栈和出栈需要一个临时空间来存储变量,空间复杂度为 O(1)。


3.3 栈的动态扩容


大家有没有想过这样一种情况,如果栈满的时候,再进行入栈操作,栈内就放不下了,我们需要动态扩容。主要是顺序栈的动态扩容比较麻烦,和我么你之前的数组的文章动态扩容一样的,对于动态扩容的性能,可以自己尝试一下。可以根据之前的文章来分析《佩奇学编程 | 复杂度分析原来这么简单》。


4

栈的实际应用


既然我们把栈的性能分析透了,理解透了,那么我们看看栈在实际中有哪些应用吧。


4.1 应用一 :栈在函数中的应用


函数我们每个人再熟悉不过了,你是不是很纳闷,栈怎么会在函数中能够应用的到呢,我学了这几年函数,我咋不知道函数中还有栈的操作。


加入我们程序开始执行代码,执行到我们声明的函数时,计算机内部会发生什么呢?首先,会为该函数开辟一块临时的内存空间,这块内存空被组织成“栈”这种数据结构,作用主要用来存储函数内部声明的临时变量。


每执行一个函数,系统就将函数中的临时变量组织成栈帧,执行入栈操作,当函数被调用完成的时候,临时变量已经用不到了,所以要在内存中释放,执行出栈操作。如以下函数:


1function main(){
2   let i = 0;
3   let j = 1;
4   i++;
5   j++;
6   console.log(i+j)
7}
8main();


具体的动画如下:


我们这时要想一个问题,那为什么函数会使用栈这种数据结构呢,为什么不用队列、链表或者其他数据结构?全体注意,重点来了,以后分析其他的问题也用到一下的方法分析。


因为函数调用的执行顺序符合后进者先出,先进者后出的特点。


比如函数中的局部变量声明的时间顺序,早先定义的变量在内存中保存的时间长,后定义的变量在内存中保存的时间短,所有有一个先后的问题。我们再去脑海中把这种问题的特点抽象成数据结构,只有使用“栈”结构,才符合这种问题。


4.2 栈在表达式中应用


计算机中数字的运算也是使用栈这种数据结构的,我们举个例子,我们要计算如下表达式:

1 + 2 × 4 - 6

如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。动画如下(动图太大,我把它拆分成两部分了):


4.3 其他应用


关于栈的应用,还有很多,比如花括号的匹配问题,有关练习去 LeedCode 实践。这里就不多举例子。


推荐阅读

基础数据结构:【动画】如何轻松手写链表?

【被虐了】详解一次shopee面试算法题:最小栈的最优解

高频面试题:什么是B树?为啥文件索引要用B树而不用二叉查找树?


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存