![[LeetCode] 232、用栈实现队列](http://pic.xiahunao.cn/yaotu/[LeetCode] 232、用栈实现队列)
题目描述使用栈实现队列的下列操作push(x) – 将一个元素放入队列的尾部。pop() – 从队列首部移除元素。peek() – 返回队列首部的元素。empty() – 返回队列是否为空。参考代码核心思路用两次「后进先出」凑出「先进先出」栈的特性是后进先出队列的特性是先进先出两者顺序完全相反。一个栈只能反转一次顺序那用两个栈连续反转两次整体顺序就会恢复成原本的入队顺序从而模拟出队列的效果。两个栈的分工我们给两个栈分配固定职责避免来回倒腾元素输入栈inStack只负责接收新加入的元素所有 push 操作直接往这里塞。输出栈outStack只负责弹出和查看队头元素所有 pop / peek 都从这里取。核心规则只有当输出栈为空时才把输入栈里的所有元素一次性全部倒入输出栈。// 该题解有一些异常输入没处理可用“全局变量”的方式处理一下就好classMyQueue{public:/** Initialize your data structure here. */MyQueue(){}/** Push element x to the back of queue. */voidpush(intx){stack1.push(x);}/** Removes the element from in front of queue and returns that element. */intpop(){if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}}if(!stack2.empty()){intresstack2.top();stack2.pop();returnres;}return-1;}/** Get the front element. */intpeek(){if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}}if(!stack2.empty())returnstack2.top();return-1;}/** Returns whether the queue is empty. */boolempty(){if(stack1.empty()stack2.empty())returntrue;elsereturnfalse;}private:stackintstack1;// 进队列stackintstack2;// 出队列};/** * Your MyQueue object will be instantiated and called as such: * MyQueue* obj new MyQueue(); * obj-push(x); * int param_2 obj-pop(); * int param_3 obj-peek(); * bool param_4 obj-empty(); */补充用队列实现栈参考思路在非空的队列里面操作boolg_invalidInputfalse;classMyStack{public:/** Initialize your data structure here. */MyStack(){// nothing}/** Push element x onto stack. */voidpush(intx){if(!q1.empty())q1.push(x);elseq2.push(x);}/** Removes the element on top of the stack and returns that element. */intpop(){if(!q1.empty()){intnumq1.size();while(num!1){q2.push(q1.front());q1.pop();num--;}intresq1.front();q1.pop();returnres;}else{intnumq2.size();while(num!1){q1.push(q2.front());q2.pop();num--;}intresq2.front();q2.pop();returnres;}g_invalidInputtrue;return-1;}/** Get the top element. */inttop(){if(!q1.empty()){returnq1.back();}else{returnq2.back();}g_invalidInputtrue;return-1;}/** Returns whether the stack is empty. */boolempty(){if(q1.empty()q2.empty())returntrue;elsereturnfalse;}private:queueintq1,q2;};/** * Your MyStack object will be instantiated and called as such: * MyStack* obj new MyStack(); * obj-push(x); * int param_2 obj-pop(); * int param_3 obj-top(); * bool param_4 obj-empty(); */
题目描述使用栈实现队列的下列操作push(x) – 将一个元素放入队列的尾部。pop() – 从队列首部移除元素。peek() – 返回队列首部的元素。empty() – 返回队列是否为空。参考代码核心思路用两次「后进先出」凑出「先进先出」栈的特性是后进先出队列的特性是先进先出两者顺序完全相反。一个栈只能反转一次顺序那用两个栈连续反转两次整体顺序就会恢复成原本的入队顺序从而模拟出队列的效果。两个栈的分工我们给两个栈分配固定职责避免来回倒腾元素输入栈inStack只负责接收新加入的元素所有 push 操作直接往这里塞。输出栈outStack只负责弹出和查看队头元素所有 pop / peek 都从这里取。核心规则只有当输出栈为空时才把输入栈里的所有元素一次性全部倒入输出栈。// 该题解有一些异常输入没处理可用“全局变量”的方式处理一下就好classMyQueue{public:/** Initialize your data structure here. */MyQueue(){}/** Push element x to the back of queue. */voidpush(intx){stack1.push(x);}/** Removes the element from in front of queue and returns that element. */intpop(){if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}}if(!stack2.empty()){intresstack2.top();stack2.pop();returnres;}return-1;}/** Get the front element. */intpeek(){if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}}if(!stack2.empty())returnstack2.top();return-1;}/** Returns whether the queue is empty. */boolempty(){if(stack1.empty()stack2.empty())returntrue;elsereturnfalse;}private:stackintstack1;// 进队列stackintstack2;// 出队列};/** * Your MyQueue object will be instantiated and called as such: * MyQueue* obj new MyQueue(); * obj-push(x); * int param_2 obj-pop(); * int param_3 obj-peek(); * bool param_4 obj-empty(); */补充用队列实现栈参考思路在非空的队列里面操作boolg_invalidInputfalse;classMyStack{public:/** Initialize your data structure here. */MyStack(){// nothing}/** Push element x onto stack. */voidpush(intx){if(!q1.empty())q1.push(x);elseq2.push(x);}/** Removes the element on top of the stack and returns that element. */intpop(){if(!q1.empty()){intnumq1.size();while(num!1){q2.push(q1.front());q1.pop();num--;}intresq1.front();q1.pop();returnres;}else{intnumq2.size();while(num!1){q1.push(q2.front());q2.pop();num--;}intresq2.front();q2.pop();returnres;}g_invalidInputtrue;return-1;}/** Get the top element. */inttop(){if(!q1.empty()){returnq1.back();}else{returnq2.back();}g_invalidInputtrue;return-1;}/** Returns whether the stack is empty. */boolempty(){if(q1.empty()q2.empty())returntrue;elsereturnfalse;}private:queueintq1,q2;};/** * Your MyStack object will be instantiated and called as such: * MyStack* obj new MyStack(); * obj-push(x); * int param_2 obj-pop(); * int param_3 obj-top(); * bool param_4 obj-empty(); */
