[leetcode] 225. Implement Stack using Queues

[leetcode] 225. Implement Stack using Queues

Description

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. Example:

MyStack stack = new MyStack();stack.push(1);stack.push(2); stack.top(); // returns 2stack.pop(); // returns 2stack.empty(); // returns false

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

分析

题目的意思是：用队列实现栈的操作。

队列是先进先出，而栈是先进后出。每次把新加入的数插到前头，这样队列保存的顺序和栈的顺序是相反的，它们的取出方式也是反的，那么反反得正，就是我们需要的顺序了。我们需要一个辅助队列tmp，把s的元素也逆着顺序存入tmp中，此时加入新元素x，再把tmp中的元素存回来，这样就是我们要的顺序了，其他三个操作也就直接调用队列的操作即可，

代码

class MyStack {private: queue q1;public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { queue tmp; while(!q1.empty()){ tmp.push(q1.front()); q1.pop(); } q1.push(x); while(!tmp.empty()){ q1.push(tmp.front()); tmp.pop(); } } /** Removes the element on top of the stack and returns that element. */ int pop() { int t=top(); q1.pop(); return t; } /** Get the top element. */ int top() { return q1.front(); } /** Returns whether the stack is empty. */ bool empty() { return q1.empty(); }};/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * bool param_4 = obj.empty(); */

参考文献

​​[LeetCode] Implement Stack using Queues 用队列来实现栈​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。