Java 中的栈（Stack）数据结构
1. 栈的定义
栈是一种遵循后进先出（LIFO：Last In First Out）原则的线性数据结构。它类似于一叠盘子：你只能在顶部添加或移除盘子。在栈中，我们只能访问最顶端的元素。
2. 栈的基本操作
压栈（Push）：将元素添加到栈顶
出栈（Pop）：移除并返回栈顶元素
查看（Peek）：查看栈顶元素但不移除
判空（isEmpty）：检查栈是否为空
3. Java 中的 Stack 类
Java 提供了一个内置的 Stack 类，它扩展了 Vector 类。尽管 Stack 类仍然可用，但在现代 Java 编程中，通常推荐使用 Deque 接口的实现（如 ArrayDeque ）来模拟栈的行为。
3.1 使用 Java 的 Stack 类
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack
// 压栈
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");
System.out.println("Stack: " + stack);
// 出栈
String top = stack.pop();
System.out.println("Popped element: " + top);
// 查看
System.out.println("Top element: " + stack.peek());
System.out.println("Updated stack: " + stack);
// 判空
System.out.println("Is stack empty? " + stack.isEmpty());
}
}
3.2 使用 Deque 接口实现栈
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeAsStackExample {
public static void main(String[] args) {
Deque
// 压栈
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");
System.out.println("Stack: " + stack);
// 出栈
String top = stack.pop();
System.out.println("Popped element: " + top);
// 查看
System.out.println("Top element: " + stack.peek());
System.out.println("Updated stack: " + stack);
// 判空
System.out.println("Is stack empty? " + stack.isEmpty());
}
}
4. 实现自定义栈
我们可以使用数组或链表来实现自定义栈。以下是使用数组实现的简单栈：
public class ArrayStack
private T[] array;
private int top;
private int capacity;
@SuppressWarnings("unchecked")
public ArrayStack(int capacity) {
this.capacity = capacity;
array = (T[]) new Object[capacity];
top = -1;
}
public void push(T item) {
if (isFull()) {
throw new IllegalStateException("Stack is full");
}
array[++top] = item;
}
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return array[top--];
}
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty");
}
return array[top];
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}
}
5. 栈的应用
栈在计算机科学和日常编程中有广泛的应用，例如：
函数调用和递归
表达式求值和语法解析
撤销操作（Undo）
深度优先搜索（DFS）算法
括号匹配问题
6. 栈的实际应用示例
6.1 括号匹配
public static boolean isBalanced(String expression) {
Stack
for (char ch : expression.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((ch == ')' && top != '(') ||
(ch == ']' && top != '[') ||
(ch == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
6.2 逆波兰表达式求值
public static int evaluateRPN(String[] tokens) {
Stack
for (String token : tokens) {
if (token.equals("+") || token.equals("-") ||
token.equals("*") || token.equals("/")) {
int b = stack.pop();
int a = stack.pop();
switch (token) {
case "+": stack.push(a + b); break;
case "-": stack.push(a - b); break;
case "*": stack.push(a * b); break;
case "/": stack.push(a / b); break;
}
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
7. 栈的优缺点
优点：
实现简单
后进先出的特性适用于许多算法和问题解决
函数调用和递归的基础
缺点：
只能访问最顶端的元素
不支持随机访问
大小通常是固定的（使用数组实现时）
8. 总结
栈是一种简单而强大的数据结构，在解决特定类型的问题时非常有用。理解栈的工作原理和应用场景对于编写高效的算法和程序至关重要。Java 提供了内置的 Stack 类和更现代的 Deque 接口实现，使得在实际编程中使用栈变得非常方便。