用栈实现队列（C++）

leetcode链接

实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

示例 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

思路：队列是先进先出，栈是先进后出。用栈实现队列则需要用两个栈，一个是入队列的栈，一个是出队列的栈。将入队列的数据放进入队列的栈。出队列时，如果出队列的栈为空，则将入队列的栈中的全部数据逐个弹出，并压入到出队列的栈中，这样出队列的栈中，栈顶即是队列的队首。若出队列时，出队列的栈不为空，则弹出栈顶元素即可。

代码：

class MyQueue {		//用栈实现队列
	stack inStack;
	stack outStack;

public:
	MyQueue() {
		
	}

	void push(int x) {
		inStack.push(x);
	}

	int pop() {
		if (outStack.empty()) {
			while (!inStack.empty()) {
				outStack.push(inStack.top());
				inStack.pop();
			}
		}
		int result = outStack.top();
		outStack.pop();
		return result;
	}

	int peek() {
		int result = this->pop();
		outStack.push(result);
		return result;
	}

	bool empty() {
		return inStack.empty() && outStack.empty();
	}
};