225. 用队列实现栈

解题思路:

利用两个队列:数据队列data和辅助队列helper实现栈的功能。

1.每来一个元素,先入辅助队列

2.如果数据队列非空,则将数据队列中的元素拷贝到辅助队列中

3.将辅助队列中的元素拷贝到数据队列,这样就可以保证数据队列的首部始终是后入队列的元素了,此时的数据队列就相当于一个栈了

4.其他功能(除了入栈)就可以正常按照栈的操作进行了

代码实现:

class MyStack {

    /** Initialize your data structure here. */
    private Queue<Integer> data;//数据队列
    private Queue<Integer> helper;//辅队列
    public MyStack() {
        data =new LinkedList<>();
        helper=new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        //始终保持数据队列的队首是后入队列的元素
        //1.先入辅助队列
        //2.如果数据队列中有元素,则拷贝到辅助队列
        //3.将辅助队列中的元素拷贝到数据队列
        helper.add(x);
        while(!data.isEmpty()){
            helper.add(data.poll());
        }
        while(!helper.isEmpty()){
            data.add(helper.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return data.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return data.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return data.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();
 */

 

225. 用队列实现栈225. 用队列实现栈 我就是个渴望成长的小菜鸡 发布了201 篇原创文章 · 获赞 14 · 访问量 2万+ 私信 关注
上一篇:java中stack与c++中stack的区别


下一篇:寒假CS精英挑战营_算法部分_第0周_直方图中最大的矩形_笔记