数据结构：队列（Queue）详解

数据结构队列Queue详解一、队列基本概念队列是一种特殊的线性表遵循先进先出FIFO, First In First Out原则。队头Front/Head执行删除、出队操作的一端队尾Rear/Tail执行插入、入队操作的一端简单理解就像日常排队先来的人先办理事务后来的排在队尾。二、Java 中队列的使用Queue是接口本身不能直接实例化常用LinkedList实现该接口。1. 常用核心方法方法作用offer(E e)元素入队队尾添加poll()队头元素出队并返回该元素peek()获取队头元素不删除size()获取队列元素个数isEmpty()判断队列是否为空2. 代码示例importjava.util.LinkedList;importjava.util.Queue;publicclassQueueTest{publicstaticvoidmain(String[]args){// 实例化队列QueueIntegerqueuenewLinkedList();// 入队queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);System.out.println(队列元素个数queue.size());System.out.println(队头元素queue.peek());// 出队queue.poll();System.out.println(执行一次出队后队头元素queue.poll());if(queue.isEmpty()){System.out.println(队列为空);}else{System.out.println(剩余元素个数queue.size());}}}三、队列模拟实现链式结构队列优先使用链式结构实现避免顺序队列出队时大量元素搬运的问题。下面基于双向链表手写简易队列publicclassMyQueue{// 双向链表节点publicstaticclassListNode{ListNodenext;ListNodeprev;intvalue;ListNode(intvalue){this.valuevalue;}}privateListNodefirst;// 队头privateListNodelast;// 队尾privateintsize;// 元素个数// 入队队尾添加节点publicvoidoffer(inte){ListNodenewNodenewListNode(e);if(firstnull){// 空队列firstnewNode;lastnewNode;}else{last.nextnewNode;newNode.prevlast;lastnewNode;}size;}// 出队删除队头节点publicintpoll(){if(firstnull){thrownewRuntimeException(队列为空无法出队);}intvalfirst.value;if(firstlast){// 只剩一个节点firstnull;lastnull;}else{firstfirst.next;first.prev.nextnull;first.prevnull;}size--;returnval;}// 获取队头元素publicintpeek(){if(firstnull){thrownewRuntimeException(队列为空);}returnfirst.value;}// 获取元素个数publicintsize(){returnsize;}// 判断是否为空publicbooleanisEmpty(){returnfirstnull;}}四、循环队列1. 概念普通顺序队列会出现假溢出问题循环队列将数组首尾相连形成环形充分利用数组空间底层基于数组实现常用于生产者-消费者模型。2. 核心下标计算规则数组长度为array.length向后移动下标index (index offset) % array.length向前移动下标index (index array.length - offset) % array.length3. 区分队空 队满常用三种方式额外增加size属性记录元素数量简单直观数组预留一个空闲位置区分空和满增加isFull标记位4. 标记位版循环队列实现publicclassCircularQueue{privateint[]array;privateintfront;// 队头下标privateintrear;// 队尾下标privatebooleanisFull;// 队列满标记publicCircularQueue(intcapacity){arraynewint[capacity];front0;rear0;isFullfalse;}// 入队publicbooleanenQueue(intvalue){if(isFull){returnfalse;}array[rear]value;rear(rear1)%array.length;if(rearfront){isFulltrue;}returntrue;}// 出队publicbooleandeQueue(){if(isEmpty()){returnfalse;}front(front1)%array.length;isFullfalse;returntrue;}// 判断队列是否为空publicbooleanisEmpty(){return!isFullfrontrear;}// 判断队列是否已满publicbooleanisFull(){returnisFull;}}五、双端队列Deque1. 概念双端队列Double Ended QueueDeque允许两端同时进行入队、出队操作是Queue的子接口。队头、队尾都可以添加/删除元素Java 中LinkedList、ArrayDeque都实现了Deque接口2. 使用场景可当做普通队列使用先进先出可当做栈使用后进先出日常开发中推荐用Deque替代传统Stack类3. 简单示例importjava.util.Deque;importjava.util.ArrayDeque;publicclassDequeTest{publicstaticvoidmain(String[]args){DequeIntegerdequenewArrayDeque();// 队尾入队deque.offerLast(1);deque.offerLast(2);// 队头入队deque.offerFirst(0);// 队头出队System.out.println(deque.pollFirst());// 队尾出队System.out.println(deque.pollLast());}}六、常见面试考点队列与栈的区别先进先出 vs 后进先出手写链式队列、循环队列经典算法题用队列实现栈、用栈实现队列循环队列判空、判满的逻辑区分