前面我们实现了栈和队列，其实栈和队列之间是可以相互实现的
下面我们来看一下 用 队列实现栈 和 用栈实现队列
用队列实现栈
使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ,否则返回 false
如图是2个队列和1个栈
此时我们已经向栈中插入了5个元素，因为用队列去模拟，所以元素存放在栈中
因为用2个队列实现栈，所以我们创建一个MyStack的结构体，里面的元素是2个队列
typedef struct { Queue q1; Queue q2; } MyStack;
创建栈
因为函数会返回创建栈的地址，如果定义的这个栈为局部遍历，则出函数后这个值就会被销毁，所以我们需要将这个栈开辟到堆区
然后也调用队列中的初始化函数，队栈结构体中2个队列进行开辟和初始化
MyStack* myStackCreate() { MyStack* new = (MyStack*)malloc(sizeof(MyStack)); if(new==NULL) { perror("malloc fail"); return NULL; } QueueInit(&new->q1); QueueInit(&new->q2); return new; }
实现入栈
在非空的队列中插入元素，就相当于入栈了
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1,x); } else { QueuePush(&obj->q2,x); } }
实现出栈
假设我们现在要出栈，按照栈的特点，先出的应该是5，但是由于队列的特点，只能先进先出，所以我们可以把最后一个元素之前的所有元素都出队并放到为空的那个队列中，再将最后一个元素出队，就做到的出栈的操作
所以这里需要找到空的那个队列，将有元素的队列中前面元素都放到空队列中后，再将最后一个元素出队，这样还是一个空队列一个有元素队列
所以一直会有一个空队列和一个非空队列
根据这个思路我们实现一下代码
首先要判断出空队列和非空队列，如果直接使用if else语句就会是语句冗余
所以我们可以定义emptyQ和nonemptyQ指针表示空队列和非空队列，然后判断出q1和q2哪个才是空队列和非空队列，emptyQ指向空队列，nonemptyQ指向非空队列
Queue* emptyQ = &obj->q1; Queue* nonemptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { nonemptyQ = &obj->q1; emptyQ = &obj->q2; } 1
然后将非空队列中最后一个元素前的所有元素放入空数组中
while(QueueSize(nonemptyQ)>1) { QueuePush(emptyQ,QueueFront(nonemptyQ)); QueuePop(nonemptyQ); } 1
最后返回原非空队列中唯一的那个值，然后将它出队列
完整代码：
int myStackPop(MyStack* obj) { Queue* emptyQ = &obj->q1; Queue* nonemptyQ = &obj->q2; if(!QueueEmpty(&obj->q1)) { nonemptyQ = &obj->q1; emptyQ = &obj->q2; } while(QueueSize(nonemptyQ)>1) { QueuePush(emptyQ,QueueFront(nonemptyQ)); QueuePop(nonemptyQ); } int front = QueueFront(nonemptyQ); QueuePop(nonemptyQ); return front; }
判空
当两个队列都为空，那么模拟的栈也为空
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2); } 1
取栈顶元素
元素都存在非空队列中，先找到非空队列，然后调用队列的QueueBack取出队列中最后一个值
int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } }
其实这里可以体现出在实现队列时，设计QueueBack函数的原因
释放
void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); obj = NULL; } 1
2
