【小白刷题之路Day29】leetcode225. 用队列实现栈(C++ STL 队列的使用操作)

leetcode225. 用队列实现栈 使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 注意: 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-stack-using-queues 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

我的第一次提交：

class MyStack { private: queue<int> int_queue; public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { int_queue.push(x); } /** Removes the element on top of the stack and returns that element. */ int pop() { for (int i=0; i<int_queue.size()-1; ++i){ int tmp = int_queue.front(); int_queue.pop(); int_queue.push(tmp); } int res = int_queue.front(); int_queue.pop(); return res; } /** Get the top element. */ int top() { int res = pop(); int_queue.push(res); return res; } /** Returns whether the stack is empty. */ bool empty() { return int_queue.empty(); } };

缺点：push()操作简单，数据在元素中以队列形式存放，结果就是后面每次操作时都要循环处理数据，

查看别人代码，令人惊喜的是看到有人在push()操作时加一点工作量，让数据在队列中以栈的顺序存储好，接下来所有操作将变得简单。

新思路的第二次提交：

class MyStack { private: queue<int> int_queue; public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { int_queue.push(x); for (int i=0; i<int_queue.size()-1; ++i){ int_queue.push(int_queue.front()); int_queue.pop(); } } /** Removes the element on top of the stack and returns that element. */ int pop() { int res = int_queue.front(); int_queue.pop(); return res; } /** Get the top element. */ int top() { return int_queue.front(); } /** Returns whether the stack is empty. */ bool empty() { return int_queue.empty(); } };

值得注意的是push()操作：

void push(int x) { nums.push(x); //将前面的size-1个元素放到后面去 for(int i = 0; i < nums.size() - 1; i++){ nums.push(nums.front()); nums.pop(); } }

刚开始怀疑了好久，把前面元素整体挪到后面后导致第二次pop()出现错误，后来才猛然反应过来，前面元素push()时，也已经按这个规则完成反向排序，是我思考的慢了。

总结 C++ STL 的queue操作： queue<int> q;   q.push()q.pop()  无返回值q.front()  返回队头元素q.back() 返回队尾元素q.size()q.empty() 本题是数据结构队列和栈的入门题、熟悉题。

 

转载于:https://www.cnblogs.com/ACStrive/p/11602440.html

相关资源：JAVA上百实例源码以及开源项目