一、题意
二、思考过程
用栈实现队列和用队列实现栈的方法是不一样的。
2.1用两个队列实现栈
class MyStack { public: /* 队列1和队列2 */ queue<int> que1; queue<int> que2;//辅助队列用来辅助 MyStack() { } //让x入队列1 void push(int x) { que1.push(x); } int pop() { int size=que1.size(); size--; while(size--)//将que1导入到que2,但要留下最后一个元素 { que2.push(que1.front()); que1.pop(); } int result=que1.front();//留下的最后一个元素就是要返回的值 que1.pop(); que1=que2;//再将que2赋值给que1 while(!que2.empty())//清空que2 { que2.pop(); } return result; } int top() { return que1.back(); } bool empty() { return que1.empty(); } };
2.2使用一个队列实现栈
其实使用一个队列也可以实现栈,在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素)重新添加到队列尾部,此时在弹出的元素顺序就是栈的元素。
class MyStack { public: queue<int> que; /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { que.push(x); } /** Removes the element on top of the stack and returns that element. */ int pop() { int size = que.size(); size--; while (size--) { // 将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部 que.push(que.front()); que.pop(); } int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了 que.pop(); return result; } /** Get the top element. */ int top() { return que.back(); } /** Returns whether the stack is empty. */ bool empty() { return que.empty(); } };