1. 用两个栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

1.1 题目描述

题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); 	// queue is: [1]
myQueue.push(2); 	// queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); 	// return 1
myQueue.pop(); 		// return 1, queue is [2]
myQueue.empty(); 	// return false

1.2 解法

使用两个栈，一个用来接收值(_s1)，一个用来输出值(_s2)，当_s2为空时，将_s1的值移动到_s2中

class MyQueue 
{stack<int> _s1, _s2;// 将_s1的值移动到_s2中void moveS1ToS2(){while(!_s1.empty()) {_s2.push(_s1.top());_s1.pop();}}   
public:MyQueue() { }void push(int x) {_s1.push(x);}int pop() {if(empty())         return -1;if(_s2.empty())     moveS1ToS2();int top = _s2.top();_s2.pop();return top;}int peek() {if(empty())         return -1;if(_s2.empty())     moveS1ToS2();return _s2.top();}bool empty() {return _s1.empty() && _s2.empty();}
};

2. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

2.1 题目描述

题目描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

示例1：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

2.2 方法1，直接模拟

两个队列，一个用来入数据(q1)，一个用来出数据(q2)，与用栈实现队列的思路类似

class MyStack 
{queue<int> q1, q2;// 将q1的队列中的值移动到另q2中, 只剩一个void moveQ1(){while(q1.size() > 1) {q2.push(q1.front());q1.pop();}}
public:MyStack() {}void push(int x) {q1.push(x);}int pop() {if(empty())     return false;moveQ1();int ret = q1.front();q1.pop();swap(q1, q2);return ret;}int top() {if(empty())     return false;moveQ1();int ret = q1.front();q2.push(ret);q1.pop();swap(q1, q2);return ret;}bool empty() {return q1.empty() && q2.empty();}
};

2.3 方法2

精简一下方法1，但仍然使用两个队列，一个用来暂时存储存储加入的数据(q2)，一个用来输出(q1)，且q1使用pop()出来的元素的顺序是栈出元素的顺序，这是在push()数据时将q2的值移动到q1导致的。

class MyStack 
{queue<int> q1, q2;
public:MyStack() {}void push(int x) {q2.push(x);while(!q1.empty()) {q2.push(q1.front());q1.pop();}swap(q1, q2);}int pop() {int ret = q1.front();q1.pop();return ret;}int top() {return q1.front();}bool empty() {return q1.empty();}
};

2.3 方法3，一个队列

注意到q2完全可以不用

class MyStack 
{queue<int> q1;
public:MyStack() {}void push(int x) {int sz = q1.size();q1.push(x);for(int i=0; i<sz; ++i) {int tmp = q1.front();q1.pop();q1.push(tmp);}}int pop() {int ret = q1.front();q1.pop();return ret;}int top() {return q1.front();}bool empty() {return q1.empty();}
};