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

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Solution:

使用两个队列qm,qs, qm存储元素，qs作为临时存储:

1)入栈列时直接qm.push

2)出栈时，先将qm中的前N-1个元素push到qs中，然后pop出最后的第N个元素，之后把qs中的元素转移到qm中

 1 class Stack { 2 public: 3     // Push element x onto stack. 4     void push(int x)  5     { 6         qm.push(x);     7     } 8  9     // Removes the element on top of the stack.10     void pop() 11     {12         while (qm.size() > 1)13         {14             qs.push(qm.front());15             qm.pop();16         }17         18         qm.pop();19         20         while (!qs.empty())21         {22             qm.push(qs.front());23             qs.pop();24         }25     }26 27     // Get the top element.28     int top() 29     {30         return qm.back();    31     }32 33     // Return whether the stack is empty.34     bool empty() 35     {36         return qm.empty();    37     }38     39 private:40     std::queue<int> qm;41     std::queue<int> qs;42 };

[leetcode] 225. Implement Stack using Queues