LeetCode Implement Stack using Queues

LeetCode 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.

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).

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。

Leave a Reply

Your email address will not be published. Required fields are marked *