数据结构（栈Stack）

1.前言：

在计算机科学中，栈（Stack）是一种基础而存在的数据结构，它的核心特性是后进先出（LIFO，Last In, First Out）。想象一下，在现实生活中我们如何处理一堆托盘——我们总是将新托盘放在最上面，而取托盘时则从最上面开始，这正好与托盘的操作方式相吻合。

栈的简单结构和高效的操作，使得在许多计算机程序和算法中扮演关键的角色。从方法调用、递归过程到表达求值、短语匹配，栈几乎暗示在。只允许在前置插入和删除元素的数据结构，不仅能简化问题的高效初始化过程，还能提供的性能，尤其是在处理需要回溯和深度优先搜索的问题时，堆栈外形更架构。

无论是Smashing初学者还是丰富的开发者，理解Stack的工作原理及其应用，都是构建健壮软件系统的基础。本文将深入探讨Stack的概念、操作以及应用场景，并通过实例经验演示如何在Java中中实现和使用栈。让我们一起来走进这个简单但强大的数据结构，了解它在实际编程中的巨大价值。

2.讲解栈：

2.1概念：

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据在栈顶。

2.2栈的使用：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(10); // 入栈
        stack.push(20); // 入栈
        stack.push(30); // 入栈

        System.out.println("Top of the stack: " + stack.peek()); // 查看栈顶元素 (30)

        System.out.println("Popped element: " + stack.pop()); // 弹出栈顶元素 (30)

        System.out.println("Is stack empty? " + stack.isEmpty()); // 判断栈是否为空 (false)

        System.out.println("Size of stack: " + stack.size()); // 查看栈大小 (2)
    }
}

2.3 栈的模拟实现：

1.实现栈前的模拟：

1.private int[] elem;

这行代码声明了一个容器的整型仓库elem，它用于存储栈中的元素。在栈中，我们需要一个容器来保存被压入栈的值，因此这里选择了一个仓库。

类型：int[]表示这是一个队列，用于存储栈中的数据。
访问控制：private关键字表示该队列只能在MyStack类内部访问，外部无法直接访问。

2.private int usedSize;

这行代码声明了一个原始的整型变量usedSize，它用来记录栈中当前存储的元素个数。

类型：int，用于表示栈中当前的元素个数。
访问控制：private关键字使得usedSize只能在MyStack类内部访问，外部无法直接修改或读取。

3.private static final int DEFAULT_SIZE = 10;

这行代码定义了一个常量DEFAULT_SIZE，它表示栈的最终容量，默认为 10。

类型：int，表示栈的容量大小。
访问控制：private关键字表示常量只能在MyStack类内部使用。
修饰符：
static：意味着该常量是类级别的，而不是实例级别的。那么，所有MyStack类的实例共享这个常量。
final：表示这个常量的值一旦被赋值后就不能修改。
作用：为栈的初始大小提供一个默认值。如果没有指定栈的大小，栈的容量将默认为10。

4.public MyStack() {

这是MyStack类的构造方法。构造方法是类的实例化时调用的特殊方法，用于初始化对象的状态。

访问控制：public关键字表示构造方法可以被外部类访问，否则允许通过构造方法创建MyStack的实例。
方法名：构造方法的名称是MyStack，与类名相同。

5.elem = new int[DEFAULT_SIZE];

在构造方法的主体中，这行代码用于初始化elem内存。

队列初始化：new int[DEFAULT_SIZE]创建了一个大小为DEFAULT_SIZE（即10）的内存队列，并赋予其赋值elem。这表示堆栈一开始的容量为10。
：栈的最终容量设为10，当栈中的元素数量小于10时，栈能够承载更多元素。当元素数量超过10时，通常会触发动态扩容。

这需要构造方法的结束。构造方法结束后，MyStack类的实例会完成初始化，可以开始使用栈。

2.push添加元素：

public void push(int val) {

访问控制：public 关键字表示这个方法可以被外部类调用，允许用户向栈中添加元素。
方法名：push 是栈数据结构中的常见操作，用于向栈中添加元素。
参数：int val 是栈要添加的元素，它表示一个整数，用户希望将其压入栈中。
返回类型：void 表示这个方法没有返回值。

2. if (isFull()) {

这行代码检查栈是否已满。isFull() 是一个方法，通常用来判断栈是否达到了最大容量。

isFull()：我们可以推测它的作用是判断栈的当前容量是否已满。可能的实现方式是检查 usedSize 是否等于栈的当前容量 elem.length。如果栈已满，则 isFull() 返回 true，否则返回 false。

3.grow();

这是一个调用 grow() 方法的语句，意味着当栈满时，栈将扩容。grow() 是扩展栈容量的操作。
扩容操作：在栈满时，我们需要增加栈的容量，通常是通过创建一个更大的数组，并将原数组的元素复制到新的数组中。扩容后，栈可以容纳更多的元素。

4. elem[usedSize] = val;

这行代码将 val 插入到栈顶。具体来说，它将 val 赋值给 elem[usedSize]，即将 val 存储到当前栈的下一个可用位置。
usedSize：在栈未满时，usedSize 表示栈中已经存储的元素个数，它也可以用作 elem 数组的下标。当插入一个新元素时，usedSize 会指向栈的顶部元素的位置。
栈的压栈操作是通过把元素存储在 elem[usedSize] 来实现的，然后 usedSize 自增，表示栈中元素个数增加了。

5. usedSize++;

这行代码执行后，usedSize 增加 1，表示栈中元素个数增加了一个。
usedSize：这个变量用于追踪栈中实际存储的元素数量。每当我们向栈中压入一个元素时，usedSize 就会递增，以保证在后续操作中可以准确地知道栈的大小。

3.pop删除元素：

1.public int pop()：

访问控制：public 表示这个方法对外可见，可以被其他类调用。
返回类型：int，表示该方法返回一个整数，即栈顶的元素值。
方法名：pop 是栈的基本操作之一，表示从栈顶移除元素并返回被移除的元素。

2. if (isEmpty()) {

在执行 pop 操作之前，方法会首先检查栈是否为空，防止对空栈执行弹栈操作。
isEmpty() 方法：这个方法通常用于判断栈是否为空。可能的实现逻辑是检查 usedSize 是否为 0：

3. throw new RuntimeException();

如果栈为空，直接抛出一个 RuntimeException。
异常的目的：防止非法操作（即对空栈执行弹栈操作）。这种设计能够提醒用户修复程序中潜在的问题。
替代方案：注释中的代码显示了一种替代方式，即返回一个特殊值（如 -1）来表示操作失败。然而，抛出异常更加严谨，因为返回特殊值可能导致逻辑混淆（-1 可能与有效数据冲突）。

4. usedSize--;

这行代码将 usedSize 减 1，表示栈中元素的数量减少了一个。
减少后的作用：
usedSize 减少后，指向的索引位置就是被弹出的元素的索引。
elem[usedSize] 表示当前栈顶的元素。

5. return elem[usedSize];

返回当前栈顶元素，即 elem[usedSize]。
逻辑：
由于前面已经执行了 usedSize--，此时 usedSize 的值指向的是刚刚被移除的栈顶元素所在的索引。
直接返回 elem[usedSize]，实现弹栈并返回被移除的元素。

4.获取栈顶元素但是不删除当前元素peek

1.public int peek()

访问控制：public 表示该方法对外可见，允许外部代码调用。
返回类型：int，表示该方法返回一个整数，即栈顶的元素值。
方法名：peek，这是栈数据结构中的常见操作，用于查看栈顶元素而不改变栈的状态。

2. if (isEmpty()) {

在执行 peek 操作之前，方法首先检查栈是否为空，以防止在空栈上进行不合法的操作。
isEmpty() 方法：判断栈是否为空。通常的实现方式是检查 usedSize 是否为 0：

3. throw new RuntimeException();

如果栈为空，抛出一个 RuntimeException。

异常处理：抛出异常意味着对空栈执行 peek 操作是非法的，并且程序会抛出一个运行时异常来提醒用户。这样可以防止程序在不正确的状态下继续运行。

这种方式相较于返回特殊值（如 -1）更为严谨，因为返回 -1 可能会与有效的数据冲突，导致逻辑错误。

4. return elem[usedSize - 1];

这行代码返回栈顶元素的值，但并不移除该元素。
usedSize - 1：栈的大小 usedSize 表示栈中当前有效元素的个数。由于数组索引从 0 开始，因此栈顶的元素位于 usedSize - 1 的索引位置。例如：
如果栈有 3 个元素，usedSize = 3，栈顶元素的位置是 elem[2]，即 usedSize - 1。
通过返回 elem[usedSize - 1]，我们能够获取栈顶的元素值，而不影响栈的内容。

5.返回栈大小：

返回 usedSize：usedSize 是一个成员变量，用于记录栈中当前元素的数量。当我们创建栈时，usedSize 从 0 开始，随着元素的压栈操作（push）而增加，随着弹栈操作（pop）而减少。
因此，size 方法返回的就是栈当前的有效元素个数，也就是 usedSize 的值。

2.4 完整代码展示：

import java.util.Arrays;

public class MyStack {

    private int[] elem;
    private int usedSize;
    private static final int DEFAULT_SIZE = 10;

    public MyStack() {
        elem = new int[DEFAULT_SIZE];
    }

    //存储数据
    public void push(int val) {
        if(isFull()) {
            //扩容
            grow();
        }
        elem[usedSize] = val;
        usedSize++;
    }
    private void grow() {
        elem = Arrays.copyOf(elem,elem.length);
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }

    //删除数据
    public int pop() {
        if(isEmpty()) {
            //return -1;
            throw new RuntimeException();
        }
        usedSize--;
        return elem[usedSize];
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    //获取栈顶元素 但是不删除当前元素
    public int peek() {
        if(isEmpty()) {
            //return -1;
            throw new RuntimeException();
        }
        //usedSize--;
        return elem[usedSize-1];
    }

    public int size() {
        return usedSize;
    }

}

2.5栈的使用场景

方法调用栈（堆栈） Java中的方法调用栈是由虚拟机（JVM）管理的栈空间。当一个方法被调用时，JVM 会在栈中为该方法分配一个栈帧，用于存储方法的局部变量、操作数栈、返回地址等信息。方法执行完毕后，栈帧会被销毁。
表达式求值 栈在算术表达式求值中非常重要。例如，在中缀表达式转后缀表达式时，栈用来保存运算符，并且根据运算符的优先级来控制栈中的内容。
回溯算法 在深度优先搜索（DFS）算法和回溯算法中，栈用于存储递归过程中的状态信息。
括号匹配 在编程中，检查一段代码中的括号是否匹配也可以通过栈来实现。遇到左括号时入栈，遇到右括号时出栈。如果栈为空或括号不匹配，则说明括号不合法。

2.6栈的优缺点

优点：

高效性：栈的插入和删除操作是常数时间操作（O(1)），不需要查找、排序等复杂操作。
简洁性：栈的操作非常简单，只有栈顶访问，避免了复杂的数据结构管理。
适用性强：栈可以用来解决许多常见的算法问题，如括号匹配、回溯算法、递归、深度优先搜索等。

缺点：

访问受限：栈只能访问栈顶的元素，无法直接访问栈中的其他元素。对于需要随机访问的场景，栈就不太合适。
空间限制：栈的大小通常是有限的，如果栈的空间耗尽（比如在递归调用时），会导致栈溢出（StackOverflowError）。

3.栈的拓展方法：

1.toArray（）将栈转换为一个数组，方便进行其他操作或输出栈的内容。

public int[] toArray() {
return Arrays.copyOf(elem, usedSize); // 返回栈中有效部分的数组
}

返回值：返回一个数组，包含栈中的所有元素。
功能：将栈的内容转换为数组。
复杂度：时间复杂度 O(n)，需要遍历栈中的元素并将其复制到数组中。

比较重要所以详细讲解：

Arrays.copyOf(elem, usedSize)：
- Arrays.copyOf() 是 Java 提供的一个静态方法，它可以复制一个数组的前几个元素到新的数组中。这里它将 elem 数组中从索引 0 到 usedSize - 1 的所有元素复制到一个新的数组。
- elem 是栈的存储数组，它的长度可能大于当前栈的实际元素个数（usedSize）。
- usedSize 表示栈中当前存储的元素个数，因此我们只需要复制前 usedSize 个元素。
- copyOf 方法返回一个新的数组，包含栈中当前的所有有效元素。

为什么使用 `Arrays.copyOf`？

Arrays.copyOf() 方法能够处理数组的拷贝，并自动管理目标数组的大小。它会创建一个新的数组，并将原数组的元素复制到新数组中。
使用 copyOf 的好处是可以确保不会出现数组越界问题，而且代码简洁。

4. 方法返回值

toArray() 方法返回的是一个新的数组，其中包含栈中当前所有的元素。返回值的类型是 int[]，也就是一个整型数组。

例如，假设栈中有以下元素：

elem = [10, 20, 30, 0, 0]
usedSize = 3

调用 toArray() 后，会返回一个包含栈中前 3 个元素的新数组：

返回的数组：[10, 20, 30]

5. 使用场景

toArray() 方法主要用于以下几种场景：

输出栈内容：有时需要输出栈的内容，toArray() 可以将栈元素转换成数组，然后方便地打印或者操作。
与其他API交互：有些算法或库可能需要将栈转换为数组进行处理。toArray() 可以方便地将栈的元素传递给这些函数。
复制栈内容：如果需要保持栈的副本，或者用于历史数据的存储时，toArray() 会返回一个包含栈元素的数组副本。

6. 时间复杂度分析

时间复杂度：Arrays.copyOf(elem, usedSize) 会复制 usedSize 个元素，因此时间复杂度为 O(n)，其中 n 是栈中当前元素的个数。
空间复杂度：toArray() 会创建一个新的数组，因此空间复杂度是 O(n)，其中 n 是栈中元素的个数。

7. 与其他集合类的对比

toArray() 是将栈中的元素转换为数组的常见方法。与其他集合类（如 ArrayList、LinkedList 等）中的 toArray() 方法类似，栈的 toArray() 方法返回一个包含当前栈元素的数组。不过，栈通常是一个基于数组或动态数组的实现，因此 toArray() 返回的数组通常是连续存储的，和数组的顺序一致。

8. 示例使用

假设我们使用 MyStack 类来测试 toArray() 方法：

import java.util.Stack;
import java.util.Arrays;

public class StackToArrayExample {
    public static void main(String[] args) {
        // 创建一个栈对象
        Stack<Integer> stack = new Stack<>();

        // 使用 push() 方法压入元素
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        // 打印栈内容
        System.out.println("栈的内容（通过 printStack() 方法查看）：");
        for (Integer item : stack) {
            System.out.print(item + " ");
        }
        System.out.println();

        // 使用 toArray() 方法将栈转换为数组
        Integer[] array = stack.toArray(new Integer[0]);

        // 打印转换后的数组
        System.out.println("栈转换成的数组：");
        System.out.println(Arrays.toString(array)); // 输出：[10, 20, 30, 40, 50]

        // 弹出栈顶元素
        stack.pop();

        // 再次打印栈转换成的数组
        array = stack.toArray(new Integer[0]);
        System.out.println("栈弹出一个元素后的数组：");
        System.out.println(Arrays.toString(array)); // 输出：[10, 20, 30, 40]
    }
}

2.contains()判断栈中是否包含指定的元素。

public boolean contains(int value) {
    for (int i = 0; i < usedSize; i++) {
        if (elem[i] == value) {
            return true;
        }
    }
    return false;
}

功能：检查栈中是否包含某个元素。通常需要遍历栈中的元素。
复杂度：时间复杂度 O(n)，因为需要遍历栈中的所有元素。
使用场景：当你需要判断栈中是否存在特定元素时使用。

3. peekAt(int index)返回栈中指定位置的元素，不修改栈的状态。

public int peekAt(int index) {
    if (index < 0 || index >= usedSize) {
        throw new IndexOutOfBoundsException("Index out of bounds");
    }
    return elem[index];
}

功能：返回栈中指定索引位置的元素。这里的索引是栈内的相对位置，不是从栈顶开始的。
复杂度：时间复杂度 O(1)。
使用场景：可以用来查看栈中某个特定位置的元素。需要注意的是，它不保证返回栈顶元素，而是指定索引位置的元素。

4. reverse()将栈中的元素反转。这个操作通常修改栈的顺序。

public void reverse() {
    int[] reversed = new int[usedSize];
    int j = 0;
    for (int i = usedSize - 1; i >= 0; i--) {
        reversed[j++] = elem[i];
    }
    System.arraycopy(reversed, 0, elem, 0, usedSize);
}

功能：反转栈中的所有元素，栈顶元素变为栈底，栈底元素变为栈顶。
复杂度：时间复杂度 O(n)，因为需要遍历栈的所有元素并进行重新排序。
使用场景：如果需要将栈中的元素顺序反转，可以使用此方法。

5. toString()将栈转换为字符串形式，方便查看栈的内容。

@Override
public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    for (int i = 0; i < usedSize; i++) {
        sb.append(elem[i]);
        if (i < usedSize - 1) {
            sb.append(", ");
        }
    }
    sb.append("]");
    return sb.toString();
}

功能：返回栈中元素的字符串表示。
复杂度：时间复杂度 O(n)，需要遍历栈中的所有元素并构建字符串。
使用场景：当需要打印栈的内容时，可以使用 toString() 方法。对于调试和日志记录非常有用。

6. clone()（深拷贝栈）克隆栈，创建栈的副本。确保副本与原栈是两个独立的对象。

@Override
public MyStack clone() {
    MyStack newStack = new MyStack();
    newStack.elem = Arrays.copyOf(this.elem, this.elem.length);
    newStack.usedSize = this.usedSize;
    return newStack;
}

功能：创建栈的一个副本，确保副本的元素与原栈相同，但两个栈是独立的对象，互不影响。
复杂度：时间复杂度 O(n)，因为需要将栈中的元素复制到新的栈中。
使用场景：需要操作栈的副本，而不改变原栈的内容时使用。

7. shrink()（可选）如果栈的容量比元素数量大很多，进行收缩，减少不必要的内存占用。

private void shrink() {
    if (usedSize < elem.length / 4) {
        int newCapacity = elem.length / 2;
        elem = Arrays.copyOf(elem, newCapacity);
    }
}