Java栈如何实现

# Java栈如何实现 ## 1. 栈的基本概念 栈（Stack）是一种遵循**后进先出（LIFO）**原则的线性数据结构，其核心操作包括： - `push`：元素入栈 - `pop`：栈顶元素出栈 - `peek`：查看栈顶元素（不删除） - `isEmpty`：判断栈是否为空 ## 2. Java中的栈实现方式 ### 2.1 使用`java.util.Stack`类 ```java import java.util.Stack; public class StackDemo { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // 入栈操作 stack.push(10); stack.push(20); // 出栈操作 System.out.println(stack.pop()); // 输出20 // 查看栈顶 System.out.println(stack.peek()); // 输出10 // 判断空栈 System.out.println(stack.isEmpty()); // false } } 

注意：虽然Stack类可用，但官方推荐使用Deque接口的实现类（如ArrayDeque），因为Stack继承自Vector，存在同步开销。

2.2 使用Deque接口（推荐）

import java.util.ArrayDeque; import java.util.Deque; public class DequeAsStack { public static void main(String[] args) { Deque<Integer> stack = new ArrayDeque<>(); stack.push(30); stack.push(40); System.out.println(stack.pop()); // 40 } } 

3. 手动实现栈（数组版）

public class ArrayStack { private int maxSize; private int[] stack; private int top = -1; public ArrayStack(int size) { this.maxSize = size; stack = new int[maxSize]; } // 判断栈满 public boolean isFull() { return top == maxSize - 1; } // 判断栈空 public boolean isEmpty() { return top == -1; } // 入栈 public void push(int value) { if (isFull()) { throw new RuntimeException("栈已满"); } stack[++top] = value; } // 出栈 public int pop() { if (isEmpty()) { throw new RuntimeException("栈为空"); } return stack[top--]; } // 查看栈顶 public int peek() { if (isEmpty()) { throw new RuntimeException("栈为空"); } return stack[top]; } } 

复杂度分析

操作	时间复杂度	空间复杂度
push	O(1)	O(n)
pop	O(1)	O(1)
peek	O(1)	O(1)

4. 手动实现栈（链表版）

public class LinkedStack { private static class Node { int data; Node next; Node(int data) { this.data = data; } } private Node top; public void push(int value) { Node newNode = new Node(value); newNode.next = top; top = newNode; } public int pop() { if (top == null) { throw new RuntimeException("栈为空"); } int value = top.data; top = top.next; return value; } public int peek() { if (top == null) { throw new RuntimeException("栈为空"); } return top.data; } public boolean isEmpty() { return top == null; } } 

5. 栈的典型应用场景

5.1 函数调用栈

public class CallStackDemo { static void methodA() { System.out.println("进入A方法"); methodB(); System.out.println("离开A方法"); } static void methodB() { System.out.println("进入B方法"); } public static void main(String[] args) { methodA(); } } 

5.2 括号匹配

public boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') stack.push(')'); else if (c == '[') stack.push(']'); else if (c == '{') stack.push('}'); else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty(); } 

5.3 逆波兰表达式

public int evalRPN(String[] tokens) { Deque<Integer> stack = new ArrayDeque<>(); for (String token : tokens) { if (token.equals("+")) { stack.push(stack.pop() + stack.pop()); } else if (token.equals("-")) { int b = stack.pop(); int a = stack.pop(); stack.push(a - b); } else if (token.equals("*")) { stack.push(stack.pop() * stack.pop()); } else if (token.equals("/")) { int b = stack.pop(); int a = stack.pop(); stack.push(a / b); } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); } 

6. 栈的变体实现

6.1 最小栈（O(1)获取最小值）

class MinStack { private Deque<Integer> dataStack; private Deque<Integer> minStack; public MinStack() { dataStack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); } public void push(int val) { dataStack.push(val); if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } } public void pop() { if (dataStack.pop().equals(minStack.peek())) { minStack.pop(); } } public int top() { return dataStack.peek(); } public int getMin() { return minStack.peek(); } } 

6.2 线程安全栈

import java.util.concurrent.locks.ReentrantLock; public class ConcurrentStack<T> { private static class Node<T> { T item; Node<T> next; Node(T item) { this.item = item; } } private volatile Node<T> top; private ReentrantLock lock = new ReentrantLock(); public void push(T item) { Node<T> newNode = new Node<>(item); lock.lock(); try { newNode.next = top; top = newNode; } finally { lock.unlock(); } } public T pop() { lock.lock(); try { if (top == null) return null; T item = top.item; top = top.next; return item; } finally { lock.unlock(); } } } 

7. 性能比较与选择建议

实现方式	优点	缺点	适用场景
java.util.Stack	线程安全	性能较差（同步开销）	需要同步的简单场景
ArrayDeque	高性能，非同步	容量固定（需扩容）	大多数单线程场景
数组实现	内存连续，访问快	需要预先确定大小	已知最大容量的场景
链表实现	动态扩容，无内存浪费	内存不连续，访问稍慢	频繁动态变化的场景

8. 常见面试题

1. 如何用两个栈实现队列？

   class MyQueue { private Deque<Integer> inStack; private Deque<Integer> outStack; public MyQueue() { inStack = new ArrayDeque<>(); outStack = new ArrayDeque<>(); } public void push(int x) { inStack.push(x); } public int pop() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } } 

2. 如何判断栈的压入、弹出序列是否合法？

   public boolean validateStackSequences(int[] pushed, int[] popped) { Deque<Integer> stack = new ArrayDeque<>(); int i = 0; for (int num : pushed) { stack.push(num); while (!stack.isEmpty() && stack.peek() == popped[i]) { stack.pop(); i++; } } return stack.isEmpty(); } 

9. 总结

Java中实现栈有多种方式，选择取决于具体需求： - 标准库优先选择Deque接口的实现 - 需要线程安全时考虑同步控制 - 特殊需求可自定义实现 - 理解栈的底层实现有助于解决复杂算法问题

掌握栈的实现原理和应用场景，是Java开发者必备的基础数据结构知识。 “`

（全文约2150字，包含代码示例、复杂度分析、实现对比和应用场景）