数据结构之栈：原理与常用方法

1. 栈的定义

Stack是Vector的一个子类，它实现标准的后进先出堆栈。Stack只定义了创建空堆栈的默认构造方法。（实际上是实现了List接口，因为Vector是List的子类）。

Stack() // 创建一个空栈

2. 栈的基本操作

// 压栈操作
public E push(E item) // 将元素压入栈顶// 弹栈操作
public E pop() // 移除栈顶元素并返回该元素// 查看栈顶元素但不移除
public E peek() // 查看栈顶元素但不移除// 判断栈是否为空
public boolean empty() // 测试栈是否为空// 查找元素在栈中的位置（从栈顶开始为1）
public int search(Object o) // 返回对象在栈中的位置，1表示栈顶

3. 继承自Vector的方法

由于Stack继承自Vector，所以还拥有以下方法：

// 获取栈的大小
public int size() // 判断栈是否包含指定元素
public boolean contains(Object o)// 返回指定位置的元素
public E get(int index)// 清空栈
public void clear()

4. Java 中的 Stack 类

Java 提供了一个内置的 Stack 类，它扩展了 Vector 类。尽管 Stack 类仍然可用，但在现代 Java 编程中，通常推荐使用 Deque 接口的实现（如 ArrayDeque ）来模拟栈的行为。

由于Stack继承自Vector，所有方法都是同步的，这在多线程环境下是安全的，但在单线程环境下会有性能损失。
Deque接口提供了更完整的栈操作，性能更好（非同步实现）

4.1. 使用 Java 的 Stack 类

import java.util.Stack;public class StackExample {public static void main(String[] args) {Stack<String> stack = new Stack<>();// 压栈操作stack.push("Apple");stack.push("Banana");stack.push("Cherry");// 查看栈大小System.out.println("Stack size: " + stack.size()); // 输出: 3// 查看栈顶元素System.out.println("Top element: " + stack.peek()); // 输出: Cherry// 弹栈操作System.out.println("Popped: " + stack.pop()); // 输出: CherrySystem.out.println("Popped: " + stack.pop()); // 输出: Banana// 判断栈是否为空System.out.println("Is stack empty? " + stack.empty()); // 输出: false// 查找元素位置System.out.println("Apple position: " + stack.search("Apple")); // 输出: 1// 清空栈stack.clear();System.out.println("Is stack empty after clear? " + stack.empty()); // 输出: true}
}

4.2. 使用 Deque 接口实现栈

import java.util.ArrayDeque;
import java.util.Deque;public class DequeAsStackExample {public static void main(String[] args) {Deque<String> stack = new ArrayDeque<>();// 压栈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());}
}

5. 实现自定义栈

我们可以使用数组或链表来实现自定义栈。以下是使用数组实现的简单栈：

public class ArrayStack<T> {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;}
}

6. 栈的应用

栈在计算机科学和日常编程中有广泛的应用，例如：

函数调用和递归
表达式求值和语法解析
撤销操作（Undo）
深度优先搜索（DFS）算法
括号匹配问题

7. 栈的实际应用示例

7.1. 括号匹配

public static boolean isBalanced(String expression) {Stack<Character> stack = new 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();
}

7.2. 逆波兰表达式求值

public static int evaluateRPN(String[] tokens) {Stack<Integer> stack = new 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();
}