[LeetCode]Implement Stack using Queues

Implement the following operations of a stack using queues.

Notes:You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).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 — which means onlypush to back,pop from front,size, andis emptyoperations are valid.

Update (2015-06-11):The class name of theJavafunction had been updated toMyStackinstead of Stack.

Credits:

Special thanks to@jianchao.li.fighterfor adding this problem and all test cases.

[LeetCode]

两种实现方法

1）两个队列，当取栈顶时，把所有元素进到另一个队列，然后最后出队列的就是栈顶。pop的操作也是类似的，注意两个队列之间的转换。

2）一个队列，记录队列此时的长度n，，出队列第n次的元素就是栈顶元素。我们可以把出队列的元素再次入队列，这样就可以用一个队列实现。

同理用两个栈实现队列也是类似的做法。

两个队列实现：

class Stack {private:queue<int>temp[2];int cur = 0;public:// Push element x onto stack.void push(int x) {temp[cur].push(x);}// Removes the element on top of the stack.void pop(void) {while(temp[cur].size()>1){int n = temp[cur].front();temp[cur].pop();temp[1-cur].push(n);}temp[cur].pop();cur = 1-cur;}// Get the top element.int top(void) {while(temp[cur].size()>1){int n = temp[cur].front();temp[cur].pop();temp[1-cur].push(n);}int ret = temp[cur].front();temp[cur].pop();temp[1-cur].push(ret);cur = 1- cur;return ret;}// Return whether the stack is empty.bool empty(void) {return temp[cur].empty();}};一个队列实现：class Stack {private:queue<int>temp;public:// Push element x onto stack.void push(int x) {temp.push(x);}// Removes the element on top of the stack.void pop(void) {int len = temp.size();while(len>1){int n = temp.front();temp.pop();temp.push(n);len — ;}temp.pop();}// Get the top element.int top(void) {int len = temp.size();while(len>1){int n = temp.front();temp.pop();temp.push(n);len — ;}int ret = temp.front();temp.pop();temp.push(ret);return ret;}// Return whether the stack is empty.bool empty(void) {return temp.empty();}};

只能昏昏沉沉地沿着青草和泥土的气息前进。