LeetCode225 用队列实现栈

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

push(x) – 元素 x 入栈 pop() – 移除栈顶元素 top() – 获取栈顶元素 empty() – 返回栈是否为空 注意:

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

思考过程：用队列实现栈，首先队列是先进先出，而栈是先进后出，对于 pop 操作，即要弹出栈的尾部元素，top 操作即为要取栈尾，empty 检查是否为空，这几个都好写，主要的就是 push 操作，这个操作和队列很不一样。先实现其他操作吧，

	/** Removes the element on top of the stack and returns that element. */
	int pop() {
		int num = q.front();
		q.pop();
		return num;
	}

	/** Get the top element. */
	int top() {
		return q.front();
	}

	/** Returns whether the stack is empty. */
	bool empty() {
		return q.empty();
	}
private:
	queue<int> q;

剩下的就是 push 操作了。用一个临时的队列来存放需要 push 的值，再将原队列中的值 push 进去。

/** Push element x onto stack. */
void push(int x) {
	queue<int> temp_q;

	while (!q.empty())
	{
		int num = q.front();
		q.pop();
		temp_q.push(num);
	}
	q.push(x);
	while (!temp_q.empty())
	{
		int num = temp_q.front();
		temp_q.pop();
		q.push(num);
	}
}

最后整体的代码为：

class MyStack {
public:

	/** Initialize your data structure here. */
	MyStack() {

	}

	/** Push element x onto stack. */
	void push(int x) {
		queue<int> temp_q;

		while (!q.empty())
		{
			int num = q.front();
			q.pop();
			temp_q.push(num);
		}
		q.push(x);
		while (!temp_q.empty())
		{
			int num = temp_q.front();
			temp_q.pop();
			q.push(num);
		}
	}

	/** Removes the element on top of the stack and returns that element. */
	int pop() {
		int num = q.front();
		q.pop();
		return num;
	}

	/** Get the top element. */
	int top() {
		return q.front();
	}

	/** Returns whether the stack is empty. */
	bool empty() {
		return q.empty();
	}
private:
	queue<int> q;
};

提交上去，显示结果无错误。