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);
}
}
- 功能：如果栈的元素数量小于数组容量的四分之一，则将栈的容量缩小为原来的一半。
- 复杂度：时间复杂度 O(n)，因为需要复制栈中的元素到新数组中。
- 使用场景：用于栈的动态缩容，当栈的元素数目小于某个比例时，减少内存浪费。
8.clearAll()（可选）清空栈，并且将栈容量调整到默认大小。
public void clearAll() {
usedSize = 0;
elem = new int[DEFAULT_SIZE]; // 将栈的容量恢复为默认大小
}
- 功能：除了清空栈中的元素，还将栈的容量恢复为默认大小。
- 复杂度：时间复杂度 O(n)（如果实现了
clear操作）+ O(n)（重新分配数组）。 - 使用场景：当你想要重置栈，包括清空栈内容和恢复容量时使用。
9.peekBottom()（可选）返回栈底元素，但不删除它。
public int peekBottom() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return elem[0]; // 栈底元素是数组的第一个元素
}
- 功能：查看栈底的元素，而不删除它。
- 复杂度：时间复杂度 O(1)，直接返回栈底元素。
- 使用场景：有时需要查看栈底的元素，或者从栈底进行操作。
4.结语：
在本文中，我们详细探讨了如何实现一个简单的栈数据结构，并对栈的常见操作如 push、pop、peek 和 size 进行了深入的分析。通过这些方法，我们不仅了解了栈的基本功能，还能看到如何通过调整 usedSize 来有效管理栈的状态，保证其操作的高效性和安全性。
栈作为一种基本的数据结构，具有广泛的应用场景，尤其在算法、数据解析、函数调用栈等方面扮演着重要角色。通过本文的学习，我们可以更好地理解栈的内在机制，并能够在实际编程中灵活运用栈。
在实现栈的过程中，我们还探讨了几个常见的优化点，例如动态扩容、异常处理、以及线程安全等，确保栈能够在不同的环境和需求下稳定高效地运行。这些设计细节不仅提升了代码的健壮性，还增强了栈的可扩展性。
希望通过本文的介绍，读者能够对栈这一数据结构有更清晰的理解，并能够在实际项目中更加熟练地使用和扩展它。栈是很多算法和应用的基础，掌握它的设计和使用，将为解决更多复杂问题打下坚实的基础。
感谢您的阅读，期待您在实践中不断深入，探索更多有趣且实用的数据结构和算法。
