题目描述：
解法一（自然解法使用两个栈 入队 - O(1)， 出队 - O(n)）：
class MyQueue {
stack<int> stk1;
stack<int> stk2;
int Front;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
if(stk1.size()==0) Front=x;
stk1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(!stk1.empty()){
int res=Front;
while(stk1.size()>1){
stk2.push(stk1.top());
stk1.pop();
}
stk1.pop();
Front=stk2.empty()? -1:stk2.top();
while(!stk2.empty()){
stk1.push(stk2.top());
stk2.pop();
}
return res;
}
else return -1;
}
/** Get the front element. */
int peek() {
return Front;
}
/** Returns whether the queue is empty. */
bool empty() {
return stk1.empty();
}
};
/**
* 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();
*/解法二（改进版使用两个栈 入队 - O(1)，出队 - 摊还复杂度 O(1)）：
class MyQueue {
stack<int> stk1;
stack<int> stk2;
int Front;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
if(stk1.empty()) Front=x;
stk1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(!stk2.empty()){
int res=stk2.top();
stk2.pop();
return res;
}
else{
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
int res=stk2.top();
stk2.pop();
return res;
}
}
/** Get the front element. */
int peek() {
if(!stk2.empty())
return stk2.top();
else return Front;
}
/** Returns whether the queue is empty. */
bool empty() {
return stk2.empty()&&stk1.empty();
}
};
/**
* 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();
*/学习到一个概念：摊还复杂度。
解法三使用两个栈 入队 - O(n)， 出队 - O(1)：
class MyQueue {
stack<int> stk1;
stack<int> stk2;
int Front;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
if(stk1.empty()) Front=x;
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
stk2.push(x);
while(!stk2.empty()){
stk1.push(stk2.top());
stk2.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int res=Front;
stk1.pop();
Front=stk1.empty()? -1:stk1.top();
return res;
}
/** Get the front element. */
int peek() {
return Front;
}
/** Returns whether the queue is empty. */
bool empty() {
return stk1.empty();
}
};
/**
* 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();
*/