【数组结构与算法分析】一篇搞懂：栈与队列的底层实现原理与接口体系

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

前一段时间我们主要侧重于刷LeetCode的题目，主要还是因为我对那些知识都比较熟悉，比如数组，字符串，哈希表，链表等等，所以主要就是刷题，而接下来的栈，队列等等，就不太熟悉，这些都是数据结构与算法的内容，虽然之前看了一遍，但是印象不是很深刻，因此在这些主要侧重一些基础知识，适合新手预习和学过的同学用来回顾（由于本人学的是java，所以主要侧重于java）。

文章摘要：

本文系统讲解了Java中栈、队列及其实现方式。

栈（LIFO）推荐使用Deque接口的ArrayDeque实现，而非遗留的Stack类；

队列（FIFO）可通过Queue或Deque实现，ArrayDeque因其数组结构性能更优。

详细对比了数组与链表实现栈的差异（数组连续内存快，链表无容量限制），并介绍了优先级队列PriorityQueue和线程安全的阻塞队列（如ArrayBlockingQueue）。

强调ArrayDeque是多场景下的最佳选择，既能高效实现队列/栈，又避免LinkedList的额外开销。附代码示例和面试常见问题解析，帮助掌握数据结构核心应用。

栈，队列，数组，链表之间的关系

栈 (Stack)：后进先出（LIFO，Last In First Out）的结构，像一叠盘子，后放的先取走。

队列 (Queue)：先进先出（FIFO，First In First Out）的结构，像排队买票，先来的先服务。

关系：栈和队列是逻辑概念（抽象数据类型），规定了数据怎么进怎么出

数组和链表是物理实现（具体存储结构），是真正存放数据的地方。栈和队列可以用数组实现，也可以用链表实现。

一、栈和队列的核心特点

在 Java 中，通常不直接“写”栈和队列，而是用它们现成的接口和类，但理解原理才能用好。

• 官方推荐用ArrayDeque来实现栈和队列，而不是用Stack类（因为Stack继承自Vector，性能差且线程安全带来了不必要的开销）。

• 用ArrayDeque当栈：push、pop、peek

• 用ArrayDeque当队列：offer、poll、peek

java // 栈用法 (用 ArrayDeque) Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); stack.push(2); int top = stack.pop(); // 得到 2 // 队列用法 (用 ArrayDeque) Deque<Integer> queue = new ArrayDeque<>(); queue.offer(1); queue.offer(2); int front = queue.poll(); // 得到 1

二、与数组、链表的关系

这是一个“逻辑 vs 物理”的关系：

• 数组和链表：是计算机内存中真实存储数据的方式。数组是一块连续内存，链表是零散内存通过指针连接。

• 栈和队列：是一种使用规则。你可以拿一段连续内存（数组）来按栈的规则存取，也可以拿一堆节点（链表）来按栈的规则存取。

类比：
数组和链表就像“砖块”，栈和队列就像“建筑图纸”。用砖块既可以盖出“后进先出”结构的塔（栈），也可以盖出“先进先出”结构的通道（队列）。

三、栈的数组实现 vs 链表实现（重点理解）

这是面试和学习的常见考点。用代码结构来理解，不要死记。

1. 数组实现栈 (Array-based Stack)

核心思想：用数组存放元素，用一个整数变量top指向栈顶位置。

java class ArrayStack<E> { private Object[] data; private int top; // 栈顶指针，初始为 -1 表示空栈 private int capacity; public ArrayStack(int capacity) { this.capacity = capacity; this.data = new Object[capacity]; this.top = -1; } public void push(E e) { if (top == capacity - 1) throw new RuntimeException("栈满"); data[++top] = e; // top 先加1，再放元素 } public E pop() { if (top == -1) throw new RuntimeException("栈空"); E e = (E) data[top]; data[top--] = null; // 帮助GC，然后 top 减1 return e; } }

• 优点：内存连续，CPU 缓存友好，访问速度快。

• 缺点：需要预定义大小，扩容时成本高（需复制整个数组）。

• Java 中：ArrayDeque就是动态数组实现，自动扩容。

2. 链表实现栈 (Linked-list based Stack)

核心思想：用链表节点，始终在头部（或尾部）操作，通常选头部因为操作 O(1)。

java 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 void push(E e) { Node<E> newNode = new Node<>(e); newNode.next = top; // 新节点指向旧栈顶 top = newNode; // 更新栈顶 size++; } public E pop() { if (top == null) throw new RuntimeException("栈空"); E e = top.data; top = top.next; // 栈顶下移 size--; return e; } }

• 优点：没有容量限制（除非内存耗尽），不会浪费空间。

• 缺点：每个元素多存一个指针（额外内存开销），指针跳转可能引起缓存不命中，速度略慢。

• Java 中：LinkedList就是双向链表，可以当栈用，但通常不如ArrayDeque快。

四、到底用哪个实现（面试常问）

总结

1. 栈和队列是规则，数组和链表是存储方式。

2. Java 中直接用ArrayDeque：new ArrayDeque<>()既可以当栈也可以当队列。

3. 数组实现栈：靠top指针移动，连续内存，快但有容量限制。

4. 链表实现栈：靠改变头节点指向，无限容量，但每个节点多存一个引用。

5. 队列的数组实现（循环队列）比栈复杂，需要front和rear两个指针；队列的链表实现也很直观（头出尾入）。

栈：

java 没有 Stack 接口

Java 的设计者没有定义Stack接口，而是让Deque接口来承担栈的角色。

text Java 中实现"栈"功能的方式： Deque (接口) ← 官方推荐的栈接口 ├── ArrayDeque (类) ← 最常用 └── LinkedList (类) ← 也可以用 还有遗留的： Stack (类) ← 旧版，不推荐使用

一、官方推荐的栈方式：Deque 接口

Deque就是 Java 中的"栈接口"，只是名字叫"双端队列"而已。

Deque 提供的栈方法

栈操作	Deque 方法	说明
压栈	push(e)	在头部添加元素
弹栈	pop()	删除并返回头部元素
查看栈顶	peek()	返回头部元素，不删除
判断空	isEmpty()	继承自 Collection
栈大小	size()	继承自 Collection

java // 这就是 Java 中标准的栈用法 Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.peek()); // 3（查看栈顶） System.out.println(stack.pop()); // 3（弹栈） System.out.println(stack.pop()); // 2 System.out.println(stack.isEmpty()); // false

Deque 的继承体系

java Iterable (接口) └── Collection (接口) └── Queue (接口) └── Deque (接口) ← 这就是你要找的"栈接口" ├── ArrayDeque (类) ← 数组实现 └── LinkedList (类) ← 链表实现

二、遗留的 Stack 类（不要用）

Java 1.0 时代有个Stack类，但官方已经不推荐使用。

为什么不推荐

问题	说明
继承设计错误	继承了Vector，所以可以用add(index, element)在中间插入，破坏了栈的 LIFO 原则
性能差	Vector是线程安全的（同步），单线程下不需要
接口不统一	有自己的push/pop，但又继承了Vector的add/remove，混乱

java // 遗留的 Stack 类（不推荐） Stack<Integer> oldStack = new Stack<>(); oldStack.push(1); oldStack.push(2); oldStack.add(0, 999); // 竟然可以在中间插入！违反了栈的定义 System.out.println(oldStack.pop()); // 2（不是 999，混乱）

三、其他可以作为栈的接口/类

1.LinkedList类（实现了 Deque）

java // LinkedList 也可以当栈用 Deque<Integer> stack = new LinkedList<>(); stack.push(1); stack.push(2); stack.pop(); // 2

2.ArrayDeque类（最推荐）

java // 最佳实践 Deque<Integer> stack = new ArrayDeque<>();

3.ConcurrentLinkedDeque类（线程安全）

java // 多线程环境下的栈 Deque<Integer> concurrentStack = new ConcurrentLinkedDeque<>(); concurrentStack.push(1); concurrentStack.push(2); concurrentStack.pop(); // 线程安全

4.BlockingDeque接口（阻塞双端队列）

java // 阻塞版本的栈（线程安全 + 阻塞） BlockingDeque<Integer> blockingStack = new LinkedBlockingDeque<>(); blockingStack.push(1); blockingStack.push(2); Integer top = blockingStack.take(); // 空时会阻塞

四、完整的"栈相关"体系图

java 栈功能提供者： 1. Deque (接口) ⭐ 官方推荐的"栈接口" ├── ArrayDeque (类) ⭐⭐⭐ 最推荐 ├── LinkedList (类) ⭐⭐ 可以用 ├── ConcurrentLinkedDeque (类) ⭐ 线程安全版 └── LinkedBlockingDeque (类) ⭐ 阻塞版 2. Stack (类) ❌ 遗留，不推荐 3. 其他能模拟栈的（不推荐，但面试可能问） └── 用 ArrayList 手动模拟（从尾部进出）

五、面试常见问题

Q1: Java 中有 Stack 接口吗

A:没有。Java 用Deque接口来提供栈功能，ArrayDeque是推荐实现。

---

Q2: Stack 类和 ArrayDeque 有什么区别

A:

对比	Stack 类	ArrayDeque
线程安全	同步（性能差）	不同步（更快）
是否允许 null	允许	不允许
设计	继承 Vector，可随机访问	纯栈语义
官方推荐	❌ 不推荐	✅ 推荐

---

Q3: 为什么不用 LinkedList 当栈

A:可以用，但ArrayDeque更快（数组连续内存，缓存友好），除非需要存储 null 或频繁在中间插入删除。

---

Q4: 多线程环境下用什么栈

A:

• 非阻塞：ConcurrentLinkedDeque

• 阻塞：LinkedBlockingDeque

六、实战总结

java // ✅ 单线程环境 - 用这个 Deque<Integer> stack = new ArrayDeque<>(); // ✅ 多线程环境 - 用这个 Deque<Integer> stack = new ConcurrentLinkedDeque<>(); // ✅ 需要阻塞功能 - 用这个 BlockingDeque<Integer> stack = new LinkedBlockingDeque<>(); // ❌ 不要用这个 Stack<Integer> stack = new Stack<>();

一句话总结

Java 中没有Stack接口，Deque接口就是栈的官方接口，用ArrayDeque实现。

队列：

Iterable └── Collection ├── Queue (接口) - 标准队列 │ ├── Deque (接口) - 双端队列 │ │ ├── ArrayDeque (类) - 数组实现 │ │ └── LinkedList (类) - 链表实现 │ │ │ └── BlockingQueue (接口) - 阻塞队列（并发编程） │ ├── ArrayBlockingQueue (类) │ ├── LinkedBlockingQueue (类) │ ├── PriorityBlockingQueue (类) │ ├── DelayQueue (类) │ ├── SynchronousQueue (类) │ └── LinkedTransferQueue (类) │ └── AbstractQueue (抽象类) - 辅助实现 还有独立的： - PriorityQueue (类) - 优先级队列，直接实现 Queue - ConcurrentLinkedQueue (类) - 并发非阻塞队列 - TransferQueue (接口) - 传递队列（高并发）

• Queue：标准的队列接口，只能一端进、另一端出（FIFO，先进先出）。

• Deque：双端队列接口（Double Ended Queue），两端都可以进出，所以它既可以当队列用，也可以当栈用。

关系：Deque是Queue的子接口，功能比Queue更强大。

java // 继承关系 Iterable -> Collection -> Queue -> Deque

一、Queue 接口（标准队列）

特点：先进先出（FIFO），队尾进，队首出。

核心方法（重要，面试常考）

为什么有两套方法

• 抛出异常版：add、remove、element— 适用于队列一定非空或有容量的场景。

• 返回特殊值版：offer、poll、peek— 更安全，推荐日常使用。

典型实现

java // LinkedList 实现 Queue Queue<String> queue = new LinkedList<>(); queue.offer("A"); queue.offer("B"); String head = queue.poll(); // "A" // 查看队首不删除 String peek = queue.peek(); // "B"

二、Deque 接口（双端队列）

特点：两端都能操作，因此功能更强大。

核心方法

Deque 如何当队列用

Deque 提供了和 Queue 完全对应的方法：

所以Queue queue = new ArrayDeque<>()完全合法，ArrayDeque就是当作队列用的。

Deque 如何当栈用（重点）

java // 用 Deque 实现栈（Java 官方推荐） Deque<Integer> stack = new ArrayDeque<>(); stack.push(1); // 压栈 stack.push(2); int top = stack.pop(); // 弹栈，得到 2 int peek = stack.peek(); // 查看栈顶，得到 1

三、Queue vs Deque 对比总结

为什么ArrayDeque比LinkedList快

• ArrayDeque底层是数组，内存连续，CPU 缓存命中率高。

• LinkedList底层是链表，每个元素需要额外存储前后指针，内存开销大，且指针跳转多。

所以记住 Java 最佳实践：

• 需要队列 →Queue<T> queue = new ArrayDeque<>()

• 需要栈 →Deque<T> stack = new ArrayDeque<>()

• 尽量避免用Stack类（遗留类，性能差）

• 尽量避免用LinkedList做队列/栈（除非需要 null 或频繁的中间插入删除）

一句话记忆

• Queue：只能从队尾进、队首出（排队）

• Deque：两头都能进能出（既可以排队，也可以叠盘子）

• 用ArrayDeque就对了，它既能当Queue也能当Deque还能当栈

回答面试题：java 中栈和队列通常怎么实现？"→ "用Deque接口配合ArrayDeque实现

一、普通队列

1.Queue接口（上面提及了）

• 标准 FIFO 队列

• 实现类：PriorityQueue、ConcurrentLinkedQueue、各种阻塞队列的父接口

2.Deque接口（上面提及了）

• 双端队列，功能更强大

• 实现类：ArrayDeque、LinkedList

3.PriorityQueue⭐ 重点掌握

特点：不是 FIFO，而是按优先级出队（最小堆实现）

java Queue<Integer> pq = new PriorityQueue<>(); pq.offer(5); pq.offer(1); pq.offer(3); System.out.println(pq.poll()); // 1 (最小的先出) System.out.println(pq.poll()); // 3 System.out.println(pq.poll()); // 5 // 自定义排序（降序） Queue<Integer> pqDesc = new PriorityQueue<>((a, b) -> b - a); pqDesc.offer(5); pqDesc.offer(1); pqDesc.offer(3); System.out.println(pqDesc.poll()); // 5 (最大的先出)

使用场景：

• 任务调度（紧急任务先执行）

• 求 Top K 问题

• Dijkstra 最短路径算法

4.ConcurrentLinkedQueue

特点：线程安全的非阻塞队列（用 CAS 实现，性能高）

java // 多线程环境下安全使用 Queue<String> queue = new ConcurrentLinkedQueue<>(); // 不需要手动加锁，多个线程可以同时 offer/poll

二、阻塞队列（并发编程核心）🔥 重要

特点：当队列满时，入队操作会阻塞等待；当队列空时，出队操作会阻塞等待。

核心接口：BlockingQueue

比 Queue 多了几个阻塞方法：

常用实现类（面试高频）

经典例子：生产者-消费者

java // 用阻塞队列轻松实现生产者-消费者模式 BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(10); // 生产者 new Thread(() -> { for (int i = 0; i < 100; i++) { queue.put(i); // 队列满时会阻塞等待 System.out.println("生产: " + i); } }).start(); // 消费者 new Thread(() -> { while (true) { Integer i = queue.take(); // 队列空时会阻塞等待 System.out.println("消费: " + i); } }).start();

三、特殊队列（高并发）

TransferQueue接口

比BlockingQueue多一个transfer()方法：生产者等待消费者接收后才返回。

java TransferQueue<String> queue = new LinkedTransferQueue<>(); // 生产者：必须等消费者取走才继续 queue.transfer("重要消息"); // 阻塞直到被 take() // 消费者 String msg = queue.take(); // 取走消息，生产者解除阻塞

四、完整分类总结（面试速记）

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！