用队列实现栈
前置学习:栈和队列分别的基本实现
可以参考:https://blog.csdn.net/xpcxpt/article/details/148481903?spm=1001.2014.3001.5501
https://blog.csdn.net/xpcxpt/article/details/148500318?spm=1001.2014.3001.5501
目录：
1.用队列实现栈
2.取栈顶元素
3.判断栈是否为空
4.销毁栈
5.代码
1.用队列实现栈
首先要调用队列的一系列前置函数
栈是后进先出，但是队列是先进先出，实现方法如下:
创建两个队列，分别为队列1和队列2，初始情况下，数据都在队列1中。
将数据从队列1移到队列2，剩下一个数据，那就是栈顶的数据。
重复以上行为，最终用队列实现栈。
下面开始详细实现:
首先创建两个队列:
接下来对两个队列进行初始化:
进行判空操作，如果队列1为空，那就往队列1里面插入数据，不然就往队列2里面插入数据:
按照思路，我们需要在两个队列间交换数据，但是我们不知道那个为空，所以使用假设法，假设队列1为空，如果不成立，那么队列2就为空:
这个时候其中一个队列是空的，另一个是非空的，我们将非空的队列的数据移到空的队列，只留一个，那个就是我们需要的栈顶的元素，至此，成功用队列实现栈:
2.取栈顶元素
这个很简单，找到非空队列，然后返回元素:
3.判断栈是否为空
只有两个队列都为空，才是空:
4.销毁栈
销毁不能直接销毁总体，要分别销毁:
5.代码
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//销毁
void QueuePush(Queue* pq, QDataType x);//队列的插入
void QueuePop(Queue* pq);//队列的删除int QueueSize(Queue* pq);//统计队列的数据个数QDataType QueueFront(Queue* pq);//返回队列表头数据
QDataType QueueBack(Queue* pq);//返回队列表尾数据
bool QueueEmpty(Queue* pq);//判断队列是否为空void QueueInit(Queue* pq)
{assert(pq);//判断是否为空pq->phead = NULL;//初始化指向NULLpq->ptail = NULL;//初始化指向NULLpq->size = 0;//初始的时候，值为0
}
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点if (newnode == NULL)//判断是否创建成功{perror("malloc fail");return;}newnode->next = NULL;//新节点的next指针为NULLnewnode->val = x;//它的值为给的xif (pq->ptail == NULL)//判断是否为初始情况{pq->phead = pq->ptail = newnode;}else//不是初始情况，链表中已经有节点{pq->ptail->next = newnode;//直接尾插pq->ptail = newnode;//成为新的尾}pq->size++;//个数加一
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);if (pq->phead->next==NULL)//是否链表中只有一个节点{free(pq->phead);pq->phead = pq->ptail = NULL;//都为NULL}else//链表中不止一个节点{QNode* tmp = pq->phead->next;//临时变量存放新的头结点free(pq->phead);pq->phead = tmp;}pq->size--;//删除节点，size要减少1
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);//判断是否为空QNode* cur = pq->phead;//创建一个额外指针指向头结点while (cur)//遍历链表{QNode* next = cur->next;//临时变量存放新的头结点free(cur);//原本头结点要被销毁掉cur = next;}pq->phead = pq->ptail = NULL;//全部节点销毁完，都置于空，防止成为野指针pq->size = 0;//size也变成0
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));//malloc开辟空间QueueInit(&(pst->q1));//对q1初始化QueueInit(&(pst->q2));//对q2初始化return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&(obj ->q1)))//队列1为空，就往队列1里面插入{QueuePush(&(obj->q1),x);}else//队列1不为空，就往队列2里面插入{QueuePush(&(obj->q2),x);}
}int myStackPop(MyStack* obj) {//假设法Queue* empty=&(obj->q1);//假设队列1是空的Queue* nonEmpty=&(obj->q2);//那么队列2就不是空的if(!QueueEmpty(&(obj->q1))){//判空函数判断，如果判空函数返回fasle，代表队列1不为空，这个时候！反转意思，所以if的括号内返回ture，执行运算//需要交换nonEmpty=&(obj->q1);//队列1非空empty=&(obj->q2);//队列2为空}//不为空的队列的前size-1个数据导入另一个队列，随后最后一个就是栈顶数据while(QueueSize(nonEmpty)>1)//非空队列留一个元素，就是栈顶的数据{QueuePush(empty,QueueFront(nonEmpty));//将非空数据插入空队列QueuePop(nonEmpty);}//这个时候还剩一个数据，他就是栈顶数据，将他返回，然后删除int top= QueueFront(nonEmpty);//top接受栈顶数据QueuePop(nonEmpty);//把他删除return top;//返回栈顶数据
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&(obj->q1))){//判空函数判断，如果判空函数返回fasle，代表队列1不为空，这个时候！反转意思，所以if的括号内返回ture，执行运算//这个时候队列1非空，取栈顶元素return QueueBack(&(obj->q1));}else{//这个时候队列2非空，取栈顶元素return QueueBack(&(obj->q2));}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));//两个都为空才是空
}void myStackFree(MyStack* obj) {QueueDestroy(&(obj->q1));QueueDestroy(&(obj->q2));free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/