【数据结构】栈与队列经典选择题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】栈与队列经典选择题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

🚀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);
}