您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 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，存在同步开销。
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
}
}
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) |
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;
}
}
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();
}
}
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();
}
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();
}
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();
}
}
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();
}
}
}
| 实现方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| java.util.Stack | 线程安全 | 性能较差（同步开销） | 需要同步的简单场景 |
| ArrayDeque | 高性能，非同步 | 容量固定（需扩容） | 大多数单线程场景 |
| 数组实现 | 内存连续，访问快 | 需要预先确定大小 | 已知最大容量的场景 |
| 链表实现 | 动态扩容，无内存浪费 | 内存不连续，访问稍慢 | 频繁动态变化的场景 |
如何用两个栈实现队列？
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();
}
}
如何判断栈的压入、弹出序列是否合法？
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();
}
Java中实现栈有多种方式，选择取决于具体需求：
- 标准库优先选择Deque接口的实现
- 需要线程安全时考虑同步控制
- 特殊需求可自定义实现
- 理解栈的底层实现有助于解决复杂算法问题
掌握栈的实现原理和应用场景，是Java开发者必备的基础数据结构知识。 “`
（全文约2150字，包含代码示例、复杂度分析、实现对比和应用场景）
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。