# 题目

使用栈实现队列的下列操作：

push (x) -- 将一个元素放入队列的尾部。
pop () -- 从队列首部移除元素。
peek () -- 返回队列首部的元素。
empty () -- 返回队列是否为空。

示例:

说明:

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

# 分析

已知栈是先进后厨，队列是先进先出

所以用栈模拟队列一个栈肯定不行，那么就需要两个栈，一个栈输入一个栈输出

当 push 时，直接把数据放到输入栈中，要 pop 时，如果输出栈为空，则把输入栈内所有数据都出栈放到输出栈中，然后 pop，如果输出栈不为空，则直接出栈即可

	class MyQueue {
	public:
	stack<int> stIn;
	stack<int> stOut;
	/** Initialize your data structure here. */
	MyQueue() {

	}
	/** Push element x to the back of queue. */
	void push(int x) {
	stIn.push(x);
	}

	/** Removes the element from in front of queue and returns that element. */
	int pop() {
	// 只有当 stOut 为空的时候，再从 stIn 里导入数据（导入 stIn 全部数据）
	if (stOut.empty()) {
	// 从 stIn 导入数据直到 stIn 为空
	while(!stIn.empty()) {
	stOut.push(stIn.top());
	stIn.pop();
	}
	}
	int result = stOut.top();
	stOut.pop();
	return result;
	}

	/** Get the front element. */
	int peek() {
	int res = this->pop(); // 直接使用已有的 pop 函数
	stOut.push(res); // 因为 pop 函数弹出了元素 res，所以再添加回去
	return res;
	}

	/** Returns whether the queue is empty. */
	bool empty() {
	return stIn.empty() && stOut.empty();
	}
	};

使用队列实现栈的下列操作：

注意:

你只能使用队列的基本操作 -- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列，只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如，对一个空的栈不会调用 pop 或者 top 操作）。

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

队列模拟栈可以一个队列也可以两个队列，首先是两个队列，当有元素入栈时，第一个队列同样入列，当出栈时，1 号队列如果只有一个元素直接出列即可，如果有多个则使多余的元素入二号队列，然后 1 号队列出列，2 号队列再赋值给 1 号，2 号清空

	class MyStack {
	public:
	queue<int> que1;
	queue<int> que2; // 辅助队列，用来备份
	/** Initialize your data structure here. */
	MyStack() {

	}

	/** Push element x onto stack. */
	void push(int x) {
	que1.push(x);
	}

	/** Removes the element on top of the stack and returns that element. */
	int pop() {
	int size = que1.size();
	size--;
	while (size--) { // 将 que1 导入 que2，但要留下最后一个元素
	que2.push(que1.front());
	que1.pop();
	}

	int result = que1.front(); // 留下的最后一个元素就是要返回的值
	que1.pop();
	que1 = que2; // 再将 que2 赋值给 que1
	while (!que2.empty()) { // 清空 que2
	que2.pop();
	}
	return result;
	}

	/** Get the top element. */
	int top() {
	return que1.back();
	}

	/** Returns whether the stack is empty. */
	bool empty() {
	return que1.empty();
	}
	};

一个队列实现栈，只需要在实现出栈时让队列的头部元素（除最后一个元素外）重新从队列尾入列即可

	class MyStack {
	public:
	queue<int> que;
	/** Initialize your data structure here. */
	MyStack() {

	}
	/** Push element x onto stack. */
	void push(int x) {
	que.push(x);
	}
	/** Removes the element on top of the stack and returns that element. */
	int pop() {
	int size = que.size();
	size--;
	while (size--) { // 将队列头部的元素（除了最后一个元素外）重新添加到队列尾部
	que.push(que.front());
	que.pop();
	}
	int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
	que.pop();
	return result;
	}

	/** Get the top element. */
	int top() {
	return que.back();//front 获得队首元素，back 获得队尾元素
	}

	/** Returns whether the stack is empty. */
	bool empty() {
	return que.empty();
	}
	};

堆栈