leetcode 225. Implement Stack using Queues 双队列实现栈

你的名字 2022-06-08 12:06 169阅读 0赞

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

要求使用双队列实现一个栈的所有的功能，是一个很经典的问题，需要记住学习。

建议和这道题[leetcode 232. Implement Queue using Stacks 双栈实现队列][leetcode 232. Implement Queue using Stacks] 一起学习。

1）取栈顶元素： 返回有元素的队列的首元素

2）判栈空：若队列a和b均为空则栈空

3）入栈：a队列当前有元素，b为空（倒过来也一样）则将需要入栈的元素先放b中，然后将a中的元素依次出列并入列倒b中。（保证有一个队列是空的）

4）出栈：将有元素的队列出列即可。

代码如下：

import java.util.LinkedList;
    import java.util.Queue;
    
    /*
     * 使用双队列来实现栈的功能
     * （1）取栈顶元素： 返回有元素的队列的首元素
     * （2）判栈空：若队列a和b均为空则栈空
     * （3）入栈：a队列当前有元素，b为空（倒过来也一样）则将需要入栈的元素先放b中，
     * 然后将a中的元素依次出列并入列倒b中。（保证有一个队列是空的）
     * （4）出栈：将有元素的队列出列即可。
     * */
    public class MyStack
    {
        
        Queue<Integer> queue1=null;
        Queue<Integer> queue2=null;
        /** Initialize your data structure here. */
        public MyStack() 
        {
            queue1=new LinkedList<>();
            queue2=new LinkedList<>();
        }
    
        /** Push element x onto stack. */
        public void push(int x) 
        {
            if(queue1.isEmpty())
            {
                queue1.add(x);
                while(queue2.isEmpty()==false)
                    queue1.add(queue2.poll());
            }else 
            {
                queue2.add(x);
                while(queue1.isEmpty()==false)
                    queue2.add(queue1.poll());
            }
        }
    
        /** Removes the element on top of the stack and returns that element. */
        public int pop() 
        {
            if(queue1.isEmpty())
                return queue2.poll();
            else 
                return queue1.poll();
        }
    
        /** Get the top element. */
        public int top()
        {
            if(queue1.isEmpty())
                return queue2.peek();
            else 
                return queue1.peek();
        }
    
        /** Returns whether the stack is empty. */
        public boolean empty()
        {
            return queue1.isEmpty() && queue2.isEmpty();
        }
    }
    
    /**
     * 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();
     * boolean param_4 = obj.empty();
     */

[leetcode 232. Implement Queue using Stacks]: http://blog.csdn.net/jackzhang_123/article/details/78083407