力扣T232：用栈来实现队列

题目 描述思路分析栈是先入后出队列是先入先出故需要用两个栈去实现队列step1将1234随便入 栈中step2出队时先出去的是1按顺序将非空栈的元素入栈到空栈再在stack2中出栈如果再次执行出队操作就让stack2再出栈step3再入队5不可以直接再次入队到stack2中不然5就会变为队头所以入队在stack1中若要取队头元素取stack2即可综上所述只要入队都在stack1中出队都在stack2中故可定义一个栈stackpush用于入队stackpop用于出队代码实现拿过来实现栈的函数void StackInit(ST* ps, SLDataType x) { ps-arr NULL; ps-top ps-capacity 0; } void StackPush(ST* ps, SLDataType x) { assert(ps); if (ps-top ps-capacity) { int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity; SLDataType* tmp (SLDataType*)realloc(ps-arr, newcapacity * sizeof(SLDataType)); if (tmp NULL) { perror(realloc fail!); exit(1); } ps-arr tmp; ps-capacity newcapacity; }//判断当前的栈是否满容量或者无容量 ps-arr[ps-top] x; } bool STEmpty(ST* ps) { assert(ps); return ps-top 0; } //如果为空那么返回ture //如果不为空那么返回false void StackPop(ST* ps) { assert(!STEmpty(ps)); --ps-top; } SLDataType StackTop(ST* ps) { assert(!STEmpty(ps)); return ps-arr[ps-top - 1]; } void StackDestroy(ST* ps) { if (ps-arr) { free(ps-arr); ps-arr NULL; } ps-top ps-capacity 0; }1.定义结构体typedef int SLDataType; typedef struct Stack { SLDataType* arr; int top; int capacity; }ST; typedef struct MyQueue { ST stackpush; ST stackpop; }MyQueue;2.初始化创建一个结构体把该结构体指针返回用malloc创建一个MyQueue大小的内存空间而后用两个栈直接调用初始化函数MyQueue* myqueueCreat() { MyQueue* pst (MyQueue*)malloc(sizeof(MyQueue)); if (pst NULL) { perror(fail); exit(-1); } StackInit(pst-stackpush,0); StackInit(pst-stackpop, 0); return pst; }3.入队直接入在stackpushvoid myQueuePush(MyQueue* obj, SLDataType x) { StackPush(obj-stackpush, x); }4.出队先要判断stackpop是否为空栈如果为空栈则需要将stackpush中的元素全部挪到stackpush中再进行出队SLDataType myQueuePop(MyQueue* obj) { if (STEmpty(obj-stackpop) ){ while (StackSize(obj-stackpush) 0) { StackPush(obj-stackpop, StackTop(obj-stackpush)); StackPop(obj-stackpush); } }先取出stackpush栈顶元素入在stackpop中删除stackpush的栈顶元素直到stackpush的有效元素变为0挪移元素的过程结束出队操作用top接收stackpop的栈顶元素因为要返回删除值之后直接出栈即可SLDataType top StackTop(obj-stackpop); StackPop(obj-stackpop); return top;完整代码实现SLDataType myQueuePop(MyQueue* obj) { if (STEmpty(obj-stackpop) ){ while (StackSize(obj-stackpush) 0) { StackPush(obj-stackpop, StackTop(obj-stackpush)); StackPop(obj-stackpush); } } SLDataType top StackTop(obj-stackpop); StackPop(obj-stackpop); return top; }5.取队头元素把stackpop的栈顶元素返回即可若stackpop为空栈仍要挪移元素SLDataType myQueuePeek(MyQueue* obj) { if (STEmpty(obj-stackpop)) { while (StackSize(obj-stackpop)0) { StackPush(obj-stackpop, StackTop(obj-stackpush)); StackPop(obj-stackpop); } } return StackTop(obj-stackpop); }6.判空两个栈都为空即为空队bool myQueueEmpty(MyQueue* obj) { return STEmpty(obj-stackpush) STEmpty(obj-stackpop); }7.销毁将两个栈都销毁而后释放指针obj指向的空间再置为NULL即可void myQueueFree(MyQueue* obj) { StackDestroy(obj-stackpush); StackDestroy(obj-stackpop); free(obj); obj NULL; }