[Leetcode] Implement Stack using Queues 用队列实现栈

ivan_qhz 发布于2019-08-14 12:39 / 2426人阅读

摘要：双队列法复杂度时间空间思路和类似，我们也可以用两个队列来模拟栈的操作。当时，我们将数字进非空的队列就行了。操作和一样，区别在于我们拿到最后一个数后，还要再把它进另一个队列中。

双队列法 复杂度

时间 O(N) 空间 O(N)

思路

和Implement Queue using Stack类似，我们也可以用两个队列来模拟栈的操作。当push时，我们将数字offer进非空的队列就行了。当pop时，因为要拿的是队列最后一个数，我们先将它前面的数offer进另一个队列，然后多带带拿出最后一个数，并且不再offer进另一个队列，这样，另一个队列就少了最后一个数，而我们也拿到了最后一个数，而本来的队列就变成空了，等待下次的pop操作来填满。top操作和pop一样，区别在于我们拿到最后一个数后，还要再把它offer进另一个队列中。

代码

class MyStack {
    
    Queue queue1;
    Queue queue2;
    int size;
    
    public MyStack(){
        this.queue1 = new LinkedList();
        this.queue2 = new LinkedList();
        this.size = 0;
    }
    
    // Push element x onto stack.
    public void push(int x) {
        if(queue1.isEmpty()){
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
        size++;
    }

    // Removes the element on top of the stack.
    public int pop() {
        if(size == 0){
            return -1;
        }
        int res = 0;
        // 将前面的数都offer进另一个队列，然后拿出最后一个数
        if(queue1.isEmpty()){
            for(int i = 0; i < size - 1; i++){
                queue1.offer(queue2.poll());
            }
            res = queue2.poll();
        } else {
            for(int i = 0; i < size - 1; i++){
                queue2.offer(queue1.poll());
            }
            res = queue1.poll();
        }
        size--;
        return res;
    }

    // Get the top element.
    public int top() {
        if(size == 0){
            return -1;
        }
        // 先执行pop
        int top = pop();
        // 然后将pop出来的数再塞回队列就行了
        if(queue1.isEmpty()){
            queue2.offer(top);
        } else {
            queue1.offer(top);
        }
        // 注意size也要加1
        size++;
        return top;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return size == 0;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64618.html

LeetCode 225：用队列实现栈 Implement Stack using Queues

摘要：下面是入栈时代码获得队列长度反转次数为队列长度减一反转语言没有栈和队列数据结构，只能用数组或双端队列实现。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用队列实现栈的下列操作： push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空 Impl...

AlanKeene 2019-08-19 10:28 评论0 收藏0
leetcode225 implement stack using queues

摘要：题目要求使用队列来模拟实现一个栈。栈是指先进后出的数据结构，而队列则是先进先出的数据结构。队列的包括在队列尾插入数据，输出队列头的数据，查看队列的长度，队列是否为空。题目要求 Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of que...

binta 2019-08-15 13:30 评论0 收藏0
LeetCode 232：用栈实现队列 Implement Queue using Stacks

摘要：题目使用栈实现队列的下列操作将一个元素放入队列的尾部。用栈实现队列，可以用两个栈完成题解。入队列时用存入节点，出队列时内节点顺序出栈压入中。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队...

cloud 2019-08-19 10:26 评论0 收藏0
[Leetcode] Implement Queue using Stacks 用栈实现队列

摘要：注意的方法是和，实际上我们应该实现的是和或者和，的实现和是一样的，但将改为时，我们要先把到的元素保存，然后再弹出输出栈，然后返回这个保存的元素。 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to th...

Martin91 2019-08-14 12:29 评论0 收藏0
leetcode232 Implement Queue using Stacks

摘要：题目要求通过队列实现一个栈的功能。栈的为压入栈顶，出栈，栈顶元素，栈是否为空。重复上述的操作。但是当需要弹出元素时，则从桶弹出。这样，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保证位输入顺序。极大的减少了不必要的入栈出栈。题目要求 Implement the following operations of a queue using stacks. push(x) ...

golden_hamster 2019-08-15 13:32 评论0 收藏0