企业官网建设流程全解析

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

解题思路：

入栈：第一次两个栈都为NULL，直接任意在一个队列插入即可，此后入栈的时候直接在非空的栈入栈
出栈：假设有n个数将前n-1个数给进去空的队列，再将最后一个数给进行返回
取栈顶：由于是实现栈，所以无法取栈的尾值，所以需要重复出栈的步骤，然后取出最后的值，并存放在变量中，且出队列，再将变量中的值给入栈到非空的队列中

typedefintDataType;typedefstructQueue{DataType val;structQueue*next;}Queue;typedefstructLinkQueue{Queue*top;Queue*tail;intsize;}LinkQueue;voidQueueInit(LinkQueue*p){assert(p);p->top=NULL;p->tail=NULL;p->size=0;}//销毁队列voidQueueDestroy(LinkQueue*p){assert(p);Queue*cur=p->top;while(cur){Queue*next=cur->next;free(cur);cur=next;}p->size=0;p->tail=NULL;p->top=NULL;}//判断是否为NULLboolQueueEmpty(LinkQueue*p){assert(p);returnp->size==0?true:false;}//获取有效的个数intQueueSize(LinkQueue*p){assert(p);returnp->size;}//获取队头的元素DataTypeGetFrom(LinkQueue*p){assert(p);assert(!QueueEmpty(p));returnp->top->val;}//入队voidQueueback(LinkQueue*p,DataType x){assert(p);Queue*newnode=(Queue*)malloc(sizeof(Queue));if(newnode==NULL){perror("newnode");exit(-1);}newnode->next=NULL;newnode->val=x;if(QueueEmpty(p)){p->tail=p->top=newnode;}else{p->tail->next=newnode;p->tail=newnode;}p->size++;}//出队DataTypeDeQueue(LinkQueue*p){assert(p);assert(!QueueEmpty(p));DataType x=p->top->val;Queue*cur=p->top->next;free(p->top);p->top=cur;p->size--;returnx;}//用队列来实现栈-----------------------------------------------------------------------typedefstruct{LinkQueue q1;LinkQueue q2;}MyStack;MyStack*myStackCreate(){MyStack*ps=(MyStack*)malloc(sizeof(MyStack));QueueInit(&ps->q1);QueueInit(&ps->q2);returnps;}voidmyStackPush(MyStack*obj,intx){if(!QueueEmpty(&obj->q1)){Queueback(&obj->q1,x);}else{Queueback(&obj->q2,x);}}intmyStackPop(MyStack*obj)//无法直接取队的尾{if(!QueueEmpty(&obj->q1)){while(QueueSize(&obj->q1)>1){inttop=DeQueue(&obj->q1);Queueback(&obj->q2,top);}returnDeQueue(&obj->q1);}else{while(QueueSize(&obj->q2)>1){inttop=DeQueue(&obj->q2);Queueback(&obj->q1,top);}returnDeQueue(&obj->q2);}}intmyStackTop(MyStack*obj){if(!QueueEmpty(&obj->q1)){while(QueueSize(&obj->q1)>1){inttop=DeQueue(&obj->q1);Queueback(&obj->q2,top);}intx=DeQueue(&obj->q1);Queueback(&obj->q2,x);returnx;}else{while(QueueSize(&obj->q2)>1){inttop=DeQueue(&obj->q2);Queueback(&obj->q1,top);}intx=DeQueue(&obj->q2);Queueback(&obj->q1,x);returnx;}}boolmyStackEmpty(MyStack*obj){returnQueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}voidmyStackFree(MyStack*obj){QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);}

第二问：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
入栈：两个栈，任意入。
出栈：由于要出栈底，所以要先把栈底的所有数据给放到另一个栈中，然后依次出栈。
不妨创建两个栈一个负责入栈，另一个负责出栈


只要出栈就判断SPop是否为NULL,为NULL就先从Spush导入数据，再出栈
第二种就是不为NULL的情况，直接到出数据，不会影响入栈

typedefintDataType;typedefstructStack{DataType*arr;inttop;intcapacity;}SqStack;//初始化voidStackInit(SqStack*p){assert(p);p->arr=(DataType*)malloc(4*sizeof(DataType));if(p->arr==NULL){perror("p->arr");exit(-1);}p->top=0;p->capacity=4;}//入栈voidStackpush(SqStack*p,DataType x){assert(p);if(p->top==p->capacity){DataType*tmp=(DataType*)realloc(p->arr,2*p->capacity*sizeof(DataType));if(tmp==NULL){perror("tmp");exit(-1);}p->arr=tmp;p->capacity*=2;}p->arr[p->top]=x;p->top++;}//判空boolEmpStack(SqStack*p){assert(p);returnp->top==0?true:false;}//出栈DataTypeStackPop(SqStack*p){assert(p);assert(!EmpStack(p));DataType x=p->arr[p->top-1];p->top--;returnx;}//取栈顶DataTypeStackTop(SqStack*p){assert(p);assert(!EmpStack(p));returnp->arr[p->top-1];}//返回有效个数intStackSize(SqStack*p){assert(p);returnp->top;}//销毁voidStackDestory(SqStack*p){assert(p);free(p->arr);p->arr=NULL;p->top=0;p->capacity=0;}typedefstruct{SqStack Spush;SqStack SPop;}MyQueue;MyQueue*myQueueCreate(){MyQueue*ps=(MyQueue*)malloc(sizeof(MyQueue));StackInit(&ps->Spush);StackInit(&ps->SPop);returnps;}voidmyQueuePush(MyQueue*obj,intx){Stackpush(&obj->Spush,x);}intmyQueuePop(MyQueue*obj){if(EmpStack(&obj->SPop)){inttmp=StackSize(&obj->Spush);while(tmp--){intx=StackPop(&obj->Spush);Stackpush(&obj->SPop,x);}}returnStackPop(&obj->SPop);}intmyQueuePeek(MyQueue*obj){if(EmpStack(&obj->SPop)){inttmp=StackSize(&obj->Spush);while(tmp--){intx=StackPop(&obj->Spush);Stackpush(&obj->SPop,x);}}returnStackTop(&obj->SPop);}boolmyQueueEmpty(MyQueue*obj){returnEmpStack(&obj->Spush)&&EmpStack(&obj->SPop);}voidmyQueueFree(MyQueue*obj){StackDestory(&obj->Spush);StackDestory(&obj->SPop);free(obj);obj=NULL;}