算法与数据结构 - 栈详解

前言

点赞再看,养成习惯

---

引言

某一日,韩梅梅陪着李雷来到了市区里一家很有名气的射击馆打卡。射击过程中，韩梅梅突然对手中的手枪产生了兴趣。
韩梅梅： 李雷，你有没有发现我们每次上子弹的时候好奇怪啊。
李雷： 怎么了梅梅，是子弹有什么问题吗？
韩梅梅： 我发现每次我最先放入弹夹的子弹都是最后射出来的，反而我最后放入弹夹的子弹先发射了。
李雷： 你是怎么发现的？
韩梅梅： 因为我在弹壳上做了记号，奇怪的发现了弹夹的这种现象。
李雷： 这是很正常的哦，弹夹属于一种具有先入后出现象的容器，生活中具有这种特性的容器还是很多的，比如我们平时使用的纸箱，我们先放进去的物品通常都在纸箱的最下面，最后才能取出。而在计算机课上我记得，也有一种类似的数据结构，好像叫做栈 。
韩梅梅： 哇，李雷你好厉害啊。

一、栈简介

1.1 什么是栈？

栈属于线性表的一种，其内部呈线性排列，这也意味着栈拥有着线性表常见的两种特性：

1. 栈中保存的元素应该是有序的
2. 栈中保存的元素应该存在某种特性的相同

不过栈相较于常见的线性表也有一些区别：

1. 栈虽然有序，但是我们只能优先访问最新添加的数据，就像是一摞书，我们取书时永远会先拿到最后放上去的书。

一句话总结栈就是：具有先入后出特性的线性表结构。

1.2 图话栈

我们假设此时有一个细长的罐子和几块大小相同的积木:

此时我们要做的就是将这些积木一次的放入盒子中:

然后我们观察现象:

1. 明明是最先放入盒子中的1号积木却是位于盒子的最低侧
2. 如果我们想要取出元素,最先取出的却是最后进入的5号积木

这种现象就是栈的重要特性:先入后出。

像是栈这种最后添加的元素最先被取出,即’后进先出’的结构,我们成为Last In First Out ,简称LIFO。
与链表和数组一样，由于栈也是线性表的一种，因此它的元素也是有序的。但是在栈中，添加和删除元素的操作只能够在一端进行，访问数据也只能访问到顶端的数据。想要访问栈的中间数据时，就必须通过出栈操作将目标数据移到栈顶才可以。

这里补充的说一下，栈的先入后出特性及只能访问栈顶元素的操作看起来似乎是十分的不方便，但是只要我们想要获取的是最新元素的时候，使用起来是不是就很合理了。就比如我们要做一个评论区系统，排序规则是按照发布时间最新优先的规则排序，是不是使用栈结构是最合适的呢？

---

二、手撕栈结构

了解完栈的基础特性，我们接下来要做的就是通过代码一步一步的实现一个栈结构。
注： 本节最后有完整代码

2.1 基础的存储结构

我们首先要做的是设计一个可以存储元素的结构，这个结构要符合以下特点：

1. 可以存储含有相同特点的元素
2. 元素之间存在顺序
3. 可以吻合先入后出的特性

让我们来实现下：

/**
 * @Classname MyStack 栈
 * @Description 模拟栈结构
 * @Date 2022/10/20 10:47
 * @Created by 晓龙Oba
 */
public class MyStack<T> {
    // 通过数组充当内存容器
    private Object[] pot;
    // 栈顶指针
    private Integer topIndex = 0;
    // 最大元素数量
    private Integer max_counts = 5;

    public MyStack() {
        pot = new Object[max_counts];
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.2 压栈操作

由于我们使用的是数组充作栈的底层容器结构，因此我们就需要考虑当数组满了时候的扩容场景。

    public void push(T element) {
        // 判断此时的栈是否已经满了
        if (topIndex >= max_counts) {
            // 扩容
            max_counts = max_counts * 2;
            pot = Arrays.copyOf(pot, max_counts);
        }
        // 元素压栈
        pot[topIndex++] = element;
    }
1
2
3
4
5
6
7
8
9
10

2.3 弹栈（获取元素）

弹栈时注意栈顶指针的变化，没有元素时应及时报错。

    public T pop() {
    	//栈顶指针后移
        topIndex--;
        // 校验是否超出栈空间范围
        if (topIndex < 0) {
            throw new IndexOutOfBoundsException("超出栈空间");
        }
        // 完成弹栈操作
        T temp = (T) pot[topIndex];
        pot[topIndex] = null;
        return temp;
    }
1
2
3
4
5
6
7
8
9
10
11
12

2.4 完整代码

一个具有简易的入栈出栈操作的栈结构就完成了：

/**
 * @Classname MyStack 栈
 * @Description 模拟栈结构
 * @Date 2022/10/20 10:47
 * @Created by 晓龙Oba
 */
public class MyStack<T> {
    // 通过数组充当内存容器
    private Object[] pot;
    // 栈顶指针
    private Integer topIndex = 0;
    // 最大元素数量
    private Integer max_counts = 5;

    public MyStack() {
        pot = new Object[max_counts];
    }


    public void push(T element) {
        // 判断此时的栈是否已经满了
        if (topIndex >= max_counts) {
            // 扩容
            max_counts = max_counts * 2;
            pot = Arrays.copyOf(pot, max_counts);
        }
        pot[topIndex++] = element;
    }

    public T pop() {
        //栈顶指针后移
        topIndex--;
        // 校验是否超出栈空间范围
        if (topIndex < 0) {
            throw new IndexOutOfBoundsException("超出栈空间");
        }
        // 完成弹栈操作
        T temp = (T) pot[topIndex];
        pot[topIndex] = null;
        return temp;
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder("当前栈内元素有:");
        Arrays.stream(pot).forEach(item -> {
            if (item != null) {
                result.append("\r\n" + item);
            }
        });
        return result.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

---

三、算法实战

3.1 包含min函数的栈

需求描述：
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

原题地址： https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/

题解思路：
这个题我们无需纠结怎么去实现一个栈，一方面我们刚刚已经实现了一个具有push，pop能力的栈结构。另一方面这道题的考察点其实是如果获取当前栈内的最小元素。由于它要求每一个函数的时间复杂度为O(1),这就限制了我们无法直接通过遍历容器获得最小值。那我们该怎么办呢？
辅助栈是解决这个问题的最简单手段，所谓的辅助栈就是在元素每一次入栈出栈的时候同时为辅助栈同步元素的变动。不过辅助栈与我们的主栈不同，辅助栈每次push的时候都是仅放入当前最小值，这样辅助栈其实记录的就是每一个阶段栈空间的最小值，如果小伙伴们有不明白的，可以参考下图：

代码实现：

package info.xiao.dataStructrue.stack;

import java.util.Stack;

/**
 * @Classname MinStack 包含min函数的栈
 * @Description : https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
 * @Date 2022/10/20 14:40
 * @Created by 晓龙Oba
 */
public class MinStack {
    // 通过数组充当内存容器
    private Stack<Integer> pot = new Stack<>();
    // 栈顶指针
    private Integer topIndex = 0;
    // 最大元素数量
    private Integer max_counts = 5;

    private Stack<Integer> minStack = new Stack<>();

    /**
     * initialize your data structure here.
     */
    public MinStack() {

    }

    public void push(int x) {
        if (pot.isEmpty()) {
            pot.push(x);
            minStack.push(x);
        } else {
            pot.push(x);
            minStack.push(minStack.peek() < x ? minStack.peek() : x);
        }
    }

    public void pop() {
        pot.pop();
        minStack.pop();
    }

    public int top() {
        return pot.peek();
    }

    public int min() {
        return minStack.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

运行结果：

---

3.2 栈排序

需求描述：
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

原题地址： https://leetcode.cn/problems/sort-of-stacks-lcci

题解思路：
这题和上题类似,栈的题解我们需要第一个想到的就是辅助栈,这里也不意外,我们只需要将主栈在存入时候进行判断,若小于当前元素则直接放置于栈顶,若大于当前元素则将栈中元素取出后放入辅助栈,依次向下比较即可:

代码实现：
这里重点关注push方法

/**
 * @Classname SortedStack 栈排序
 * @Description 链接：https://leetcode.cn/problems/sort-of-stacks-lcci/
 * @Date 2022/10/20 15:52
 * @Created by 晓龙Oba
 */


public class SortedStack {
    private Stack<Integer> mainStack;
    private Stack<Integer> surportStack;

    public SortedStack() {
        this.mainStack = new Stack<>();
        this.surportStack = new Stack<>();
    }

    public void push(int val) {
        // 判断元素大小
        while (!mainStack.isEmpty()) {
            Integer pop = mainStack.pop();
            if (val < pop) {
                mainStack.push(pop);
                break;
            }
            surportStack.push(pop);
        }
        mainStack.push(val);
        while (!surportStack.isEmpty()) {
            mainStack.push(surportStack.pop());
        }
    }

    public void pop() {
        try {
            mainStack.pop();
        } catch (Exception e) {
        }
    }

    public int peek() {
        try {
            return mainStack.peek();
        } catch (Exception e) {
            return -1;
        }
    }

    public boolean isEmpty() {
        return mainStack.isEmpty();
    }


    public String[] execute(String[] instruction, Integer[] variable) {

        String[] result = new String[instruction.length];
        for (int i = 0; i < instruction.length; i++) {
            if (i == 29) {
                System.out.println("");
            }
            switch (instruction[i]) {
                case "SortedStack":
                    result[i] = "null";
                    break;
                case "peek":
                    result[i] = this.peek() + "";
                    break;
                case "pop":
                    this.pop();
                    result[i] = "null";
                    break;
                case "isEmpty":
                    result[i] = this.isEmpty() + "";
                    break;
                case "push":
                    this.push(variable[i]);
                    result[i] = "null";
                    break;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SortedStack sortedStack = new SortedStack();
        String[] instruction = {
                "SortedStack", "peek", "peek", "pop", "isEmpty", "peek", "push", "pop", "push", "peek", "push", "peek", "pop", "pop", "push", "isEmpty", "push", "peek", "isEmpty", "push", "peek", "peek", "isEmpty", "push", "isEmpty", "peek", "isEmpty", "pop", "peek", "pop", "push", "push", "isEmpty", "pop", "isEmpty", "peek", "push", "pop", "push", "push", "isEmpty", "pop", "pop", "push", "peek", "isEmpty", "pop", "peek", "push", "push", "peek", "isEmpty", "isEmpty", "isEmpty", "isEmpty", "isEmpty", "push", "push", "push", "push", "push", "peek", "peek", "isEmpty", "push"
        };
        Integer[] variable = {0, 0, 0, 0, 0, 0, 40, 0, 19, 0, 44, 0, 0, 0, 42, 0, 8, 0, 0, 29, 0, 0, 0, 25, 0, 0, 0, 0, 0, 0, 52, 63, 0, 0, 0, 0, 47, 0, 45, 52, 0, 0, 0, 17, 0, 0, 0, 0, 6, 30, 0, 0, 0, 0, 0, 0, 51, 46, 2, 56, 39, 0, 0, 0, 38};
        String[] execute = sortedStack.execute(instruction, variable);
        Arrays.stream(execute).forEach(item -> {
            System.out.print(item + ",");
        });
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

---

结语

今天的内容就到此结束了，有疑问的小伙伴欢迎评论区留言或者私信博主，博主会在第一时间为你解答。
Leetcode刷题攻略已上传到gitee仓库，需要的小伙伴们可以自取：
https://gitee.com/xiaolong-oba/algorithm-and-data-structure

码字不易，感到有收获的小伙伴记得要关注博主一键三连，不要当白嫖怪哦~
如果大家有什么意见和建议请评论区留言或私聊博主，博主会第一时间反馈的哦。