用栈实现队列
使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
实现 MyQueue类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
我们先将一些数据入到一个栈中
如果我们想实现出队，首先出队的数据应该是1，但是根据栈的特点，1是最后一个出
所以需要将栈中非栈底元素全都入栈到另一个栈中，根据栈的特点，这些元素到另一个栈中后，元素的顺序对于队列来说就是“正的了”
所以对于这个栈，它的出栈顺序和要模拟的队列出队顺序是一样的
如果想入栈,如果入到之前“顺序正常”的栈中，则会改变最后出队的顺序
所以从上面的分析可以看出，2个栈可以单独负责一项任务，一个栈负责入队，一个负责出队
在定义MyQueue时，直接定义一个叫PushStack和一个叫PopStack的栈
typedef struct { ST PushStack; ST PopStack; } MyQueue;
只要是入队，就往PushStack中入
当出队时，如果PopStack为空，就需要把PushStack中的数据先出栈，在入栈到PopStack中，然后出PopStack的栈顶元素
如果PopStack不为空，出队其实就是直接从PopStack中出栈，出PopStack的栈顶元素
所以可以看出，最终都是出PopStack的栈顶元素，只是如果PopStack为空，就需要将元素放到PopStack中，在实现时判断PopStack是否为空
所以下面我们来实现一下：
创建队列
MyQueue* myQueueCreate() { MyQueue*new = (MyQueue*)malloc(sizeof(MyQueue)); if(new ==NULL) { perror("malloc fail"); return NULL; } STInit(&new->PushStack); STInit(&new->PopStack); return new; }
1
根据前面的分析，入队就是将元素入栈到PushStack
中
void myQueuePush(MyQueue* obj, int x) { STPush(&obj->PushStack,x); }
出队
如果PopStack为空，就需要把PushStack中的元素都放到PopStack中
if(STEmpy(&obj->PopStack)) { while(obj->PushStack.top>0) { STPush(&obj->PopStack,STTop(&obj->PushStack)); STPop(&obj->PushStack); } }
如果PopStack为不为空，就直接出栈顶元素
int top = STTop(&obj->PopStack); STPop(&obj->PopStack); return top; 1 2
3
完整代码：
int myQueuePop(MyQueue* obj) { if(STEmpy(&obj->PopStack)) { while(obj->PushStack.top>0) { STPush(&obj->PopStack,STTop(&obj->PushStack)); STPop(&obj->PushStack); } } int top = STTop(&obj->PopStack); STPop(&obj->PopStack); return top; }
1
返回队列开头的元素
其实返回队列开头的元素的操作与上面出队列操作类似
当PopStack为空时，就将PushStack中的元素出栈，再依次入栈到PopStack中
当PopStack不为空时，就直接返回栈顶元素
可以看出，这个操作与出队列的操作唯一有差距的一点就是，不用pop掉PopStack中的栈顶元素
int myQueuePeek(MyQueue* obj) { if(STEmpy(&obj->PopStack)) { while(obj->PushStack.top>0) { STPush(&obj->PopStack,STTop(&obj->PushStack)); STPop(&obj->PushStack); } } int top = STTop(&obj->PopStack); return top; }
判空
如果当PushStack和PopStack都为空的话，模拟出的队列才为空
bool myQueueEmpty(MyQueue* obj) { return STEmpy(&obj->PushStack)&&STEmpy(&obj->PopStack); }
释放
调用STDestroy函数，销毁模拟队列的2个栈，然后再free掉队列
void myQueueFree(MyQueue* obj) { STDestroy(&obj->PushStack); STDestroy(&obj->PopStack); free(obj); obj = NULL; }
