3.队列实现栈
使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
首先思考队列的栈对于数据进出所遵循的原则，队列是先进先出而栈是先进后出。
既然这两种线性表所遵循的原则不相同，又该用什么方式去实现呢？
两个队列是关键点，接下来就思考两个队列如何去实现队列。
假设只有一个队列中有数据，另一个队列为空。
此时队列 q2 删除数据的话，只能从队头删除，这样就不符合栈先进后出的原则。
如果将队列 q2 只留下队尾的数据，其余的全部转移到队列 q1 中，这时删除 q2 中数据就符合后进先出的原则。
同样的道理如果再次删除数据，就将队列 q1 中除队尾以外的数据转移到队列 q2 中，再进行删除操作。
由此便得到思路：保持一个队列为空，删除数据时，将另一个不为空的队列的数据除队尾以外全部转移到空队列中。
定义两个队列
typedef struct { QE q1; QE q2; } MyStack;
两个队列实现栈，并进行初始化
MyStack* myStackCreate() { MyStack*obj=(MyStack*)malloc(sizeof(MyStack)); QEinit(&obj->q1); QEinit(&obj->q2); return obj; }
数据入栈
void myStackPush(MyStack* obj, int x) { if(!(QEempty(&obj->q1))) { QEpush(&obj->q1,x); } else { QEpush(&obj->q2,x); } }
这里假设队列 q2 不为空
数据出栈
先判断队列 q1,q2 哪个为空，哪个不为空
假设队列 q2 不为空，将其 N-1 个数据转移到 队列 q1 中，接着将最后一个数据出栈
int myStackPop(MyStack* obj) { QE*empty=&obj->q1; QE*nonempty=&obj->q2; if(!QEempty(&obj->q1)) { empty=&obj->q2; nonempty=&obj->q1; } //将队列中的N-1个数据，转移到空队列中 while(QEsize(nonempty)>1) { QEpush(empty,QEfront(nonempty)); QEpop(nonempty); } //取出栈顶数据（也就是不为空队列的最后一个数据） int top = QEfront(nonempty); //删除不为空队列最后一个数据 QEpop(nonempty); //返回栈顶数据 return top; }
读取栈顶数据
先判断哪个队列不为空，读取不为空队列的队尾数据，即栈顶数据
int myStackTop(MyStack* obj) { if(!QEempty(&obj->q1)) { return QEback(&obj->q1); } else { return QEback(&obj->q2); } }
判断栈是否为空
必须队列 q1 ,q2 都为空，才能说明栈也为空
bool myStackEmpty(MyStack* obj) { assert(obj); return QEempty(&obj->q1)&&QEempty(&obj->q2); }
销毁栈
销毁栈，不可以直接释放栈开辟的空间，会造成内存泄漏
因为队列q1 q2 中也有开辟的空间，直接释放栈开辟的空间，会导致再也找不到队列开辟的空间，从而造成内存泄漏
所有先将队列销毁，最后再释放栈开辟的空间
void myStackFree(MyStack* obj) { QEdestory(&obj->q1); QEdestory(&obj->q2); free(obj); }
4.栈实现队列
既然队列可以实现栈，那么栈是否可以实现队列呢？
答案是：当然可以
与上面类似，都是需要两个，也就是通过两个队列去实现栈
由于栈所遵守的原则是先进后出，所以不需要将其中一个栈一直保存空的状态
接下来开始慢慢分析
两个栈 其中 pushSK 是插入数据的栈，popSK 是删除数据的栈
如果此时删除数据，按照队列的原则需要将第一个插入的数据进行删除操作，也就是删除位于栈底的 1 。很简单只需要将 pushSK 中的所有数据全部转移到 popSK 中即可。然后在 popSK 中删除栈顶数据 1，就完成队列的数据删除
如果继续删除数据，便可直接在 popSK 中删除，直到栈 popSK 为空，再将栈 pushSK 中的数据全部转移到其中。
由此可得出思考：
插入数据到pushSK 中，然后将pushSK 中的数剧全部转移到 popSK 中，当 popSK为空，再重复此操作。
由于栈的特点，转移的数据再 popSK 中全部都是倒置的，因此符合队列的特点。
定义两个栈 pushSK,popSK
typedef struct { SK pushSK;//数据压入栈 SK popSK;//数据压出栈 } MyQueue;
初始化两个栈
MyQueue* myQueueCreate() { MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue)); SKinit(&obj->pushSK); SKinit(&obj->popSK); return obj; }
数据插入队列
void myQueuePush(MyQueue* obj, int x) { SKpush(&obj->pushSK,x); }
数据出队列
在删除队头的数据时，需要判断 栈 popSK 是否为空。如果为空，则不能完成删除操作。
为了方便起见，将判断这一过程独立为函数，在之后还能用到
void pushSKtopopSK(MyQueue*obj) { if(SKempty(&obj->popSK)) { while(!SKempty(&obj->pushSK)) { SKpush(&obj->popSK,SKtop(&obj->pushSK)); SKpop(&obj->pushSK); } } }
int myQueuePop(MyQueue* obj) { if(SKempty(&obj->popSK)) { pushSKtopopSK(obj); } int top=SKtop(&obj->popSK); SKpop(&obj->popSK); return top; }
读取队头数据
int myQueuePeek(MyQueue* obj) { if(SKempty(&obj->popSK)) { pushSKtopopSK(obj); } return SKtop(&obj->popSK); }
判断队列是否为空
栈 pushSK和 栈 popSK 必须都为空，队列才表示为空
bool myQueueEmpty(MyQueue* obj) { return SKempty(&obj->pushSK)&&SKempty(&obj->popSK); }
销毁队列
与上面类似，不能直接释放队列所开辟的空间，否则同样会造成内存泄漏
void myQueueFree(MyQueue* obj) { SKdestory(&obj->pushSK); SKdestory(&obj->popSK); free(obj); }
