当前位置：首页 > news >正文

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

news 2025/7/27 20:37:15

在这里插入图片描述

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

在这里插入图片描述

文章目录

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

前言：

在前面的学习中外面学习了栈与队列。但是似乎对于栈与队列的理解却很潜，今天通过这些选择题和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);
}