题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
题目链接
LeetCode232. 用栈实现队列
思路分析
题目的意思是要用两个栈来模拟实现一个队列。仅可以用栈的基本功能实现队列的基本功能。所以需要创建两个栈。所以这两个栈st1，st2可用一个结构体包含。
本质就是用两个后进先出的栈，来模拟一个先进先出的队列。
思路：
1.st2这个栈用来压栈，st1的作用：把st2的所有值压到st1中，然后经过st1出栈。这样就达到了队列先进先出的性质。
2.st2一直用来压栈。如果st1为空则将st2里面的值全都转移到st1，如果st1不为空，则继续出栈，知道st1为空为止。
代码实现
ypedef char STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST; //初始化结构体 void StackInit(ST* ps); //销毁结构体 void StackDestroy(ST* ps); //压栈 void StackPush(ST* ps, STDataType x); //出栈 void StackPop(ST* ps); //得到栈顶的值 STDataType StackTop(ST* ps); //判断栈是否为空 bool StackEmpty(ST* ps); //得到栈的长度 int StackSize(ST* ps); //初始化结构体 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } //销毁结构体 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; } //压栈 void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity); if (new == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = new; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); ps->top--; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top>0); return ps->a[ps->top-1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //得到栈的长度 int StackSize(ST* ps) { assert(ps); return ps->top; } //创建了两个栈 typedef struct { ST st1; ST st2; } MyQueue; //对两个栈进行初始化。 MyQueue* myQueueCreate() { MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue)); assert(newQueue); StackInit(&newQueue->st1); StackInit(&newQueue->st2); return newQueue; } void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->st2, x); } int myQueuePop(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->st1)) { while(!StackEmpty(&obj->st2)) { StackPush(&obj->st1, StackTop(&obj->st2)); StackPop(&obj->st2); } } int top = 0; if(!StackEmpty(&obj->st1)) { top = StackTop(&obj->st1); StackPop(&obj->st1); } return top; } int myQueuePeek(MyQueue* obj) { assert(obj); if(StackEmpty(&obj->st1)) { while(!StackEmpty(&obj->st2)) { StackPush(&obj->st1, StackTop(&obj->st2)); StackPop(&obj->st2); } } if(!StackEmpty(&obj->st1)) { return StackTop(&obj->st1); } return 0; } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->st1) && StackEmpty(&obj->st2); } void myQueueFree(MyQueue* obj) { StackDestroy(&obj->st1); StackDestroy(&obj->st2); free(obj); }
