用栈实现队列
点击链接答题
思路：
定义两个栈：
pushST（入数据）和popST（出数据）假设我们要在队列里放
123，出队列123我们先在
pushST里面放进去1 2 3然后把
pushST里面的数据拿到popST里面，依次是3 2 1然后把
1提取出来，把2提取出来，把3提取出来.
如果我们先在
pushST里面放进去1 2 3然后把
pushST里面的数据拿到popST里面，依次是3 2 1然后在
pushST里面放进去4然后把
popST里面的1提取出来，把2提取出来，把3提取出来.然后把
pushST里面的数据4拿到popST里面然后把
4提取出来
入队：往
pushST中插入数据出队：判断
popST是否为空，不为空直接pop，为空的话将pushST导入到popST中再pop取队头：跟出队一样，但这里只取数据，不
pop数据
代码：
//定义栈的结构
typedef char STDataType;
typedef struct Stack {STDataType* arr;int capacity;//栈的空间大小int top;//栈顶
}ST;//栈的初始化
void STInit(ST* ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//栈的销毁
void STDestory(ST* ps) {assert(ps);if (ps->arr) {free(ps->arr);}ps->arr = NULL;ps->top = ps->capacity = 0;
}//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x) {assert(ps);//1.判断空间是否足够if (ps->capacity == ps->top) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("relloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//判断栈是否为空
bool StackEmpty(ST* ps) {assert(ps);return ps->top == 0;
}//出数据
void StackPop(ST* ps) {assert(ps);assert(!StackEmpty(ps));//栈为空报错--ps->top;
}//获取栈中有效元素个数
int STSize(ST* ps){assert(ps);return ps->top;
}//取栈顶元素
STDataType StackTop(ST* ps) {assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//
typedef struct {ST pushST;ST popST;
} MyQueue;//队列的初始化
MyQueue* myQueueCreate() {MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pst->pushST);STInit(&pst->popST);return pst;
}//往pushST中插入数据
void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST,x);
}//删除数据
//1.检查popST是否为空，不为空直接出，为空pushST导入到popST，再出数据
int myQueuePop(MyQueue* obj) {if(StackEmpty(&obj->popST)){//如果popST为空//导数据while(!StackEmpty(&obj->pushST)){//如果pushST非空StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进popSTStackPop(&obj->pushST);}}//取栈顶，删除栈顶元素并返回栈顶数据int top = StackTop(&obj->popST);//储存删除的栈顶元素StackPop(&obj->popST);return top;//返回删除的栈顶元素
}//取队头元素
int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->popST)){//如果popST为空//导数据while(!StackEmpty(&obj->pushST)){//如果pushST非空StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进pushSTStackPop(&obj->pushST);}}//取栈顶，删除栈顶元素并返回栈顶数据return StackTop(&obj->popST);//返回删除的栈顶元素}//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}//队列的销毁
//就是两个栈的销毁
void myQueueFree(MyQueue* obj) {STDestory(&obj->pushST);STDestory(&obj->popST);free(obj);obj = NULL;
}/*** 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);
*/
