思路:
一开始模糊的方向是想着每次调用pop就吧push的栈全部压到pop的栈,同样调用push也罢pop的栈压入push为了保证两者信息的一致,但这里涉及到两次调用同一个操作时肯定一个容器为空还要压入另一个吗,感觉绕远还不对果断放弃(其实花了很久才放弃)。
然后直接模拟入手,设入队放入栈1,当要出队肯定是要栈底,所以将栈1出栈干净到栈2才能拿到底部,这时若继续出队则继续出栈2栈1不动,若继续的是入队则栈2不动栈1入栈,那如果栈2没出完栈1又入了新元素,影响使用吗?此时两个栈都有元素,继续出队是出栈2,极限是出完了还要出,出的是栈1没有弄到栈2的所以条件在此,还要出队时栈2没元素则请求栈1的过来,且要请求完才能保证栈顶是队尾。另一方面入队考虑发现根本不用考虑栈2的情况无限入栈1。
总接:
stack1是队列的后半部用来入队的部分,数目不固定可能为0可能很多,stack2是队列的前半部数目也是不一定,当为0且还请求了出队则会将后半部更新为头半部。
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution
{
public:
void push(int node) {
stack1.push(node); //入队没什么要求,就是入stack1
}
int pop() {
if(stack2.size()==0) {//出队先判代表头部部分的stack2是否还有,没有则要那后面的部分来更新
while (stack1.size() > 0) {//要吧stac1拿完才能拿到栈底即队头
stack2.push(stack1.top());
stack1.pop();
}
}
int ret=stack2.top();
stack2.pop();
return ret;
}
private:
stack<int> stack1;
stack<int> stack2;
};
京公网安备 11010502036488号