栈(先进后出)
两个栈(第一个存数据,第二个辅助输出(先进后出))
效果(先进先出)
class MyQueue {
public:
/** Initialize your data structure here. */
stack<int>s1,s2;
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
while(s1.size()>1) s2.push(s1.top()),s1.pop();
int t=s1.top();
s1.pop();
while(s2.size()) s1.push(s2.top()),s2.pop();
return t;
}
/** Get the front element. */
int peek() {
while(s1.size()>1) s2.push(s1.top()),s1.pop();
int t=s1.top();
while(s2.size()) s1.push(s2.top()),s2.pop();
return t;
}
/** Returns whether the queue is empty. */
bool empty() {
return s1.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/
1.push(x),我们直接将x插入主栈中即可。
2.pop(),此时我们需要弹出最先进入栈的元素,也就是栈底元素。我们可以先将所有元素从主栈中弹出,压入辅助栈中。则辅助栈的栈顶元素就是我们要弹出的元素,将其弹出即可。然后再将辅助栈中的元素全部弹出,压入主栈中。
3.peek(),可以用和pop()操作类似的方式,得到最先压入栈的元素。
4.empty(),直接判断主栈是否为空即可。