算法-栈和队列：用队列组成栈

使用队列（单向队列）实现栈的下列操作：

pop():弹出栈顶元素。push(x):将x入栈。top():获取栈顶元素。empty():返回栈是否为空。

方法一：使用两个队列实现栈

#include #include using namespace std;class MyStack{public: queue quIn; queue quOut;//纯纯用来备份的 //- push(x):将x入栈。 void push(int x){ quIn.push(x); } //- pop():弹出栈顶元素。 int pop(){ int res; int size = quIn.size(); size--; while (size--) { //将quIn导入quOut，但是要留下最后一个元素 quOut.push(quIn.front()); quIn.pop(); } res = quIn.front(); quIn = quOut; return res; } //- top():获取栈顶元素。 int top(){ return quIn.back(); } //- empty():返回栈是否为空。 bool empty(){ return quIn.empty(); }};int main(){ MyStack mySt; mySt.push(1); mySt.push(2); mySt.push(3); mySt.push(4); cout<<"myQue.empty()=="<

方法二：使用一个队列实现栈。
和方法一的差别在与pop函数，方法二采用的策略是将前面的元素重新进入一次队列。

#include #include using namespace std;class MyStack{public: queue quIn; //- push(x):将x入栈。 void push(int x){ quIn.push(x); } //- pop():弹出栈顶元素。将前面的元素重新进入队列 int pop(){ int res; int size = quIn.size(); size--; while (size--) { quIn.push(quIn.front()); quIn.pop(); } res = quIn.front(); return res; } //- top():获取栈顶元素。 int top(){ return quIn.back(); } //- empty():返回栈是否为空。 bool empty(){ return quIn.empty(); }};int main(){ MyStack mySt; mySt.push(1); mySt.push(2); mySt.push(3); mySt.push(4); cout<<"myQue.empty()=="<