用两个栈,分别为 stk1,stk2,当 push 的时候,直接 push 进 stk1,pop 时,如果 stk2 为空,则将 stk1 全部弹出并依次入栈 stk2,返回 stk2 的 top 即可。
class MyQueue { public: /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { stk1.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { int ret = peek(); stk2.pop(); return ret; } /** Get the front element. */ int peek() { if(stk2.empty()) { while(!stk1.empty()) { stk2.push(stk1.top()); stk1.pop(); } } return stk2.top(); } /** Returns whether the queue is empty. */ bool empty() { return stk1.empty() && stk2.empty(); } private: stack<int> stk1, stk2; };