225. Implement Stack using Queues

Implement the following operations of a stack using queues.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• empty() — Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue — which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). 225. Implement Stack using Queues

---

和LeetCode Implement Queue using Stacks正好相反，本题要用队列实现堆栈的效果。 队列是先进先出的，而堆栈是后进先出。如果用队列q保存数据，则要实现堆栈的pop效果时，需要获取到q的队尾元素，可以不断把q的数据从队首弹出，同时压回队尾，重复n-1次，此时队首元素就是原来的队尾元素了。堆栈的top效果和push的实现方法是类似的。 这种题目就是数据不断的倒腾。。。 完整代码如下：

class MyStack {
private:
    queue<int> m_q;
public: /** Initialize your data structure here. */
    MyStack() {} /** Push element x onto stack. */
    void push(int x) { m_q.push(x); } /** Removes the element on top of the stack and returns that element. */
    int pop()
    {
        int sz = m_q.size();
        for (int i = 0; i < sz – 1; ++i) {
            m_q.push(m_q.front());
            m_q.pop();
        }
        int front = m_q.front();
        m_q.pop();
        return front;
    } /** Get the top element. */
    int top()
    {
        int sz = m_q.size(), front = m_q.front();
        for (int i = 0; i < sz; ++i) {
            front = m_q.front();
            m_q.push(front);
            m_q.pop();
        }
        return front;
    } /** Returns whether the stack is empty. */
    bool empty() { return m_q.empty(); }
};

本代码提交AC，用时3MS。

二刷。用两个queue来模拟stack，不如上面的解法好看：

class MyStack {
private:
	vector<queue<int>> vq_;
	int data_queue_id_;
public:
	/** Initialize your data structure here. */
	MyStack() {
		vq_.push_back(queue<int>());
		vq_.push_back(queue<int>());
		data_queue_id_ = 0;
	}

	/** Push element x onto stack. */
	void push(int x) {
		vq_[data_queue_id_].push(x);
	}

	/** Removes the element on top of the stack and returns that element. */
	int pop() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			if (!vq_[data_queue_id_].empty()) {
				vq_[another_id].push(last_data);
			}
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Get the top element. */
	int top() {
		int another_id = 1 - data_queue_id_;
		int last_data = 0;
		while (!vq_[data_queue_id_].empty()) {
			last_data = vq_[data_queue_id_].front();
			vq_[data_queue_id_].pop();
			vq_[another_id].push(last_data);
		}
		swap(another_id, data_queue_id_);
		return last_data;
	}

	/** Returns whether the stack is empty. */
	bool empty() {
		return vq_[data_queue_id_].empty();
	}
};

本代码提交AC，用时0MS。