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。

232. Implement Queue using Stacks 232. Implement Queue using Stacks

Implement the following operations of a queue using stacks.

• push(x) — Push element x to the back of queue.
• pop() — Removes the element from in front of queue.
• peek() — Get the front element.
• empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

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

本题要求用堆栈来实现队列的功能。因为堆栈是后进先出，而队列是先进先出，顺序正好相反。比如进入队列的顺序是1,2,3，但是进到堆栈stk1之后，从栈顶到栈底的顺序就变成了3,2,1，此时如果要实现队列出队的效果，就必须借助另一个堆栈stk2，把stk1的内容压入到stk2，这样从栈顶到栈底的顺序就和队列一样了，是1,2,3。 所以本题借助两个堆栈stk1和stk2，stk1就是常规的数据来了就压栈，当需要实现队列的pop效果时，就借助stk2倒腾一下，如果又要实现队列的push效果时，又要把stk2的数据捣腾回stk1。 总的来说，我们使用懒人规则，每次直到调用某个操作，且当前stk*不能满足要求时，才捣腾stk1和stk2。 完整代码如下：

class MyQueue {
private:
    stack<int> stk1, stk2; // 输入来源1,2,3，stk1从栈底到栈顶的顺序是1,2,3，stk2从栈底到栈顶的顺序是3,2,1
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x)
    {
        while (!stk2.empty()) {
            stk1.push(stk2.top());
            stk2.pop();
        }
        stk1.push(x);
    } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        int top = stk2.top();
        stk2.pop();
        return top;
    } /** Get the front element. */
    int peek()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
        return stk2.top();
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

本代码提交AC，用时3MS。
二刷。其实push的时候可以不需要把stk2的数据倒腾回stk1，stk2的数据始终是队列头的，stk1的数据始终是队列尾的，代码如下：

class MyQueue {
private:
    stack<int> stk1, stk2;
    void adjust()
    {
        while (!stk1.empty()) {
            stk2.push(stk1.top());
            stk1.pop();
        }
    }
public: /** Initialize your data structure here. */
    MyQueue() {} /** Push element x to the back of queue. */
    void push(int x) { stk1.push(x); } /** Removes the element from in front of queue and returns that element. */
    int pop()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        stk2.pop();
        return ans;
    } /** Get the front element. */
    int peek()
    {
        if (stk2.empty())
            adjust();
        int ans = stk2.top();
        return ans;
    } /** Returns whether the queue is empty. */
    bool empty() { return stk1.empty() && stk2.empty(); }
};

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