Java 数据结构:栈与队列核心指南
本文系统介绍 Java 中栈、队列和双端队列的数据结构与实现。内容包括核心概念、API 使用规范、基于数组和链表的模拟实现、循环队列策略、典型应用场景如括号匹配和 BFS 搜索,以及经典面试题解法。同时对比了不同实现的性能差异,并给出实际开发中的选型建议。

本文系统介绍 Java 中栈、队列和双端队列的数据结构与实现。内容包括核心概念、API 使用规范、基于数组和链表的模拟实现、循环队列策略、典型应用场景如括号匹配和 BFS 搜索,以及经典面试题解法。同时对比了不同实现的性能差异,并给出实际开发中的选型建议。

栈 (Stack) 是一种特殊的线性表,只允许在固定的一端(栈顶) 进行插入和删除操作。数据遵循后进先出 (LIFO) 原则。
关键术语:
import java.util.Stack;
public class StackDemo {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
// 压栈操作
stack.push(10); // 栈:[10]
stack.push(20); // 栈:[10, 20]
stack.push(30); // 栈:[10, 20, 30]
// 查看栈顶元素
System.out.println("栈顶元素:" + stack.peek()); // 30
// 出栈操作
int top = stack.pop(); // 移除 30
System.out.println("出栈元素:" + top); // 30
// 栈大小
System.out.println("栈大小:" + stack.size()); // 2
// 判断栈是否为空
System.out.println("栈是否为空:" + stack.isEmpty()); // false
}
}
// Stack 类的继承层次
public class Stack<E> extends Vector<E> {
// ...
}
// Vector 是线程安全的动态数组
// 这意味着 Stack 也是线程安全的,但性能较低
为什么 Stack 继承 Vector 是个设计问题?
Deque 接口的实现类代替 Stack// 推荐使用 Deque 作为栈
Deque<Integer> stack = new ArrayDeque<>(); // 性能更好
stack.push(1);
stack.pop();
public class ArrayStack<E> {
private Object[] elements; // 存储元素的数组
private int top; // 栈顶指针
private int capacity; // 栈容量
public ArrayStack(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
this.top = -1; // 空栈时 top 为 -1
}
// 压栈操作
public boolean push(E element) {
if (isFull()) { // 动态扩容
resize();
}
elements[++top] = element;
return true;
}
// 出栈操作
@SuppressWarnings("unchecked")
public E pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
E element = (E) elements[top];
elements[top--] = null; // 帮助 GC
return element;
}
// 查看栈顶元素
@SuppressWarnings("unchecked")
public E peek {
(isEmpty()) {
();
}
(E) elements[top];
}
{
top == -;
}
{
top == capacity - ;
}
{
capacity * ;
elements = Arrays.copyOf(elements, newCapacity);
capacity = newCapacity;
}
}
public class LinkedStack<E> {
// 链表节点
private static class Node<E> {
E data;
Node<E> next;
Node(E data) {
this.data = data;
}
}
private Node<E> top; // 栈顶节点
private int size; // 栈大小
public LinkedStack() {
top = null;
size = 0;
}
// 压栈操作 - O(1)
public void push(E element) {
Node<E> newNode = new Node<>(element);
newNode.next = top; // 新节点指向原栈顶
top = newNode; // 更新栈顶
size++;
}
// 出栈操作 - O(1)
public E pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
E element = top.data;
top = top.next; // 栈顶下移
size--;
return element;
}
// 查看栈顶 - O(1)
public E peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
top.data;
}
{
top == ;
}
{
size;
}
}
public class BracketChecker {
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
// 左括号入栈
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
}
// 右括号检查匹配
else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else {
return false; // 不匹配
}
}
return stack.isEmpty(); // 栈为空说明全部匹配
}
// 测试
public static void main(String[] args) {
System.out.println(isValid("()[]{}")); // true
System.out.println(isValid("([)]")); // false
}
}
public class BrowserHistory {
private Stack<String> backStack; // 后退栈
private Stack<String> forwardStack; // 前进栈
private String currentPage;
public BrowserHistory(String homepage) {
backStack = new Stack<>();
forwardStack = new Stack<>();
currentPage = homepage;
}
// 访问新页面
public void visit(String url) {
backStack.push(currentPage);
currentPage = url;
forwardStack.clear(); // 清空前进栈
}
// 后退
public String back(int steps) {
while (steps > 0 && !backStack.isEmpty()) {
forwardStack.push(currentPage);
currentPage = backStack.pop();
steps--;
}
return currentPage;
}
// 前进
public String forward(int steps) {
while (steps > 0 && !forwardStack.isEmpty()) {
backStack.push(currentPage);
currentPage = forwardStack.pop();
steps--;
}
return currentPage;
}
}
public class RPNCalculator {
// 计算逆波兰表达式
public static int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (isOperator(token)) {
int b = stack.pop();
int a = stack.pop();
int result = applyOperation(a, b, token);
stack.push(result);
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
private static boolean isOperator(String token) {
return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
}
private static int applyOperation(int a, int b, String op) {
switch (op) {
case "+": return a + b;
case "-": return a - b;
case "*": a * b;
: a / b;
: ();
}
}
List<String> {
List<String> output = <>();
Stack<String> operators = <>();
Map<String, Integer> precedence = <>();
precedence.put(, );
precedence.put(, );
precedence.put(, );
precedence.put(, );
(String token : infix) {
(isNumber(token)) {
output.add(token);
} (token.equals()) {
operators.push(token);
} (token.equals()) {
(!operators.peek().equals()) {
output.add(operators.pop());
}
operators.pop();
} {
(!operators.isEmpty() && !operators.peek().equals() && precedence.getOrDefault(operators.peek(), ) >= precedence.getOrDefault(token, )) {
output.add(operators.pop());
}
operators.push(token);
}
}
(!operators.isEmpty()) {
output.add(operators.pop());
}
output;
}
}
| 概念 | 定义 | 特点 |
|---|---|---|
| 数据结构栈 | 后进先出的线性表 | 用于算法设计,如 DFS、表达式求值 |
| JVM 栈 | Java 虚拟机内存区域 | 存储局部变量、操作数栈、方法出口等 |
| 栈帧 | 方法调用的基本单位 | 包含局部变量表、操作数栈、动态链接、返回地址 |
| 线程栈 | 每个线程私有的栈 | 存储线程执行的方法调用信息 |
// JVM 栈的简单理解
public class JVMStackDemo {
public static void main(String[] args) {
// main 方法栈帧
int x = 10;
method1(x); // 创建 method1 的栈帧
}
static void method1(int param) {
// method1 栈帧
int y = 20;
method2(y); // 创建 method2 的栈帧
}
static void method2(int param) {
// method2 栈帧
System.out.println(param);
}
}
队列 (Queue) 是一种只允许在一端(队尾)插入,在另一端(队头)删除的线性表,遵循先进先出 (FIFO) 原则。
import java.util.LinkedList;
import java.util.Queue;
public class QueueDemo {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 入队操作
queue.offer(10); // 队列:[10]
queue.offer(20); // 队列:[10, 20]
queue.offer(30); // 队列:[10, 20, 30]
// 查看队头元素
System.out.println("队头元素:" + queue.peek()); // 10
// 出队操作
int front = queue.poll(); // 移除 10
System.out.println("出队元素:" + front); // 10
// 队列大小
System.out.println("队列大小:" + queue.size()); // 2
// 判断队列是否为空
System.out.println("队列是否为空:" + queue.isEmpty()); // false
// 遍历队列
System.out.print("队列元素: ");
for (Integer num : queue) {
System.out.print(num + " "); // 20 30
}
}
}
| 方法 | 功能 | 异常处理 |
|---|---|---|
add(e) | 入队,失败时抛出异常 | IllegalStateException |
offer(e) | 入队,失败时返回 false | 无异常 |
remove() | 出队,空队列时抛出异常 | NoSuchElementException |
poll() | 出队,空队列时返回 null | 无异常 |
element() | 查看队头,空队列时抛异常 | NoSuchElementException |
peek() | 查看队头,空队列时返回 null | 无异常 |
推荐使用:offer()、poll()、peek(),避免异常处理
public class LinkedQueue<E> {
// 链表节点
private static class Node<E> {
E data;
Node<E> next;
Node(E data) {
this.data = data;
}
}
private Node<E> head; // 队头
private Node<E> tail; // 队尾
private int size;
public LinkedQueue() {
head = tail = null;
size = 0;
}
// 入队操作 - O(1)
public boolean offer(E element) {
Node<E> newNode = new Node<>(element);
if (tail == null) { // 空队列
head = tail = newNode;
} else {
tail.next = newNode;
tail = newNode;
}
size++;
return true;
}
// 出队操作 - O(1)
public E poll() {
if (isEmpty()) {
return null;
}
E element = head.data;
head = head.next;
if (head == null) {
tail = null; // 队列已空
}
size--;
return element;
}
E {
(isEmpty()) {
;
}
head.data;
}
{
head == ;
}
{
size;
}
}
普通队列使用数组实现时,出队操作会导致"假溢出"(数组前面有空位但后面已满)。循环队列通过循环利用数组空间解决这个问题。
public class CircularQueue<E> {
private Object[] elements;
private int head; // 队头索引
private int tail; // 队尾索引
private int size; // 元素个数
private int capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
this.head = this.tail = 0;
this.size = 0;
}
// 入队操作
public boolean offer(E element) {
if (isFull()) {
return false;
}
elements[tail] = element;
tail = (tail + 1) % capacity; // 循环移动
size++;
return true;
}
// 出队操作
@SuppressWarnings("unchecked")
public E poll() {
if (isEmpty()) {
return null;
}
E element = (E) elements[head];
elements[head] = ;
head = (head + ) % capacity;
size--;
element;
}
{
size == ;
}
{
size == capacity;
}
E {
(isEmpty()) {
;
}
(E) elements[head];
}
{
size;
}
{
( ; i < capacity; i++) {
elements[i] = ;
}
head = tail = ;
size = ;
}
}
| 策略 | 实现方式 | 优点 | 缺点 |
|---|---|---|---|
| size 计数法 | 维护 size 变量 | 逻辑简单,判断准确 | 需要额外空间 |
| 空一位法 | tail+1=head 为满 | 不需要 size 变量 | 浪费一个数组位置 |
| 标志位法 | 使用 flag 标记 | 可区分空和满 | 逻辑复杂 |
推荐使用 size 计数法,代码清晰易懂。
public class ThreadPool {
private final Queue<Runnable> taskQueue;
private final List<WorkerThread> threads;
private volatile boolean isShutdown;
public ThreadPool(int poolSize) {
taskQueue = new LinkedList<>();
threads = new ArrayList<>();
isShutdown = false;
// 创建工作线程
for (int i = 0; i < poolSize; i++) {
WorkerThread thread = new WorkerThread();
thread.start();
threads.add(thread);
}
}
// 提交任务
public void execute(Runnable task) {
if (isShutdown) {
throw new IllegalStateException("线程池已关闭");
}
synchronized (taskQueue) {
taskQueue.offer(task);
taskQueue.notify(); // 唤醒等待的工作线程
}
}
// 工作线程
private class WorkerThread extends Thread {
@Override
{
(!isShutdown || !taskQueue.isEmpty()) {
;
(taskQueue) {
(taskQueue.isEmpty() && !isShutdown) {
{
taskQueue.wait();
} (InterruptedException e) {
Thread.currentThread().interrupt();
;
}
}
task = taskQueue.poll();
}
(task != ) {
{
task.run();
} (Exception e) {
e.printStackTrace();
}
}
}
}
}
{
isShutdown = ;
(taskQueue) {
taskQueue.notifyAll();
}
}
}
public class BFS {
// 图的节点
static class Node {
int value;
List<Node> neighbors;
Node(int value) {
this.value = value;
this.neighbors = new ArrayList<>();
}
}
// BFS 遍历
public static void bfs(Node start) {
if (start == null) return;
Queue<Node> queue = new LinkedList<>();
Set<Node> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
Node current = queue.poll();
System.out.print(current.value + " "); // 访问邻居节点
for (Node neighbor : current.neighbors) {
if (!visited.contains(neighbor)) {
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
System.out.println(); // 换行表示新的一层
}
}
// 寻找最短路径
public {
Queue<Node> queue = <>();
Map<Node, Integer> distances = <>();
queue.offer(start);
distances.put(start, );
(!queue.isEmpty()) {
queue.poll();
distances.get(current);
(current == target) {
currentDist;
}
(Node neighbor : current.neighbors) {
(!distances.containsKey(neighbor)) {
distances.put(neighbor, currentDist + );
queue.offer(neighbor);
}
}
}
-;
}
}
双端队列 (Deque) 允许在队头和队尾都可以进行插入和删除操作,结合了栈和队列的特性。
Java 提供了两种主要实现:
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeDemo {
public static void main(String[] args) {
// 作为栈使用
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 压栈
stack.push(2);
System.out.println(stack.pop()); // 2 (出栈)
// 作为队列使用
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 入队
queue.offer(2);
System.out.println(queue.poll()); // 1 (出队)
// 双端操作
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // 头部添加
deque.addLast(2); // 尾部添加
System.out.println(deque.removeFirst()); // 1
System.out.println(deque.removeLast()); // 2
}
}
| 操作类型 | 队头操作 | 队尾操作 | 说明 |
|---|---|---|---|
| 插入 | addFirst(e) | addLast(e) | 失败时抛出异常 |
offerFirst(e) | offerLast(e) | 失败时返回 false | |
| 删除 | removeFirst() | removeLast() | 空队列时抛异常 |
pollFirst() | pollLast() | 空队列时返回 null | |
| 查看 | getFirst() | getLast() | 空队列时抛异常 |
peekFirst() | peekLast() | 空队列时返回 null |
public class SlidingWindow {
// 使用双端队列维护窗口最大值
public static int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // 存储索引
for (int i = 0; i < n; i++) {
// 移除窗口外的元素
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// 保持队列递减(从大到小)
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
// 添加当前元素索引
deque.offerLast(i);
// 记录窗口最大值
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
public static void main(String[] args) {
[] nums = {, , -, -, , , , };
;
[] result = maxSlidingWindow(nums, k);
}
}
class MyStack {
private Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
// 方法 1:每次入栈时重新排列队列
public void push(int x) {
int size = queue.size();
queue.offer(x);
// 将前面的元素依次移到后面
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
// 方法 2:使用两个队列
class MyStack2 {
private Queue<Integer> mainQueue;
private Queue<Integer> helperQueue;
public MyStack2() {
mainQueue = new LinkedList<>();
helperQueue = new LinkedList<>();
}
public void push(int x) {
helperQueue.offer(x);
// 将主队列所有元素移到辅助队列
while (!mainQueue.isEmpty()) {
helperQueue.offer(mainQueue.poll());
}
// 交换两个队列
Queue<Integer> temp = mainQueue;
mainQueue = helperQueue;
helperQueue = temp;
}
public int pop() {
mainQueue.poll();
}
{
mainQueue.peek();
}
{
mainQueue.isEmpty();
}
}
{
queue.poll();
}
{
queue.peek();
}
{
queue.isEmpty();
}
}
class MyQueue {
private Stack<Integer> inStack; // 输入栈
private Stack<Integer> outStack; // 输出栈
public MyQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
// 入队:直接压入输入栈
public void push(int x) {
inStack.push(x);
}
// 出队:如果输出栈为空,将输入栈所有元素弹出并压入输出栈
public int pop() {
if (outStack.isEmpty()) {
transfer();
}
return outStack.pop();
}
// 查看队头
public int peek() {
if (outStack.isEmpty()) {
transfer();
}
return outStack.peek();
}
// 转移元素
private void transfer() {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
// 判断队列是否为空
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
}
class MinStack {
private Stack<Integer> dataStack; // 数据栈
private Stack<Integer> minStack; // 最小栈
public MinStack() {
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
dataStack.push(val);
// 如果最小栈为空或当前值更小,则入栈
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
if (dataStack.isEmpty()) return;
int val = dataStack.pop();
// 如果弹出的是最小值,最小栈也弹出
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return dataStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
// 优化版:只用一个栈存储差值
class MinStackOptimized {
private Stack<Long> stack;
private long min;
public MinStackOptimized {
stack = <>();
}
{
(stack.isEmpty()) {
stack.push();
min = val;
} {
val - min;
stack.push(diff);
(diff < ) {
min = val;
}
}
}
{
stack.pop();
(diff < ) {
min = min - diff;
}
}
{
stack.peek();
(diff < ) {
() min;
} {
() (min + diff);
}
}
{
() min;
}
}
| 操作 | Stack (继承 Vector) | ArrayDeque | LinkedList | 推荐 |
|---|---|---|---|---|
| push/pop | O(1) 同步开销大 | O(1) 平摊 | O(1) | ArrayDeque |
| 随机访问 | O(1) | O(1) | O(n) | ArrayDeque |
| 内存占用 | 较少 | 较少 | 较多(节点开销) | ArrayDeque |
| 线程安全 | 是 | 否 | 否 | 无并发用 ArrayDeque |
结论:优先使用 ArrayDeque 作为栈的实现。
| 场景 | 推荐实现 | 理由 |
|---|---|---|
| 一般队列 | LinkedList | 功能完整,支持 null 元素 |
| 高并发队列 | ConcurrentLinkedQueue | 线程安全,无锁 |
| 有界队列 | ArrayBlockingQueue | 固定大小,阻塞操作 |
| 延迟队列 | DelayQueue | 支持延迟获取元素 |
| 优先级队列 | PriorityQueue | 按优先级出队 |
| 数据结构 | 压栈/入队 | 出栈/出队 | 查看栈顶/队头 | 随机访问 |
|---|---|---|---|---|
| ArrayStack | O(1) 平摊 | O(1) | O(1) | O(1) |
| LinkedStack | O(1) | O(1) | O(1) | O(n) |
| ArrayQueue | O(1) | O(n) 需搬移 | O(1) | O(1) |
| CircularQueue | O(1) | O(1) | O(1) | O(1) |
| LinkedQueue | O(1) | O(1) | O(1) | O(n) |
| ArrayDeque | O(1) 平摊 | O(1) | O(1) | O(1) |
// 1. 优先使用 Deque 而不是 Stack
Deque<Integer> stack = new ArrayDeque<>(); // ✓
// Stack<Integer> stack = new Stack<>(); // ✗(过时)
// 2. 初始容量预估
Deque<Integer> stack = new ArrayDeque<>(100); // 预估初始容量
// 3. 栈的典型应用模式
public class StackPatterns {
// 模式 1:对称性匹配(括号、标签等)
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
// ... 括号匹配逻辑
}
// 模式 2:撤销/重做功能
public class Editor {
Deque<String> undoStack = new ArrayDeque<>();
Deque<String> redoStack = new ArrayDeque<>();
public void edit(String content) {
undoStack.push(content);
redoStack.clear(); // 新编辑清空重做栈
}
}
// 模式 3:深度优先遍历
public void dfs(Node root) {
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
// 处理节点
for (Node child : node.children) {
stack.push(child);
}
}
}
}
// 1. 根据场景选择合适的队列实现
Queue<String> queue = new LinkedList<>(); // 一般队列
BlockingQueue<String> bq = new ArrayBlockingQueue<>(100); // 有界阻塞队列
// 2. 生产者 - 消费者模式
public class ProducerConsumer {
private final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10);
class Producer implements Runnable {
public void run() {
try {
for (int i = 0; i < 100; i++) {
queue.put(i); // 阻塞直到有空间
System.out.println("生产:" + i);
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
class Consumer implements Runnable {
public void run() {
try {
while (true) {
Integer item = queue.take(); // 阻塞直到有元素
System.out.println( + item);
}
} (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
}
{
PriorityQueue<Task> taskQueue = <>(
Comparator.comparing(Task::getPriority)
);
{
taskQueue.offer(task);
}
Task {
taskQueue.poll();
}
}

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online