每日两道算法Day5—用队列实现栈，用栈实现队列

请你仅使用两个队列实现一个后入先出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(); // 返回 2myStack.pop(); // 返回 2myStack.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-topNULL;p-tailNULL;p-size0;}//销毁队列voidQueueDestroy(LinkQueue*p){assert(p);Queue*curp-top;while(cur){Queue*nextcur-next;free(cur);curnext;}p-size0;p-tailNULL;p-topNULL;}//判断是否为NULLboolQueueEmpty(LinkQueue*p){assert(p);returnp-size0?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(newnodeNULL){perror(newnode);exit(-1);}newnode-nextNULL;newnode-valx;if(QueueEmpty(p)){p-tailp-topnewnode;}else{p-tail-nextnewnode;p-tailnewnode;}p-size;}//出队DataTypeDeQueue(LinkQueue*p){assert(p);assert(!QueueEmpty(p));DataType xp-top-val;Queue*curp-top-next;free(p-top);p-topcur;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){inttopDeQueue(obj-q1);Queueback(obj-q2,top);}returnDeQueue(obj-q1);}else{while(QueueSize(obj-q2)1){inttopDeQueue(obj-q2);Queueback(obj-q1,top);}returnDeQueue(obj-q2);}}intmyStackTop(MyStack*obj){if(!QueueEmpty(obj-q1)){while(QueueSize(obj-q1)1){inttopDeQueue(obj-q1);Queueback(obj-q2,top);}intxDeQueue(obj-q1);Queueback(obj-q2,x);returnx;}else{while(QueueSize(obj-q2)1){inttopDeQueue(obj-q2);Queueback(obj-q1,top);}intxDeQueue(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 1myQueue.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-arrNULL){perror(p-arr);exit(-1);}p-top0;p-capacity4;}//入栈voidStackpush(SqStack*p,DataType x){assert(p);if(p-topp-capacity){DataType*tmp(DataType*)realloc(p-arr,2*p-capacity*sizeof(DataType));if(tmpNULL){perror(tmp);exit(-1);}p-arrtmp;p-capacity*2;}p-arr[p-top]x;p-top;}//判空boolEmpStack(SqStack*p){assert(p);returnp-top0?true:false;}//出栈DataTypeStackPop(SqStack*p){assert(p);assert(!EmpStack(p));DataType xp-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-arrNULL;p-top0;p-capacity0;}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)){inttmpStackSize(obj-Spush);while(tmp--){intxStackPop(obj-Spush);Stackpush(obj-SPop,x);}}returnStackPop(obj-SPop);}intmyQueuePeek(MyQueue*obj){if(EmpStack(obj-SPop)){inttmpStackSize(obj-Spush);while(tmp--){intxStackPop(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);objNULL;}