企业官网建设流程全解析

题目 描述：

思路分析：栈是先入后出，队列是先入先出，故需要用两个栈去实现队列

step1：将1，2，3，4随便入 栈中

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.入队：直接入在stackpush

void 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; }