JAVA数据结构与算法：队列

队列队列只允许在⼀端进⾏插⼊数据操作在另⼀端进⾏删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)⼊队列进⾏插⼊操作的⼀端称为队尾Tail/Rear出队列进⾏删除操作的⼀端称为队头Head/Front队列的使用在Java中Queue是个接⼝底层是通过链表实现的方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检测队列是否为空队列的模拟实现队列的接口packageDataStructure.DS_Queue;publicinterfaceQueueInterface{// 入队队尾添加元素voidenqueue(intval);// 出队删除并返回队首元素队列为空抛异常intdequeue();// 获取队首元素不删除队列为空抛异常intgetFront();// 判断队列是否为空booleanisEmpty();// 获取队列当前元素个数intsize();// 清空队列所有元素voidclear();// 判断队列是否包含指定值booleancontains(intval);}入队队尾添加元素/** * 入队操作将元素添加到队尾 * param val 要添加的元素值 */Overridepublicvoidenqueue(intval){ListNodenewNodenewListNode(val);if(lastnull){firstlastnewNode;}else{last.nextnewNode;newNode.prelast;lastnewNode;}size;}出队删除并返回队首元素队列为空抛异常/** * 出队操作移除并返回队头元素 * return 被移除的队头元素的值 * throws EmptyStackException 如果队列为空 */Overridepublicintdequeue(){if(isEmpty()){thrownewEmptyStackException();}intdatafirst.val;if(firstlast){firstlastnull;}else{firstfirst.next;first.prenull;}size--;returndata;}获取队首元素不删除/** * 获取队头元素的值但不移除 * return 队头元素的值 * throws EmptyStackException 如果队列为空 */OverridepublicintgetFront(){if(isEmpty()){thrownewEmptyStackException();}returnfirst.val;}判断队列是否为空/** * 检查队列是否为空 * return 如果队列为空返回true否则返回false */OverridepublicbooleanisEmpty(){returnsize0;}获取队列当前元素个数/** * 获取队列中元素的数量 * return 队列中元素的数量 */Overridepublicintsize(){returnsize;}清空队列所有元素/** * 清空队列 */Overridepublicvoidclear(){firstlastnull;size0;}判断队列是否包含指定值/** * 检查队列是否包含指定值的元素 * param val 要查找的值 * return 如果队列中包含该值返回true否则返回false */Overridepublicbooleancontains(intval){ListNodecurfirst;while(cur!null){if(cur.valval){returntrue;}curcur.next;}returnfalse;}队列模拟实现完整代码packageDataStructure.DS_Queue;importjava.util.EmptyStackException;/** * 自定义队列类实现了QueueInterface接口 * 使用双向链表实现队列数据结构 */publicclassMyQueueimplementsQueueInterface{/** * 静态内部类表示队列中的节点 * 采用双向链表结构每个节点包含值、前驱和后继指针 */staticclassListNode{publicintval;// 节点存储的值publicListNodenext;// 指向后继节点的指针publicListNodepre;// 指向前驱节点的指针/** * 构造函数初始化节点 * param val 节点存储的值 */publicListNode(intval){this.valval;this.nextnull;this.prenull;}}ListNodefirstnull;//队头节点ListNodelastnull;//队尾节点intsize0;// 队列中元素的数量/** * 入队操作将元素添加到队尾 * param val 要添加的元素值 */Overridepublicvoidenqueue(intval){ListNodenewNodenewListNode(val);if(lastnull){firstlastnewNode;}else{last.nextnewNode;newNode.prelast;lastnewNode;}size;}/** * 出队操作移除并返回队头元素 * return 被移除的队头元素的值 * throws EmptyStackException 如果队列为空 */Overridepublicintdequeue(){if(isEmpty()){thrownewEmptyStackException();}intdatafirst.val;if(firstlast){firstlastnull;}else{firstfirst.next;first.prenull;}size--;returndata;}/** * 获取队头元素的值但不移除 * return 队头元素的值 * throws EmptyStackException 如果队列为空 */OverridepublicintgetFront(){if(isEmpty()){thrownewEmptyStackException();}returnfirst.val;}/** * 检查队列是否为空 * return 如果队列为空返回true否则返回false */OverridepublicbooleanisEmpty(){returnsize0;}/** * 获取队列中元素的数量 * return 队列中元素的数量 */Overridepublicintsize(){returnsize;}/** * 清空队列 */Overridepublicvoidclear(){firstlastnull;size0;}/** * 检查队列是否包含指定值的元素 * param val 要查找的值 * return 如果队列中包含该值返回true否则返回false */Overridepublicbooleancontains(intval){ListNodecurfirst;while(cur!null){if(cur.valval){returntrue;}curcur.next;}returnfalse;}}循环队列循环队列是一种特殊的队列数据结构它允许队列的头尾相接形成一个环。循环队列解决了普通队列的一些缺点空间浪费和在元素出队后无法再次入队的问题循环队列通常使用数组来实现其内部有两个指针front和rear分别指向队列的第一个元素和最后一个元素的下一个位置。初始化时front和rear都指向数组的第一个位置。当往循环队列中插入元素时将元素放入rear指向的位置并将rear指针向后移动一位。如果rear指针到达数组的尾部则将其指向数组的起始位置。当从循环队列中删除元素时将front指针向后移动一位表示该元素已出队列。如果front指针到达数组的尾部则将其指向数组的起始位置使用循环队列可以实现高效的元素入队和出队操作因为循环队列的空间利用率较高。当队列满时rear指针和front指针会指向同一个位置此时队列被认为是满的。而在普通队列中即使队列中还有空闲位置当rear指针到达数组的尾部时无法再向队列中插入元素循环队列通过循环利用数组空间解决了普通队列的空间浪费和无法再次入队的问题提高了队列的空间利用率和性能如何区别队列空与满通过添加size属性记录在队列的结构中额外增加一个整型变量 size 来记录当前队列中有效元素的个数判断为空当 size 0 时队列为空判断为满当 size capacity 即数组的总长度时队列已满特点逻辑非常简单直观出队入队时只需对 size 进行加减即可不需要纠结下标的重合问题publicclassCircularQueueBySize{privateint[]array;privateintfront;privateintrear;privateintsize;// 记录有效元素个数publicCircularQueueBySize(intcapacity){arraynewint[capacity];front0;rear0;size0;}publicbooleanenQueue(intvalue){if(sizearray.length){returnfalse;// 队列已满}array[rear]value;rear(rear1)%array.length;// 下标最后再往后的小技巧size;returntrue;}publicbooleandeQueue(){if(size0){returnfalse;// 队列为空}front(front1)%array.length;size--;returntrue;}publicbooleanisEmpty(){returnsize0;}publicbooleanisFull(){returnsizearray.length;}}保留⼀个位置为了能使用 Q.rear 和 Q.front 来区别是队空还是队满我们常常认为出现特定的情况即为队满的情况。具体做法是数组中始终保留一个空位不存数据判断为空front rear判断为满当尾指针的下一个位置就是头指针时即 (rear 1) % capacity front 时认为队列已满特点这是最经典、最常用的处理循环队列的方式。不需要引入额外的计数变量但代价是实际容量比数组长度少1。publicclassCircularQueueByReserve{privateint[]array;privateintfront;privateintrear;publicCircularQueueByReserve(intcapacity){// 因为要保留一个位置为了能存下 capacity 个元素数组长度需要1arraynewint[capacity1];front0;rear0;}publicbooleanenQueue(intvalue){if(isFull()){returnfalse;// 队列已满}array[rear]value;rear(rear1)%array.length;returntrue;}publicbooleandeQueue(){if(isEmpty()){returnfalse;// 队列为空}front(front1)%array.length;returntrue;}publicbooleanisEmpty(){returnfrontrear;}publicbooleanisFull(){// 重点判断尾结点的下一个位置是不是头结点return(rear1)%array.lengthfront;}}使⽤标记通过引入一个布尔类型的标志位如 isFull来区分状态初始状态队列为空时front rear 0标志位 isFull false判断为满返回 isFull。每次入队时检查 rear 是否与 front 重合如果重合设置 isFull true表示队列已满判断为空返回 !isFull front rear。出队时移动 front 指针必然不满因此设置 isFull false特点可以完全利用数组的所有空间不需要像方法二那样牺牲一个位置但需要维护额外的布尔标记publicclassCircularQueueByFlag{privateint[]array;privateintfront;privateintrear;privatebooleanisFull;// 标记位privateintcapacity;publicCircularQueueByFlag(intcapacity){this.capacitycapacity;this.arraynewint[capacity];this.front0;this.rear0;this.isFullfalse;}publicbooleanenQueue(intvalue){if(isFull){//[cite: 1]returnfalse;// 队列已满[cite: 1]}array[rear]value;//[cite: 1]rear(rear1)%capacity;//[cite: 1]if(rearfront){//[cite: 1]isFulltrue;//[cite: 1]}returntrue;//[cite: 1]}publicbooleandeQueue(){if(isEmpty()){//[cite: 1]returnfalse;//队列为空[cite: 1]}intitemarray[front];//[cite: 1]front(front1)%capacity;//[cite: 1]isFullfalse;//[cite: 1]returntrue;//[cite: 1]}publicbooleanisEmpty(){// 根据标记位和指针综合判断空return!isFullfrontrear;//[cite: 1]}publicbooleanisFull(){returnisFull;//[cite: 1]}}