疯狂数据结构-栈-Java

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家， 跳转到网站

概念

基本概念解读

当谈到 "栈" 时，它是一种遵循后进先出（Last In, First Out，LIFO）原则
的有序集合。这意味着最后入栈的元素首先被弹出，而最早入栈的元素最后被弹
出。
在栈中，只能对最上面的元素进行操作，其他元素都不可见，需要将上面的元素
先出栈才能访问到其他元素。
1
2
3
4
5

基本操作分析

栈的基本操作包括入栈（push）和出栈（pop）。入栈指的是向栈中添加一个元
素，使其成为新的栈顶；而出栈指的是移除栈顶的元素，使得下一个元素成为新
的栈顶。此外，还可以通过栈顶元素的读取（top）来查看当前栈顶的值，以及
判断栈是否为空（empty）。
1
2
3
4

基本操作总结

入栈（Push）：将一个元素放入栈的顶部。
出栈（Pop）：从栈的顶部移除一个元素，并将其返回。
获取栈顶元素（Top）：返回栈的顶部元素，但不对栈进行修改。
判空（isEmpty）：检查栈是否为空。
获取栈的大小（getSize）：返回栈中元素的个数。
1
2
3
4
5

应用分析

实际应用分析

栈的应用相当广泛，例如函数的调用栈、浏览器的前进后退功能和计算器的后缀
表达式求值等等。在算法设计中，栈也常用于解决问题，如深度优先搜索和括号
匹配等。
1
2
3

实际应用场景

表达式求值：栈可用于将中缀表达式转换为后缀表达式，并对其进行求值。运算
符和操作数依次入栈，直到遇到更高优先级的运算符。这时，先前的运算符必须
先出栈。
递归算法：递归算法通常使用栈来实现，因为递归函数的调用过程本质上也是一
个栈结构，每次递归调用都会将当前函数的局部变量和返回地址保存在栈上。

浏览器历史记录：浏览器使用栈来跟踪用户访问不同网页的历史记录。每当用户
访问一个新页面时，该页面被推入栈中。通过后退操作，最近访问的页面会从栈
中弹出。

函数调用：函数调用通常使用栈来管理函数的调用顺序和返回地址。每当一个函
数被调用时，其相关信息（参数、局部变量等）会被压入栈，函数执行完成后将
被弹出。

撤销操作：编辑器、文本处理软件等应用中，栈可以用于实现撤销操作。每次对
文本进行修改时，相关的操作记录会被压入栈中，在用户需要撤销操作时，可以
从栈中弹出最近的修改记录，实现撤销功能。

浏览器的浏览历史：浏览器通过使用栈来记录用户的浏览历史。每当用户访问一
个新的网页时，该网页的 URL 被推入栈中，当用户点击“后退”按钮时，最近访
问的网页 URL 被弹出栈。

括号匹配：栈可以用于检查表达式中的括号是否匹配。遍历表达式，将左括号压
入栈中，当遇到右括号时，检查栈顶的左括号是否与之匹配，若匹配则继续。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

需要注意的是，在使用栈时要避免两个常见的问题：栈上溢（stack overflow）和栈下溢（stack underflow）。栈上溢发生在尝试向已满的栈中插入元素时，而栈下溢发生在尝试从空栈中弹出元素时。

注意事项

基本注意事项

栈的初始化：在使用栈之前，需要对栈进行初始化，即为栈分配一定大小的内存
空间，并将栈的指针指向栈底。如果栈的大小事先不确定，可以动态调整栈的大
小。

入栈操作：在进行入栈操作时，需要注意判断栈是否已满。如果栈已满，则需要
进行相应的处理，如扩充栈的空间或者报错。入栈时要确保栈的指针指向栈顶，
并将要入栈的数据放入栈顶位置，同时栈顶指针要更新。

出栈操作：在进行出栈操作时，需要判断栈是否为空。如果栈为空，则需要进行
相应的处理，如报错或者返回特定的值。出栈时要确保栈的指针指向栈顶元素，
取出栈顶元素后，栈顶指针要更新。

栈的访问：栈是一种后进先出的数据结构，因此只能访问栈顶元素，无法直接访
问栈中的其他元素。如果需要访问栈中的其他元素，需要先将栈顶元素出栈，然
后再入栈其他元素，或者使用辅助栈进行操作。

栈的容量控制：由于栈的大小是有限的，对于大量数据的处理，需要合理控制栈
的容量，避免过多的数据存储在栈中，以免造成栈溢出或者浪费内存的问题。可
以根据具体需求，设定一个合适的栈的容量上限，并在入栈操作时判断栈是否超
过容量上限。

异常处理：在使用栈的过程中，可能会出现一些异常情况，如栈溢出、空栈出栈
等。需要进行异常处理，如使用try-catch语句来捕获异常并进行相应的处理。
避免程序崩溃或者逻辑错误。

内存管理：在使用栈的过程中，需要合理地管理栈的内存。当不再需要使用栈时，
需要及时释放栈所占用的内存空间，以避免内存泄漏问题。

栈的大小限制：栈的大小是有限的，具体取决于操作系统和计算机硬件的限制。
在使用栈的过程中，需要确保栈不会溢出。当递归层数过深或者栈中的数据量
过大时，可能会导致栈溢出的问题。

入栈和出栈的顺序：栈是一种遵循"先入后出"原则的数据结构，因此在进行入栈
和出栈操作时，需要确保顺序正确，否则可能会导致程序逻辑错误。

栈的线程安全性：多线程环境下，如果多个线程同时使用同一个栈，可能会导致
线程安全的问题。需要通过合适的同步机制来保证栈的操作的线程安全性，例如
使用互斥锁或者信号量等。
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

理论总结

总结来说，栈是一种简单而重要的数据结构，具有广泛的应用场景。掌握栈的基
本操作和实现方式对于理解和应用许多问题都非常有帮助。
1
2

代码实现

思路分析

栈的实现可以使用数组或链表等数据结构。在数组中，栈的底部通常对应数组的
起始位置，栈的顶部对应最后一个元素；而在链表中，栈的顶部对应链表的首个
元素。
1
2
3

常规操作

import java.util.EmptyStackException;

public class Stack {
    private int[] stackArray;
    private int top;
    private int minElement; // 记录栈的最小值
    
    // 构造函数，初始化栈
    public Stack(int capacity) {
        stackArray = new int[capacity];
        top = -1; // 栈顶指针初始化为-1，表示栈为空
        minElement = Integer.MAX_VALUE; // 最小值初始化为正无穷大
    }
    
    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }
    
    // 判断栈是否已满
    public boolean isFull() {
        return top == stackArray.length - 1;
    }
    
    // 入栈操作
    public void push(int data) {
        if (isFull()) {
            throw new StackOverflowError("Stack is full");
        }
        if (data < minElement) {
            // 更新最小值
            minElement = data;
        }
        stackArray[++top] = data;
    }
    
    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        int data = stackArray[top];
        if (data == minElement) {
            // 如果出栈的元素是最小值，更新最小值
            updateMinElement();
        }
        top--;
        return data;
    }
    
    // 获取栈顶元素
    public int top() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return stackArray[top];
    }
    
    // 获取栈的大小
    public int size() {
        return top + 1;
    }
    
    // 清空栈
    public void clear() {
        top = -1;
        minElement = Integer.MAX_VALUE;
    }
    
    // 获取栈的最小值
    public int getMin() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return minElement;
    }
    
    // 判断栈是否存在某个元素
    public boolean contains(int data) {
        for (int i = 0; i <= top; i++) {
            if (stackArray[i] == data) {
                return true;
            }
        }
        return false;
    }
    
    // 更新最小值
    private void updateMinElement() {
        minElement = Integer.MAX_VALUE;
        for (int i = 0; i <= top; i++) {
            if (stackArray[i] < minElement) {
                minElement = stackArray[i];
            }
        }
    }
}
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

上面代码中
	获取栈的最小值的操作 getMin() 和判断栈是否存在某个元素的操作 
	contains()。在 push() 方法中，新增了对栈的最小值的更新操作，
	以便在出栈时更新最小值。在 pop() 方法中，将出栈的元素与最小值
	进行比较，如果相等，则更新最小值。 updateMinElement() 方法用
	于更新最小值，它会遍历栈中的元素以找到最小值。
1
2
3
4
5
6

实际应用

public class ArrayStack {
    private Object[] arra
   y;
    private int top;
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.array = new Object[capacity];
        this.top = -1;
    }

    public void push(Object element) {
        if (top == capacity - 1) {
            throw new StackOverflowError("Stack is full");
        }
        top++;
        array[top] = element;
    }

    public Object pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        Object element = array[top];
        array[top] = null;
        top--;
        return element;
    }

    public Object top() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int getSize() {
        return top + 1;
    }
}
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

调用上面代码
1

public static void main(String[] args) {
    ArrayStack stack = new ArrayStack(3);
    stack.push("A");
    stack.push("B");
    stack.push("C");

    System.out.println("Size: " + stack.getSize()); // 输出：Size: 3

    System.out.println(stack.pop()); // 输出：C
    System.out.println(stack.top()); // 输出：B

    System.out.println(stack.isEmpty()); // 输出：false

    stack.push("D");
    System.out.println(stack.pop()); // 输出：D
    System.out.println(stack.pop()); // 输出：B
    System.out.println(stack.pop()); // 输出：A

    System.out.println(stack.isEmpty()); // 输出：true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这个代码演示了使用数组实现的栈的基本操作。你可以根据需要进行进一步扩展和优化，例如，使用链表实现栈，或实现其他更高级的功能。