题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例1
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
思路分析：
此题思路和用队列实现栈思路类似
用栈（先进后出）实现队列（先进先出），我们可以用两个栈来实现，一个栈(Stack PushSt)用来实现队列的入数据，当需要实现出队列时，只需将Stack PushSt中的所有数据导入另一个空栈(Stack PopSt)中，然后直接出栈就可实现队列先进先出
图解如下：
代码实现
typedef int STDataType;
typedef struct Stack
{
STDataType* a;//动态数组
int top; //栈顶
int capacity; //容量
}Stack;
//初始化栈
void StackInit(Stack* pst);
//销毁栈
void StackDestroy(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType data);
//出栈
void StackPop(Stack* pst);
//获取栈中有效元素的个数
int StackSize(Stack* pst);
//获取栈顶元素
STDataType StackTop(Stack* pst);
//检测栈是否为空，为空返回1，非空返回0
int StackEmpty(Stack* pst);
//初始化栈
void StackInit(Stack* pst)
{
assert(pst);
pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);
if (pst->a == NULL)
{
printf("malloc fail");
}
pst->top = 0;
pst->capacity = 4;
}
//销毁栈
void StackDestroy(Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType data)
{
assert(pst);
//空间不够需要增容
if (pst->top == pst->capacity)
{
//增容为原来的2倍
int* tem = (STDataType*)realloc(pst->a, sizeof(STDataType)* pst->capacity * 2);
if (tem == NULL)
{
printf("realloc fail");
exit(-1);
}
pst->a = tem;
pst->capacity = pst->capacity * 2;
}
pst->a[pst->top] = data;
pst->top++;
}
//出栈
void StackPop(Stack* pst)
{
assert(pst);
//判断栈是否为空
//相当于assert(pst->top != 0);
assert(!StackEmpty(pst));
pst->top--;
}
//获取栈中有效元素的个数
int StackSize(Stack* pst)
{
assert(pst);
//因为初始化top是0,如果初始化top是-1则返回top+1;
return pst->top;
}
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
assert(pst);
assert(!StackEmpty(pst));
return pst->a[pst->top - 1];
}
//检测栈是否为空，为空返回1，非空返回0
int StackEmpty(Stack* pst)
{
assert(pst);
return pst->top == 0 ? 1 : 0;
}
typedef struct {
Stack PushSt;
Stack PopSt;
} MyQueue;
/** Initialize your data structure here. */
MyQueue* myQueueCreate() {
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&pst->PushSt);
StackInit(&pst->PopSt);
return pst;
}
/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushSt,x);
}
/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
//若PopSt为空则把PushSt中的数据全部导入
if(StackEmpty(&obj->PopSt))
{
while(!StackEmpty(&obj->PushSt))
{
StackPush(&obj->PopSt,StackTop(&obj->PushSt));
StackPop(&obj->PushSt);
}
}
//保存队头数据，返回
int Top = StackTop(&obj->PopSt);
StackPop(&obj->PopSt);
return Top;
}
/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
//若PopSt为空则把PushSt中的数据全部导入
if(StackEmpty(&obj->PopSt))
{
while(!StackEmpty(&obj->PushSt))
{
StackPush(&obj->PopSt,StackTop(&obj->PushSt));
StackPop(&obj->PushSt);
}
}
return StackTop(&obj->PopSt);
}
/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PushSt) && StackEmpty(&obj->PopSt);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PushSt);
StackDestroy(&obj->PopSt);
free(obj);
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/