目录
前言
1. 题目：使用队列实现栈
2. 思路
3. 分析
3.1 创建栈
3.2入栈
3.3 出栈
3.4 栈顶数据
3.5 判空和 “ 栈 ” 的销毁
4. 题解
总结
前言
我们已经学习了栈和队列，也都实现了它们各自的底层接口，那么接下我们就要开始栈和队列的专项刷题训练。
1. 题目：使用队列实现栈
题目描述：
题目链接：
队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/
2. 思路
队列的结构是先进先出，题目的要求是，让我们利用队列的底层接口来实现栈，不可以改变队列的底层逻辑，所以如果你的思路是逆置队列这个链表，那这个思路就被pass掉了。
那我们要如何利用队列尾进头出的特性来实现栈的尾进尾出呢？题目中给了我们两个队列，我们要使用这两个队列实现栈。
入栈操作好说，问题在于出栈问题，思路是这样的：我们有两个队列，一个队列用于存储数据，另外一个队列（空队列）用于拷贝数据，将原队列的前n-1个数据拷贝到空队列中，然后再将原队列剩余的最后一个元素出队列，这样就模拟实现了栈的尾出。
3. 分析
根据上述的思路分析，队列实现栈，入栈不需要什么特殊操作例如我们入栈：1、2、3、4、5，出栈呢就是：5、4、3、2、1。
上述的思路已经介绍了解决办法，也是非常简单的，但有人可能会问：那这样算法的效率岂不是很低？这种方法的效率确实低，但是这道题目考察的并不是效率的问题，而实性质问题，这也是一道经典的面试题目。这道题目并不难，但它考察对数据结构的理解，各各接口的实现中有很多需要注意的细节。
首先这道题目是并没有给现成的队列，使用C语言解决需要我们现成造轮子，这也是C语言刷题的弊端，有很多题目都需要造轮子。那么这里我们就可以直接复制前边我们实现的队列。
接下来就是我们开始注意实现接口：
首先题目中给了我们两个队列，为了便于传参和使用，我们可以定义一个结构体：
typedef struct {
Que q1; //注意这里定于的队列类型一定要与自己定义的队列结构体类型对应
Que q2;
} MyStack;这里我们在前边介绍结构体时提到过，匿名结构体。
3.1 创建栈
MyStack* myStackCreate() {
}题目给出的接口如上，那这里我们要怎么创建我们的栈呢？是这样吗？
MyStack* myStackCreate() {
MyStack st;
//…
return &st;
}对函数和指针比较熟悉的同学可能就已经发现不行，为什么不行？这里就牵扯到了函数相关的知识，函数内创建的变量都是存储在栈区，出了函数就会被销毁，内存已经被销毁，返回指针还有什么意义呢？所以这里需要使用malloc函数，动态内存分配开辟的空间在堆区，程序结束前不主动释放就一直存在。所以上述的创建变量的方法不可取。
正确的方法：
MyStack* myStackCreate() {
MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}这里的pst->q1,就等价于我们在创建的队列的结构体变量：Que q；在调用接口时需要传地址过去。
3.2入栈
接下来就是入栈，题目中给了我们两个队列，为了后续出栈操作我们需要确保一个队列为空，用于拷贝数据，所以我们入栈时需要在不为空的队列入。
void myStackPush(MyStack* obj, int x) {
if(!IsEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}如果两个都为空那就随便选一个都可以。
3.3 出栈
在进行出栈操作的时候，我们需要判断哪一个队列为空，然后将非空队列的前n-1个元素依次拷贝到空队列当中。这里我们可以先假设队列1为空，然后在判断队列1是否为空，如果不为空那就是队列2为空，进行修改。这个假设的方法还是很实用的。
拷贝过程如下：
注意这里是拷贝，不是将原队列的节点插入到空队列，而是通过队头数据这个函数接口来将数据传过去，然后入队（调用入队接口），入队之后及时更新队头（出队）。
int myStackPop(MyStack* obj) {
Que* Empty=&obj->q1;
Que* NoEmpty=&obj->q2;
if(!IsEmpty(&obj->q1))
{
Empty=&obj->q2;
NoEmpty=&obj->q1;
}
while(QueueSize(NoEmpty)>1)
{
QueuePush(Empty,QueueFront(NoEmpty));
QueuePop(NoEmpty);
}
int top=QueueFront(NoEmpty);//最后保存非空队列最后一个队列节点的数据，便于返回
QueuePop(NoEmpty); //最后一个元素出队。
return top;
}3.4 栈顶数据
栈顶数据接口实现就简单了，我们前边对队列进行实现时，有队头和队尾数据的接口，我们可以直接调用。
int myStackTop(MyStack* obj) {
if(!IsEmpty(&obj->q1))
{
return QueueBlack(&obj->q1);
}
else
{
return QueueBlack(&obj->q2);
}
}
3.5 判空和 “ 栈 ” 的销毁
判空就很简单，如果两个队列都为空，那么这个 “ 栈 ” 也就为空。
bool myStackEmpty(MyStack* obj) {
return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2));
}
“ 栈 ”的销毁，这里就不能直接free掉obj了，如果直接释放那我们程序中的两个队列就会丢失无法释放，所以在释放掉obj之前，我们需要先将两个队列销毁。
void myStackFree(MyStack* obj) {
DestoryQueue(&obj->q1);
DestoryQueue(&obj->q2);
free(obj);
}4. 题解
完整代码如下：
typedef int Datatype;
typedef struct QueueNode
{
struct QueueNode* next;
Datatype data;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
int size;
}Que;
//初始化队列
void QueueInit(Que* pq);
//入队
void QueuePush(Que* pq, Datatype x);
//出队
void QueuePop(Que* pq);
//队头数据
Datatype QueueFront(Que* pq);
//队尾数据
Datatype QueueBlack(Que* pq);
//判空
bool IsEmpty(Que* pq);
//队列大小
int QueueSize(Que* pq);
//销毁队列
void DestoryQueue(Que* pq);
void QueueInit(Que* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueuePush(Que* pq, Datatype x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Que* pq)
{
assert(pq);
assert(!IsEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QueueNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
Datatype QueueFront(Que* pq)
{
assert(pq);
assert(!IsEmpty(pq));
return pq->head->data;
}
Datatype QueueBlack(Que* pq)
{
assert(pq);
assert(!IsEmpty(pq));
return pq->tail->data;
}
bool IsEmpty(Que* pq)
{
assert(pq);
return (pq->head == NULL);
}
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
void DestoryQueue(Que* pq)
{
assert(pq);
QueueNode* cur = pq->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
typedef struct {
Que q1;
Que q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x) {
if(!IsEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
Que* Empty=&obj->q1;
Que* NoEmpty=&obj->q2;
if(!IsEmpty(&obj->q1))
{
Empty=&obj->q2;
NoEmpty=&obj->q1;
}
while(QueueSize(NoEmpty)>1)
{
QueuePush(Empty,QueueFront(NoEmpty));
QueuePop(NoEmpty);
}
int top=QueueFront(NoEmpty);
QueuePop(NoEmpty);
return top;
}
int myStackTop(MyStack* obj) {
if(!IsEmpty(&obj->q1))
{
return QueueBlack(&obj->q1);
}
else
{
return QueueBlack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2));
}
void myStackFree(MyStack* obj) {
DestoryQueue(&obj->q1);
DestoryQueue(&obj->q2);
free(obj);
}文章来源：https://www.toymoban.com/news/detail-645575.html
总结
本文队列模拟实现栈，让我们在实践中深入思考了数据结构的本质和应用，为我们的编程能力和问题解决能力提供了锻炼。本期内容到此结束，感谢阅读！文章来源地址https://www.toymoban.com/news/detail-645575.html
到了这里，关于数据结构刷题训练：队列实现栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
