疯狂数据结构-栈-Java

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

概念

基本概念解读

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

基本操作分析

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

基本操作总结

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

应用分析

实际应用分析

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

实际应用场景

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

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

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

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

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

括号匹配：栈可以用于检查表达式中的括号是否匹配。遍历表达式，将左括号压
入栈中，当遇到右括号时，检查栈顶的左括号是否与之匹配，若匹配则继续。

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

注意事项

基本注意事项

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

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

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

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

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

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

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

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

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

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

理论总结

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

代码实现

思路分析

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

常规操作

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];
            }
        }
    }
}

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

实际应用

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;
    }
}

调用上面代码

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
}

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