用队列实现栈
1 .思路及目的
用两个标准的队列（先进先出）实现栈（后进先出）
始终保持一个队列为空，往非空的栈插入数据
删除数据时，将数据导入另一个队列，留下最后一个数据（这个数据就是要删除的数据）
并实现多个接口：
push(插入数据)
top(返回栈顶元素)
pop(删除数据)
empty(判空)
栈结构图示 ：q1和q2为队列，obj是构成的栈
栈基本接口：
typedef int QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
1.1 栈初始化
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&(pst->q1));
QueueInit(&(pst->q2));
return pst;
}
1.2 插入数据
使用两个栈实现队列，往非空的栈插入数据，若两个栈都为空，往任意一个栈插入数据即可
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&(obj->q1)))
{
QueuePush(&(obj->q1), x);
}
else
{
QueuePush(&(obj->q2), x);
}
}
1.3 删除数据
删除数据时，需要将队列内的数据导入另一个队列，留下最后一个数据，这个数据就是要删除的数据
图解：
int myStackPop(MyStack* obj) {
Queue* empty = &(obj->q1);
Queue* nonEmpty = &(obj->q2);
if(!QueueEmpty(&(obj->q1)))
{
nonEmpty = &(obj->q1);
empty = &(obj->q2);
}
while(QueueSize(nonEmpty) > 1)
{
QueuePush(empty, QueueFront(nonEmpty));
QueuePop(nonEmpty);
}
int top = QueueFront(nonEmpty);
QueuePop(nonEmpty);
return top;
}
1.4 获取栈顶元素
即获取非空队列的尾部元素
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&(obj->q1)))
{
return QueueBack(&(obj->q1));
}
else{
return QueueBack(&(obj->q2));
}
}
1.5 栈的判空
两个队列都为空，栈才为空
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}
1.6 栈的销毁
分别销毁两个队列，最后再销毁栈
void myStackFree(MyStack* obj) {
QueueDestroy(&(obj->q1));
QueueDestroy(&(obj->q2));
free(obj);
}
2 . 总结
利用两个队列实现栈的关键，在于数据的删除、插入时如何处理