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

末蓝、 2024-04-27 15:59 59阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：  
> ?️博客主页：[睿睿的博客主页][Link 1]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言：
 *   *  例题1：
     *  例题2：
     *  例题3：
     *  例题4：
 *  例题5：
 *  总结

## 前言： ##

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

### 例题1： ###

![在这里插入图片描述][7619c1502b0441589674f607b0fa2952.png]  
**答案：C**  
在这里我们要先弄清楚**栈的实现方法**：

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

### 例题2： ###

![在这里插入图片描述][909d17827d464fd8bc69f33528a4ce49.png]  
**答案：A B**

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

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

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

D正确：栈和队列的特性

### 例题3： ###

既然栈两种线性表示都能实现，队列呢？队列的链表实现我们已经实现了，现在我们来看看用顺序表实现队列：  
[循环队列][Link 2]  
![在这里插入图片描述][5e0d23d7c837457d8acf5458e72556cd.png]  
因为队列长度有限，所以我们要及时的判断什么时候队列满了。那么怎么判断队列是否满了呢？  
如果我们通过队尾和队顶是否相等来判断是否填满就会发现，在队列空的时候，队尾也等于对队顶。所以我们不能通过这种方法来判断：  
![在这里插入图片描述][2049ed103dbc4abbb2388e27e2e8fd1a.png]  
![在这里插入图片描述][913812518cb24b899f489ec1895bf35b.png]  
那么我们该如何解决呢？  
**方法1：**

加一个size来计数

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

**空的情况：**  
![在这里插入图片描述][3e2d468c015f428cb5dc43bbf578ea02.png]  
**满的情况：**  
![在这里插入图片描述][44da4207a2cc4c898f265889b6b7b5f1.png]

下面我们就以方法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);
    }

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

**空的情况：**  
![在这里插入图片描述][08f34b9cd629422e9c1f2540d586106e.png]  
**满的情况：**  
![在这里插入图片描述][887bb7d447824e41a878add2758a9c34.png]  
  在这里我们学到了如何在数组里建立循环！那就是通过mod数组的长度，就可以使数组循环起来！

**找队尾：**  
![在这里插入图片描述][05460fae940a40eb8ae446185f49f12a.png]  
  尾部其实就是rear的后面一个元素，即**rear-1**，但是当**rear等于0**的时候，**-1就会导致越界**。对一个正数加a模a，得到的值不变。对于rear=0的时候进行这个操作就会避免越界的情况。

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

### 例题4： ###

![在这里插入图片描述][32c12f8e8a5c408794b06343835ddfc3.png]  
**标准答案：C**

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

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

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

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

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

## 例题5： ##

![在这里插入图片描述][331b627b3cc846f39f3961eacfa97897.png]  
**正确答案：B**

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

## 总结 ##

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

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

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/7df27ef0342b400da65f155162292929.gif
[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/0939e801a00b40089b4052cd8c9b4eb2.gif
[7619c1502b0441589674f607b0fa2952.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/41d31f26238e4a79a719cd212c2a92fa.png
[909d17827d464fd8bc69f33528a4ce49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/2909097b0bfc4d01aff63b0972d959a6.png
[Link 2]: https://leetcode.cn/problems/design-circular-queue/
[5e0d23d7c837457d8acf5458e72556cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ed6ebd42ed9546e381e09c5df8328681.png
[2049ed103dbc4abbb2388e27e2e8fd1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/560569341e6e413eb337d3a84aabe974.png
[913812518cb24b899f489ec1895bf35b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/aef82580deef4833933a5c11eb142581.png
[3e2d468c015f428cb5dc43bbf578ea02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/1e0b7e694e82450a8bace208444f9ac9.png
[44da4207a2cc4c898f265889b6b7b5f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/36cce3f97a1e4880b0ad3ddfd4ab4fe2.png
[08f34b9cd629422e9c1f2540d586106e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/6e83d45d1bae489786f8b2321c8d7c13.png
[887bb7d447824e41a878add2758a9c34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/88ea6467df5041eb8c32aae43164332e.png
[05460fae940a40eb8ae446185f49f12a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/3cc9fbef657c4d5db1e664ce93b2b7bc.png
[32c12f8e8a5c408794b06343835ddfc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/bce7f184223a4a4f80de04356d71a291.png
[331b627b3cc846f39f3961eacfa97897.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/29cadbabd0424839b8545599a8f71d8d.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[Link 6]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/f739ff00907b4c46814f2cbb876bc6c5.gif