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

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言前一段时间我们主要侧重于刷LeetCode的题目主要还是因为我对那些知识都比较熟悉比如数组字符串哈希表链表等等所以主要就是刷题而接下来的栈队列等等就不太熟悉这些都是数据结构与算法的内容虽然之前看了一遍但是印象不是很深刻因此在这些主要侧重一些基础知识适合新手预习和学过的同学用来回顾由于本人学的是java所以主要侧重于java。文章摘要本文系统讲解了Java中栈、队列及其实现方式。栈LIFO推荐使用Deque接口的ArrayDeque实现而非遗留的Stack类队列FIFO可通过Queue或Deque实现ArrayDeque因其数组结构性能更优。详细对比了数组与链表实现栈的差异数组连续内存快链表无容量限制并介绍了优先级队列PriorityQueue和线程安全的阻塞队列如ArrayBlockingQueue。强调ArrayDeque是多场景下的最佳选择既能高效实现队列/栈又避免LinkedList的额外开销。附代码示例和面试常见问题解析帮助掌握数据结构核心应用。栈队列数组链表之间的关系栈 (Stack)后进先出LIFOLast In First Out的结构像一叠盘子后放的先取走。队列 (Queue)先进先出FIFOFirst In First Out的结构像排队买票先来的先服务。关系栈和队列是逻辑概念抽象数据类型规定了数据怎么进怎么出数组和链表是物理实现具体存储结构是真正存放数据的地方。栈和队列可以用数组实现也可以用链表实现。一、栈和队列的核心特点在 Java 中通常不直接“写”栈和队列而是用它们现成的接口和类但理解原理才能用好。特性栈 (Stack)队列 (Queue)原则后进先出 (LIFO)先进先出 (FIFO)主要操作push压栈、pop弹栈、peek看栈顶offer入队、poll出队、peek看队首Java 中的典型实现ArrayDeque推荐、Stack旧版不推荐、LinkedListArrayDeque、LinkedList、PriorityQueue生活类比浏览器的后退按钮、撤销操作 (CtrlZ)打印机任务队列、线程池任务排队官方推荐用ArrayDeque来实现栈和队列而不是用Stack类因为Stack继承自Vector性能差且线程安全带来了不必要的开销。用ArrayDeque当栈push、pop、peek用ArrayDeque当队列offer、poll、peekjava // 栈用法 (用 ArrayDeque) DequeInteger stack new ArrayDeque(); stack.push(1); stack.push(2); int top stack.pop(); // 得到 2 // 队列用法 (用 ArrayDeque) DequeInteger queue new ArrayDeque(); queue.offer(1); queue.offer(2); int front queue.poll(); // 得到 1二、与数组、链表的关系这是一个“逻辑 vs 物理”的关系数组和链表是计算机内存中真实存储数据的方式。数组是一块连续内存链表是零散内存通过指针连接。栈和队列是一种使用规则。你可以拿一段连续内存数组来按栈的规则存取也可以拿一堆节点链表来按栈的规则存取。类比数组和链表就像“砖块”栈和队列就像“建筑图纸”。用砖块既可以盖出“后进先出”结构的塔栈也可以盖出“先进先出”结构的通道队列。三、栈的数组实现 vs 链表实现重点理解这是面试和学习的常见考点。用代码结构来理解不要死记。1. 数组实现栈 (Array-based Stack)核心思想用数组存放元素用一个整数变量top指向栈顶位置。java class ArrayStackE { 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 LinkedStackE { private static class NodeE { E data; NodeE next; Node(E data) { this.data data; } } private NodeE top; // 栈顶指针 private int size; public void push(E e) { NodeE 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快。四、到底用哪个实现面试常问场景推荐实现一般编程 (Java)ArrayDeque(数组实现) - 速度快内存紧凑非常频繁的 push/pop但不确定最大数量链表实现或ArrayDeque自动扩容也足够好要求严格的实时系统不能有扩容停顿链表实现存储基本类型 (int, long 等) 且追求极致性能数组实现 手动管理面试让你手写两者都要会但重点说清楚数组的扩容问题 / 链表的指针操作总结栈和队列是规则数组和链表是存储方式。Java 中直接用ArrayDequenew ArrayDeque()既可以当栈也可以当队列。数组实现栈靠top指针移动连续内存快但有容量限制。链表实现栈靠改变头节点指向无限容量但每个节点多存一个引用。队列的数组实现循环队列比栈复杂需要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()继承自 Collectionjava // 这就是 Java 中标准的栈用法 DequeInteger 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()); // falseDeque 的继承体系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 类不推荐 StackInteger oldStack new Stack(); oldStack.push(1); oldStack.push(2); oldStack.add(0, 999); // 竟然可以在中间插入违反了栈的定义 System.out.println(oldStack.pop()); // 2不是 999混乱三、其他可以作为栈的接口/类1.LinkedList类实现了 Dequejava // LinkedList 也可以当栈用 DequeInteger stack new LinkedList(); stack.push(1); stack.push(2); stack.pop(); // 22.ArrayDeque类最推荐java // 最佳实践 DequeInteger stack new ArrayDeque();3.ConcurrentLinkedDeque类线程安全java // 多线程环境下的栈 DequeInteger concurrentStack new ConcurrentLinkedDeque(); concurrentStack.push(1); concurrentStack.push(2); concurrentStack.pop(); // 线程安全4.BlockingDeque接口阻塞双端队列java // 阻塞版本的栈线程安全 阻塞 BlockingDequeInteger 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 // ✅ 单线程环境 - 用这个 DequeInteger stack new ArrayDeque(); // ✅ 多线程环境 - 用这个 DequeInteger stack new ConcurrentLinkedDeque(); // ✅ 需要阻塞功能 - 用这个 BlockingDequeInteger stack new LinkedBlockingDeque(); // ❌ 不要用这个 StackInteger 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(e)offer(e)容量限制时offer返回falseadd抛异常出队队首删除remove()poll()队列空时poll返回nullremove抛异常查看队首不删除element()peek()队列空时peek返回nullelement抛异常为什么有两套方法抛出异常版add、remove、element— 适用于队列一定非空或有容量的场景。返回特殊值版offer、poll、peek— 更安全推荐日常使用。典型实现java // LinkedList 实现 Queue QueueString queue new LinkedList(); queue.offer(A); queue.offer(B); String head queue.poll(); // A // 查看队首不删除 String peek queue.peek(); // B二、Deque 接口双端队列特点两端都能操作因此功能更强大。核心方法操作位置操作类型抛出异常版返回特殊值版说明队首插入addFirst(e)offerFirst(e)在头部添加队首删除removeFirst()pollFirst()删除并返回头部队首查看getFirst()peekFirst()查看头部不删除队尾插入addLast(e)offerLast(e)在尾部添加队尾删除removeLast()pollLast()删除并返回尾部队尾查看getLast()peekLast()查看尾部不删除Deque 如何当队列用Deque 提供了和 Queue 完全对应的方法Queue 方法Deque 等效方法说明offer(e)offerLast(e)队尾入队poll()pollFirst()队首出队peek()peekFirst()查看队首所以Queue queue new ArrayDeque()完全合法ArrayDeque就是当作队列用的。Deque 如何当栈用重点栈操作Deque 方法说明压栈push(e)等价于addFirst(e)弹栈pop()等价于removeFirst()查看栈顶peek()等价于peekFirst()java // 用 Deque 实现栈Java 官方推荐 DequeInteger stack new ArrayDeque(); stack.push(1); // 压栈 stack.push(2); int top stack.pop(); // 弹栈得到 2 int peek stack.peek(); // 查看栈顶得到 1三、Queue vs Deque 对比总结对比维度QueueDeque操作方向只能队尾进、队首出两端都能进出能否当队列✅ 本身就是队列✅ 可以用offerLast/pollFirst能否当栈❌ 不能✅ 可以用push/pop常用实现LinkedList、PriorityQueueArrayDeque、LinkedList官方推荐场景只需标准 FIFO 时需要栈或双端操作时为什么ArrayDeque比LinkedList快ArrayDeque底层是数组内存连续CPU 缓存命中率高。LinkedList底层是链表每个元素需要额外存储前后指针内存开销大且指针跳转多。所以记住 Java 最佳实践需要队列 →QueueT queue new ArrayDeque()需要栈 →DequeT stack new ArrayDeque()尽量避免用Stack类遗留类性能差尽量避免用LinkedList做队列/栈除非需要 null 或频繁的中间插入删除一句话记忆Queue只能从队尾进、队首出排队Deque两头都能进能出既可以排队也可以叠盘子用ArrayDeque就对了它既能当Queue也能当Deque还能当栈回答面试题java 中栈和队列通常怎么实现→ 用Deque接口配合ArrayDeque实现一、普通队列1.Queue接口上面提及了标准 FIFO 队列实现类PriorityQueue、ConcurrentLinkedQueue、各种阻塞队列的父接口2.Deque接口上面提及了双端队列功能更强大实现类ArrayDeque、LinkedList3.PriorityQueue⭐ 重点掌握特点不是 FIFO而是按优先级出队最小堆实现java QueueInteger 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 // 自定义排序降序 QueueInteger 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 // 多线程环境下安全使用 QueueString queue new ConcurrentLinkedQueue(); // 不需要手动加锁多个线程可以同时 offer/poll二、阻塞队列并发编程核心 重要特点当队列满时入队操作会阻塞等待当队列空时出队操作会阻塞等待。核心接口BlockingQueue比 Queue 多了几个阻塞方法操作抛出异常返回特殊值阻塞等待超时等待入队add(e)offer(e)put(e)offer(e, time, unit)出队remove()poll()take()poll(time, unit)查看element()peek()不支持不支持常用实现类面试高频实现类特点使用场景ArrayBlockingQueue有界数组实现公平锁可选固定大小的生产者-消费者LinkedBlockingQueue可选有界链表实现默认无界常用默认选择PriorityBlockingQueue无界优先级队列需要优先级排序的并发场景DelayQueue延迟队列元素需实现 Delayed定时任务、订单超时取消SynchronousQueue不存储元素直接传递线程间手递手传递任务LinkedTransferQueue无界支持transfer()高并发下的高效传递经典例子生产者-消费者java // 用阻塞队列轻松实现生产者-消费者模式 BlockingQueueInteger 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 TransferQueueString queue new LinkedTransferQueue(); // 生产者必须等消费者取走才继续 queue.transfer(重要消息); // 阻塞直到被 take() // 消费者 String msg queue.take(); // 取走消息生产者解除阻塞四、完整分类总结面试速记分类接口/类核心特点基础队列QueueFIFO 标准接口双端队列Deque两端操作可当栈数组队列ArrayDeque数组实现最快链表队列LinkedList链表实现允许 null优先级队列PriorityQueue按优先级出队堆并发非阻塞ConcurrentLinkedQueueCAS 实现高并发阻塞队列BlockingQueue满/空时阻塞有界阻塞ArrayBlockingQueue固定大小无界阻塞LinkedBlockingQueue常用默认延迟队列DelayQueue延迟出队传递队列SynchronousQueue不存数据手递手传输队列TransferQueue等待消费者接收结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励