循环、双向、链式、数组一文搞懂队列( 二 ) _队列

是否为空：return rear == front;
【循环、双向、链式、数组一文搞懂队列】大小：return (rear+maxsize-front)%maxsize; 这里很容易理解，一张图就能解释清楚，无论是front实际在前在后都能满足要求。

文章插图

这里面有几个大家需要注意的，就是指标相加如果遇到最后需要转到头的话。可以判断是否到数组末尾位置。也可以直接+1求余。其中maxsize是数组实际大小。
具体实现：

public class MyCircularQueue {private int data[];// 数组容器private int front;// 头private int rear;// 尾private int maxsize;// 最大长度public MyCircularQueue(int k) {data = https://www.isolves.com/it/cxkf/sf/2021-09-16/new int[k+1];front = 0;rear = 0;maxsize = k+1;}public boolean enQueue(int value){if (isFull())returnfalse;else {data[rear] = value;rear=(rear + 1) % maxsize;}returntrue;}public boolean deQueue() {if (isEmpty())return false;else {front=(front+1)%maxsize;}returntrue;}public int Front() {if(isEmpty())return -1;return data[front];}public int Rear() {if(isEmpty())return -1;return data[(rear-1+maxsize)%maxsize];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear + 1) % maxsize == front;}}

循环队列(链表实现)

对于链表实现的队列，要根据先进先出的规则考虑头和尾的位置

我们知道队列是先进先出的，对于链表，我们能采用单链表尽量采用单链表，能方便尽量方便，同时还要兼顾效率。使用链表大概有两个实现方案：
方案一如果队列头设在链表尾，队列尾设在链表头。那么队尾进队插入在链表头部插入没问题，容易实现，但是如果队头删除在链表尾部进行，如果不设置尾指针要遍历到队尾，但是设置尾指针删除需要将它前驱节点需要双向链表，都挺麻烦的。
方案二如果队列头设在链表头，队列尾设在链表尾，那么队尾进队插入在链表尾部插入没问题(用尾指针可以直接指向next)，容易实现，如果队头删除在链表头部进行也很容易，就是我们前面常说的头节点删除节点。
所以我们最终采取的是方案2的带头节点、带尾指针的单链表!
主要操作为：
初始化：设立一个头结点，是front和rear都先指向它。
入队：rear.next=va;rear=va;（va为被插入节点）

文章插图

出队：队不空，front.next=front.next.next;经典带头节点删除，但是如果仅有一个节点删除时候，需要多加一个rear=front，不然rear就失联啦。

文章插图

是否为空：return rear == front; 或者自定义维护len判断return len==0
大小：节点front遍历到rear的个数，或者自定义维护len直接返回(这里并没实现) 。
实现代码：

public class MyCircularQueue{class node {int data;// 节点的结果node next;// 下一个连接的节点public node() {}public node(int data) {this.data = https://www.isolves.com/it/cxkf/sf/2021-09-16/data;}}node front;//相当于head 带头节点的node rear;//相当于tail/endint maxsize;//最大长度int len=0;public MyCircularQueue(int k) {front=new node(0);rear=front;maxsize=k;len=0;}public boolean enQueue(int value){if (isFull())returnfalse;else {node va=new node(value);rear.next=va;rear=va;len++;}returntrue;}public boolean deQueue() {if (isEmpty())return false;else {front.next=front.next.next;len--;//注意 如果被删完 需要将rear指向frontif(len==0)rear=front;}returntrue;}public int Front() {if(isEmpty())return -1;return front.next.data;}public int Rear() {if(isEmpty())return -1;return rear.data;}public boolean isEmpty() {returnlen==0;//return rear == front;}public boolean isFull() {return len==maxsize;}}

双向队列(加餐)设计实现双端队列，其实你经常使用的ArrayDeque就是一个经典的双向队列，其基于数组实现，效率非常高。我们这里实现的双向队列模板基于力扣641 设计循环双端队列。
你的实现需要支持以下操作：