【数据结构】栈与队列经典选择题

🚀write in front🚀
📜所属专栏：
🛰️博客主页：睿睿的博客主页
🛰️代码仓库：🎉VS2022_C语言仓库
🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！
关注我，关注我，关注我，你们将会看到更多的优质内容！！

前言：

  在前面的学习中外面学习了栈与队列。但是似乎对于栈与队列的理解却很潜，今天通过这些选择题和oj题来加深认识。

例题1：

答案：C
在这里我们要先弄清楚栈的实现方法：

  顺序表和链表都可以用来实现栈，不过一般都使用顺序表，因为栈相当于是阉割版的顺序表，只用到了顺序表的尾插和尾删操作，顺序表的尾插和尾删不需要搬移元素效率非常高，故一般都是使用顺序表实现。
  当然，我们也可以通过链表的头插和头删来实现栈，头插与头删也正好满足了栈的“先进后出“的性质。
  此时，链表的优点就出来了，每次入栈相当于链表中头插一个节点，没有扩容一说。

例题2：

答案：A B

A错误：栈是尾部插入和删除，一般使用顺序表实现，队列是头部删除尾部插入，一般使用链表实现

B错误：栈是后进先出，尾部插入和删除；队列是先进先出，尾部插入头部删除

C正确：栈只能访问栈顶元素，不支持随机访问，队列也不支持

D正确：栈和队列的特性

例题3：

  既然栈两种线性表示都能实现，队列呢？队列的链表实现我们已经实现了，现在我们来看看用顺序表实现队列：
循环队列

因为队列长度有限，所以我们要及时的判断什么时候队列满了。那么怎么判断队列是否满了呢？
如果我们通过队尾和队顶是否相等来判断是否填满就会发现，在队列空的时候，队尾也等于对队顶。所以我们不能通过这种方法来判断：


那么我们该如何解决呢？
方法1：

加一个size来计数

方法2：
多添加一个位置：

空的情况：

满的情况：

下面我们就以方法2来实现代码：

typedef struct 
{int *a;int front;int rear;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));obj->k=k;obj->front=obj->rear=0;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->rear==obj->front;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{return (obj->rear+1)%(obj->k+1)==obj->front;
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(myCircularQueueIsFull(obj))return false;obj->a[obj->rear++]=value;obj->rear%=(obj->k+1);return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front%=(obj->k+1);return true;}int myCircularQueueFront(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->a);free(obj);
}

这里我们只要关注这几点，其他的都很好实现：

空的情况：

满的情况：

  在这里我们学到了如何在数组里建立循环！那就是通过mod数组的长度，就可以使数组循环起来！

找队尾：

  尾部其实就是rear的后面一个元素，即rear-1，但是当rear等于0的时候，-1就会导致越界。对一个正数加a模a，得到的值不变。对于rear=0的时候进行这个操作就会避免越界的情况。

做完这一题，我们再来看看与这题相关的选择题：

例题4：

标准答案：C

队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的

A错误：循环队列的长度都是固定的

B错误：队头和队尾在同一个位置时 队列可能是空的，也可能是满的，因此无法判断

C正确：设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空

D错误：循环队列也是队列的一种，是一种特殊的线性数据结构

例题5：

正确答案：B

有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。

总结

  更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

专栏订阅：
每日一题
c语言学习
算法
智力题
初阶数据结构
更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！