数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)（上）：https://developer.aliyun.com/article/1513405
力扣链接：622. 设计循环队列
难度中等
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。
typedef struct { } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { } bool myCircularQueueDeQueue(MyCircularQueue* obj) { } int myCircularQueueFront(MyCircularQueue* obj) { } int myCircularQueueRear(MyCircularQueue* obj) { } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { } bool myCircularQueueIsFull(MyCircularQueue* obj) { } void myCircularQueueFree(MyCircularQueue* obj) { } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */
解析：
这道题用数组和链表都能实现，各有优劣
要注意下面的判空和判满问题：
判空和判满问题可以使用添加一个size解决，但比较官方是多开一个空间：
【0】 【1】 【2】 【3】 【4】
一般情况tail+1等于front 如上面tail 是【1】，front是【2】（1+1）%（4+1）==2也是满
但是如果tail是【4】，front是【0】，tail+1等于front就不能判断
用上面的公式（4+1）%（4+1）==0 就是满
链表空的情况和上面一样，满的情况是这样：
数组实现 函数bool myCircularQueueDeQueue(MyCircularQueue* obj)的图：
数组实现的代码：（有空可以写写链表实现的）
typedef struct { //匿名结构体 int* arr; int front; int tail; int k; } MyCircularQueue; bool myCircularQueueIsEmpty(MyCircularQueue* obj);//可以先实现这两个 声明后下面可以用 bool myCircularQueueIsFull(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //OJ题一般都会开辟空间成功，不用判空了 cq->arr = (int*)malloc(sizeof(int) * (k + 1));//初始化 开k+1个空间 cq->front = cq->tail = 0; cq->k = k; return cq; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { //enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。 //(失败返回假)满了就失败 //先滑到下面实现myCircularQueueIsFull和myCircularQueueIsEmpty，记得在上面声明 if (myCircularQueueIsFull(obj)) { return false; } obj->arr[obj->tail] = value; obj->tail++; obj->tail %= (obj->k + 1);//超出k+1就模到0从头开始，没超，模和没模一样 return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { //deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。 if (myCircularQueueIsEmpty(obj)) { return false; } obj->front++; //不理解可以看上面的图 obj->front %= (obj->k + 1); //超出k+1就模到0从头开始，没超，模和没模一样 return true; } int myCircularQueueFront(MyCircularQueue* obj) { //Front: 从队首获取元素。如果队列为空，返回 -1 。 if (myCircularQueueIsEmpty(obj)) { return -1; } return obj->arr[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { //Rear: 获取队尾元素。如果队列为空，返回 -1 。 if (myCircularQueueIsEmpty(obj)) { return -1; } if (obj->tail == 0)//如果tail在0上，返回tail的上一个就是k { return obj->arr[obj->k]; } else { return obj->arr[obj->tail - 1]; } } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail; //看上面图的判空和判满条件 } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->tail + 1) % (obj->k + 1) == obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); free(obj); //有两层 结构体里面有个数组 }
五、概念选择题
1.下列关于队列的叙述错误的是（ ）
A.队列可以使用链表实现
B.队列是一种“先入先出”的数据结构
C.数据出队列时一定只影响尾指针
D.数据入队列时一定从尾部插入
2.用无头单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时（ ）
A.仅修改队头指针
B.队头、队尾指针都要修改
C.队头、队尾指针都可能要修改
D.仅修改队尾指针
3.下列关于栈的叙述正确的是（ ）
A.栈是一种“先进先出”的数据结构
B.栈可以使用链表或顺序表来实现
C.栈只能在栈底插入数据
D.栈不能删除数据
4.一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ）
A.ABCDE
B.EDCBA
C.DCEBA
D.ECDBA
5.链栈与顺序栈相比，比较明显的优点是（ ）
A.插入操作更加方便
B.删除操作更加方便
C.入栈时不需要扩容
6.以下不是队列的基本运算的是（ ）
A.从队尾插入一个新元素
B.从队列中删除队尾元素
C.判断一个队列是否为空
D.读取队头元素的值
7.(多选)下面关于栈和队列的说法中错误的是（ ）
A.队列和栈通常都使用链表实现
B.队列和栈都只能从两端插入、删除数据
C.队列和栈都不支持随机访问和随机插入
D.队列是“先入先出”，栈是“先入后出”
8.下列关于用栈实现队列的说法中错误的是（ ）
A.用栈模拟实现队列可以使用两个栈，一个栈模拟入队列，一个栈模拟出队列
B.每次出队列时，都需要将一个栈中的全部元素导入到另一个栈中，然后出栈即可
C.入队列时，将元素直接往模拟入队列的栈中存放即可
D.入队列操作时间复杂度为O(1)
9.下列关于顺序结构实现循环队列的说法，正确的是（ ）
A.循环队列的长度通常都不固定
B.直接用队头和队尾在同一个位置可以判断循环队列是否为满
C.通过设置计数的方式可以判断队列空或者满
D.循环队列是一种非线性数据结构
10.现有一循环队列，其队头为front，队尾为rear，循环队列长度为N,最多存储N-1个数据。其队内有效长度为（ ）
A.(rear - front + N) % N + 1
B.(rear - front + N) % N
C.(rear - front) % (N + 1)
D.(rear - front + N) % (N - 1)
答案：
1答案：C
出队操作，一定会影响头指针，如果出队之后，队列为空，会影响尾指针。
2.答案：C
出队操作，一定会修改头指针，如果出队之后，队列为空，需要修改尾指针。
3.答案：B
A错误：栈是一种后进先出的数据结构，队列是先进先出的
B正确：顺序表和链表都可以用来实现栈，不过一般都使用顺序表，因为栈想当于是阉割版的顺序表，只用到了顺序表的尾插和尾删操作，顺序表的尾插和尾删不需要搬移元素效率非常高，故一般都是使用顺序表实现
C错误：栈只能在栈顶进行输入的插入和删除操作
D错误：栈是有入栈和出栈操作，出栈就是从栈中删除一个元素
4.答案：D
此题在校招选择题中出现较频繁，稳妥的做法是画图逐个选项检测，大概率是不会出错的
如果是E先出，说明ABCDE都已经全部入栈，E出栈之后，此时栈顶元素是D，如果再要出栈应该是D，而不应该是C。
5.答案：C
A错误，如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，因此使用顺序结构实现栈更简单
B错误，原因参考A
C正确，链式结构实现栈时，每次入栈相当于链表中头插一个节点，没有扩容一说
6.答案：B
队列只能从队头删除元素。
7.答案：AB
A错误：栈是尾部插入和删除，一般使用顺序表实现，队列是头部删除尾部插入，一般使用链表实现
B错误：栈是后进先出，尾部插入和删除；队列是先进先出，尾部插入头部删除
C正确：栈只能访问栈顶元素，不支持随机访问，队列也不支持
D正确：栈和队列的特性
8.答案：B
选项B中，一个栈模拟入队列，一个栈模拟出队列，出队列时直接弹出模拟出队列栈的栈顶元素，当该栈为空时，将模拟入队列栈中所有元素导入即可，不是每次都需要导入元素，故错误
选项A中，栈和队列的特性是相反的，一个栈实现不了队列
选项C中，一个栈模拟入队列，一个栈模拟出队列，入队列时，将元素直接往模拟入队列的栈中存放
选项D中，入队列就是将元素放到栈中，因此时间复杂度就是O(1)
9.答案：C
队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的
A错误：循环队列的长度都是固定的
B错误：队头和队尾在同一个位置时 队列可能是空的，也可能是满的，因此无法判断
C正确：设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空
D错误：循环队列也是队列的一种，是一种特殊的线性数据结构
10答案：B
有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。
