一、引言前面我们说了栈Stack这次我们来说说和Stack比较相似的队列Queue先声明Queue同样是比LinkedList和ArrayList要简单许多这一篇博客将从概念和使用来讲解并且会讲解用队列实现栈和用栈实现队列。二、概念队列与栈不同栈是先进后出而队列是先进先出并且只能从队尾进来就像去景区排队一样先排队的可以先进去后来的也必须排到队尾。也就是进行删除的一头是队头进行插入操作的是队尾。在Java里Queue是一个接口底层的通过链表实现的因此我们想创建一个队列的时候是不能直接对Queue实例化的。具体如何使用我会在下面一一解释。三、模拟实现关于模拟实现队列有两种方法分别为用链表、双向链表来实现这里说一下这两种。首先是链表class ListNode { int val; ListNode next; ListNode(int val) { this.val val; } } // 链表实现队列 class MyQueue { // 队头、队尾指针 private ListNode front; private ListNode rear; // 初始化空队列 public MyQueue() { front null; rear null; } // 入队加到尾部 public void enqueue(int val) { ListNode newNode new ListNode(val); if (isEmpty()) { // 空队列时头和尾都指向新节点 front newNode; rear newNode; } else { // 尾插法 rear.next newNode; rear newNode; } } // 出队从头部删 public Integer dequeue() { if (isEmpty()) { System.out.println(队列为空无法出队); return null; } int val front.val; front front.next; // 如果删完变空了rear 也要置空 if (front null) { rear null; } return val; } // 查看队头 public Integer peek() { if (isEmpty()) return null; return front.val; } // 判断空 public boolean isEmpty() { return front null; } }要用链表来实现的话我们要定义两个指针分别指向队头和队尾入队的时候队列为空就让两个指针指向同一个不然就尾插法出队就先存一下队头的值之后之让队头指向当前队头的下一个最后再返回存的值查看队头就很简单了看一眼就知道怎么回事了。然后是双向链表// 双向链表节点 class ListNode { int val; ListNode prev; ListNode next; ListNode(int val) { this.val val; } } // 双向链表实现队列 class MyQueue { private ListNode front; // 队头 private ListNode rear; // 队尾 // 初始化空队列 public MyQueue() { front null; rear null; } // 入队加到队尾 public void enqueue(int val) { ListNode node new ListNode(val); if (isEmpty()) { front node; rear node; } else { rear.next node; node.prev rear; rear node; } } // 出队从队头删 public Integer dequeue() { if (isEmpty()) { System.out.println(队列空了); return null; } int val front.val; // 只有一个节点 if (front rear) { front null; rear null; } else { front front.next; front.prev null; } return val; } // 查看队头 public Integer peek() { return isEmpty() ? null : front.val; } // 判断是否为空 public boolean isEmpty() { return front null; } }双向链表和单向链表思路上是十分相似的只不过要注意一下prev就可以了。下面简单演示一下Queue的使用import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { // 创建队列 QueueString queue new LinkedList(); // 入队操作 queue.add(Apple); queue.add(Banana); queue.offer(Cherry); // 与add()类似但更推荐用于队列 // 查看队首元素不删除 System.out.println(队首元素: queue.peek()); // 出队操作 String removedItem queue.poll(); System.out.println(出队元素: removedItem); // 遍历队列 System.out.println(当前队列内容:); for (String item : queue) { System.out.println(item); } } }四、循环队列前面用链表实现的队列无需提前指定容量无空间浪费但用数组实现普通队列会出现“假溢出”——即rear到达数组末尾时数组前部因出队空出的空间无法利用。循环队列将数组首尾相连解决假溢出问题核心难点是区分队列空和满常见有三种实现方式重点掌握第一种。4.1 循环队列实现方式一牺牲一个位置最常用、教科书标准核心思路故意空出一个数组位置用于区分空和满数组容量比实际可存元素数多1。4.1.1 核心原理与判断条件定义两个指针front指向队头初始0、rear指向队尾下一个位置初始0队列空front rear队列满(rear 1) % 数组长度 front取模运算实现指针循环移动避免超出数组范围。4.1.2 完整代码实现// 数组实现循环队列牺牲一个位置版 class MyCircularQueue { private int[] elem; // 存储元素的数组 private int front; // 队头指针指向队头元素 private int rear; // 队尾指针指向队尾下一个位置 // 构造方法参数为实际容量数组长度实际容量1牺牲一个位置 public MyCircularQueue(int capacity) { elem new int[capacity 1]; front 0; rear 0; } // 入队添加到队尾满则返回false public boolean enQueue(int value) { if (isFull()) { System.out.println(队列已满无法入队); return false; } elem[rear] value; rear (rear 1) % elem.length; // 循环移动 return true; } // 出队移除队头空则返回false public boolean deQueue() { if (isEmpty()) { System.out.println(队列为空无法出队); return false; } front (front 1) % elem.length; // 覆盖式删除 return true; } // 获取队头元素不删除 public int Front() { if (isEmpty()) { System.out.println(队列为空无队头元素); return -1; } return elem[front]; } // 获取队尾元素不删除 public int Rear() { if (isEmpty()) { System.out.println(队列为空无队尾元素); return -1; } // 避免rear为0时出现负下标 int index (rear - 1 elem.length) % elem.length; return elem[index]; } // 判断空 public boolean isEmpty() { return front rear; } // 判断满 public boolean isFull() { return (rear 1) % elem.length front; } }4.1.3 优缺点分析优点实现简单、逻辑清晰无需额外变量性能高效是实际开发首选缺点牺牲1个空间容量较小时浪费比例略高多数场景可忽略。4.2 循环队列实现方式二使用计数器count最直观核心思路不牺牲空间增加count变量记录元素个数直接通过count判断空和满逻辑直观。4.2.1 核心原理与判断条件队列空count 0队列满count 数组长度指针移动同第一种方式入队count出队count--。4.2.2 完整代码实现// 数组实现循环队列计数器版 class MyCircularQueue2 { private int[] elem; // 存储元素的数组 private int front; // 队头指针 private int rear; // 队尾指针 private int count; // 记录元素个数 // 构造方法数组长度实际容量 public MyCircularQueue2(int capacity) { elem new int[capacity]; front 0; rear 0; count 0; } // 入队 public boolean enQueue(int value) { if (isFull()) { System.out.println(队列已满无法入队); return false; } elem[rear] value; rear (rear 1) % elem.length; count; return true; } // 出队 public boolean deQueue() { if (isEmpty()) { System.out.println(队列为空无法出队); return false; } front (front 1) % elem.length; count--; return true; } // 获取队头、队尾元素同第一种方式 public int Front() { if (isEmpty()) { System.out.println(队列为空无队头元素); return -1; } return elem[front]; } public int Rear() { if (isEmpty()) { System.out.println(队列为空无队尾元素); return -1; } int index (rear - 1 elem.length) % elem.length; return elem[index]; } public boolean isEmpty() { return count 0; } public boolean isFull() { return count elem.length; } }4.2.3 优缺点分析优点不浪费空间逻辑直观适合初学者缺点需额外维护count变量多一步更新操作。4.3 循环队列实现方式三使用标记位flag考试常考核心思路不牺牲空间、不使用计数器用boolean类型flag标记最后一次操作入队/出队区分空和满面试高频考点。4.3.1 核心原理与判断条件flag false最后一次是出队或初始空队列flag true最后一次是入队队列空front rear flag false队列满front rear flag true。4.3.2 完整代码实现// 数组实现循环队列标记位版 class MyCircularQueue3 { private int[] elem; // 存储元素的数组 private int front; // 队头指针 private int rear; // 队尾指针 private boolean flag; // 标记位true入队false出队/初始 public MyCircularQueue3(int capacity) { elem new int[capacity]; front 0; rear 0; flag false; // 初始空队列 } // 入队成功后标记为true public boolean enQueue(int value) { if (isFull()) { System.out.println(队列已满无法入队); return false; } elem[rear] value; rear (rear 1) % elem.length; flag true; return true; } // 出队成功后标记为false public boolean deQueue() { if (isEmpty()) { System.out.println(队列为空无法出队); return false; } front (front 1) % elem.length; flag false; return true; } // 获取队头、队尾元素同前 public int Front() { if (isEmpty()) { System.out.println(队列为空无队头元素); return -1; } return elem[front]; } public int Rear() { if (isEmpty()) { System.out.println(队列为空无队尾元素); return -1; } int index (rear - 1 elem.length) % elem.length; return elem[index]; } public boolean isEmpty() { return front rear !flag; } public boolean isFull() { return front rear flag; } }4.3.3 优缺点分析优点不牺牲空间、无需计数器仅用一个标记位缺点逻辑稍复杂每次操作需更新标记位易出错。总结三种方式核心都是解决“空满区分”实际开发优先选第一种牺牲一个位置笔试重点掌握第三种标记位第二种计数器适合初学者理解。五、双端队列Deque双端队列Double Ended Queue是队列的扩展允许在队头和队尾同时进行入队、出队操作兼具队列和栈的特性。核心特点无固定进出规则队头、队尾均可插入和删除底层可通过双向链表或数组实现。 Java中Deque是接口常用实现类有LinkedList、ArrayDeque核心方法addFirst()、addLast()、removeFirst()、removeLast()可灵活实现队列或栈的功能。以下便是双端队列的演示。import java.util.Deque; import java.util.LinkedList; public class DequeDemo { public static void main(String[] args) { // 1. 创建Deque实例LinkedList实现 DequeInteger deque new LinkedList(); // 2. 队头/队尾入队 deque.addFirst(1); // 队头入队[1] deque.addLast(2); // 队尾入队[1, 2] deque.addLast(3); // 队尾入队[1, 2, 3] // 3. 队头/队尾出队 deque.removeFirst(); // 队头出队[2, 3] deque.removeLast(); // 队尾出队[2] // 4. 查看队头/队尾不删除 System.out.println(deque.getFirst()); // 输出2 System.out.println(deque.getLast()); // 输出2 } }六、栈实现队列栈是先进后出LIFO队列是先进先出FIFO我们可以通过两个栈的配合模拟实现队列的功能核心思路是利用两个栈的“倒腾”将栈的先进后出转化为队列的先进先出。6.1 核心原理定义两个栈stack1和stack2分工明确stack1作为“入队栈”专门负责接收新元素push操作stack2作为“出队栈”专门负责弹出元素pop、peek操作核心逻辑当stack2为空时将stack1中的所有元素依次弹出并压入stack2此时stack2的栈顶就是队列的队头实现先进先出。6.2 完整代码实现class MyQueue { StackInteger stack1; // 入队栈负责接收新元素 StackInteger stack2; // 出队栈负责弹出元素 // 初始化创建两个空栈 public MyQueue() { stack1 new Stack(); stack2 new Stack(); } // 入队将元素压入stack1入队栈 public void push(int x) { stack1.push(x); } // 出队弹出队头元素先进先出 public int pop() { // 队列空两个栈都空返回-1 if(empty()){ return -1; } // 出队栈为空时将入队栈所有元素倒腾到出队栈 else if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); // stack1弹出stack2压入反转顺序 } } // 出队栈栈顶就是队头弹出即可 return stack2.pop(); } // 查看队头元素不弹出 public int peek() { // 队列空返回-1 if(empty()){ return -1; } // 出队栈为空时先倒腾元素 else if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } // 出队栈栈顶就是队头直接查看 return stack2.peek(); } // 判断队列是否为空两个栈都为空队列才为空 public boolean empty() { return stack1.isEmpty() stack2.isEmpty(); } }6.3 核心说明1. 入队操作直接压入stack1时间复杂度O(1)2. 出队、查看队头仅当stack2为空时才倒腾stack1的元素整体平均时间复杂度O(1)3. 空判断必须两个栈都为空才说明队列为空避免遗漏元素。七、队列实现栈与“栈实现队列”思路类似队列是先进先出FIFO栈是先进后出LIFO我们可以通过两个队列的配合将队列的先进先出转化为栈的先进后出核心是利用一个队列存储元素另一个队列辅助“倒腾”元素找到栈顶队列的队尾。7.1 核心原理定义两个队列qu1和qu2分工协作核心是“始终保持一个队列有元素另一个队列为空”qu1、qu2交替作为“存储队列”存放当前所有元素和“辅助队列”临时转移元素入队push将元素加入当前非空的队列若均为空默认加入qu1出队pop、查看栈顶top将存储队列中除最后一个元素外的所有元素转移到辅助队列剩余的最后一个元素就是栈顶完成操作后辅助队列变为新的存储队列。7.2 完整代码实现class MyStack { public QueueInteger qu1; // 队列1交替作为存储队列/辅助队列 public QueueInteger qu2; // 队列2交替作为辅助队列/存储队列 // 初始化创建两个空队列 public MyStack() { qu1 new LinkedList(); qu2 new LinkedList(); } // 入栈将元素加入当前非空的队列均空则加入qu1 public void push(int x) { if(!qu1.isEmpty()){ qu1.offer(x); // qu1非空加入qu1 }else if(!qu2.isEmpty()){ qu2.offer(x); // qu2非空加入qu2 }else{ qu1.offer(x); // 均为空默认加入qu1 } } // 出栈弹出栈顶元素先进后出 public int pop() { if(empty()){ // 两个队列都空栈为空返回-1 return -1; } // qu1非空将qu1中除最后一个元素外全部转移到qu2 if(!qu1.isEmpty()){ int sizequ1.size(); for(int i0;isize-1;i){ qu2.offer(qu1.poll()); } return qu1.poll(); // 剩余的最后一个元素就是栈顶弹出 }else { // qu2非空同理将qu2元素转移到qu1 int sizequ2.size(); for(int i0;isize-1;i){ qu1.offer(qu2.poll()); } return qu2.poll(); } } // 查看栈顶元素不弹出 public int top() { if(empty()){ // 栈为空返回-1 return -1; } // qu1非空转移所有元素到qu2记录最后一个元素栈顶 if(!qu1.isEmpty()){ int sizequ1.size(); int val-1; for(int i0;isize;i){ valqu1.poll(); qu2.offer(val); } return val; // 返回记录的栈顶元素 }else { // qu2非空同理转移所有元素到qu1记录栈顶 int sizequ2.size(); int val-1; for(int i0;isize;i){ valqu2.poll(); qu1.offer(val); } return val; } } // 判断栈是否为空两个队列都为空栈才为空 public boolean empty() { return qu1.isEmpty() qu2.isEmpty(); } }7.3 核心说明1. 入栈操作直接加入非空队列时间复杂度O(1)2. 出栈、查看栈顶需转移除最后一个元素外的所有元素时间复杂度O(n)3. 空判断两个队列均为空时栈才为空确保不遗漏任何元素4. 核心技巧通过两个队列交替作为存储和辅助队列巧妙将队列的“先进先出”转化为栈的“先进后出”。八、总结总而言之栈和队列是十分相似的我们在记忆的时候可以把两个放在一起记忆但也千万不能忘记了Queue是一个接口要用LikedList来实现这也是新手常犯的错误。接口就是个“空架子”自己不能直接new出来用就像你不能拿着“手机”的概念直接打电话一样得有具体的实现类才行。咱们写代码的时候最常用的就是LinkedList用LinkedList去实现Queue才能正常用它的入队、出队功能很多新手一上来就写new Queue()直接报错血的教训一定要记牢总的来说栈和队列都是基础款数据结构不用搞太复杂把它们的特性、实现方式和易错点记牢再稍微练两遍日常开发、笔试面试都能轻松应对主打一个“学会就够用”再也不用为这俩货头疼啦。另外小提一下Stack类 Java 官方已不推荐最好提一句实际开发用Deque代替栈会比较好一点。