剑指offer/LintCode494_用两个队列实现一个栈

rose 发布于2019-08-14 18:10 / 1847人阅读

摘要：剑指用两个队列实现一个栈声明文章均为本人技术笔记，转载请注明出处解题思路实现功能用两个队列实现一个栈，实现，，和方法解题思路假设有队列和实现栈的操作实现栈操作始终用来入队实现实现栈的方法模拟栈的过程中，保证两个队列中始终有一个队列为空，另一

剑指offer/LintCode494_用两个队列实现一个栈 声明

文章均为本人技术笔记，转载请注明出处https://segmentfault.com/u/yzwall

解题思路 实现功能：

用两个队列实现一个栈，实现push(element)，pop()，top()和isEmpty()方法；

解题思路

假设有队列queue1和queue2；

实现栈的push(element)操作

实现栈push(element)操作：始终用来queue1入队实现；

实现栈的pop()方法

模拟栈的过程中，保证两个队列中始终有一个队列为空，另一个队列不空，空栈时两队列全部为空；；

queue1和queue2运行过程中有时充当from，有时充当to；

非空队列from中所有元素依次出队并入队to队列中，直到from中只剩下一个元素，

实现pop()操作：弹出from中最后一个元素；

实现top()操作：保存from中最后一个元素并返回，from弹出并入队to队列中（保证每次操作完成后，两个队列中始终有一个队列为空，另一个队列不空，空栈除外）；

注意点

使用java.util.ArrayDeque实现队列时，切记用offer()方法入队而不用push()方法，用poll()方法出队而不用pop()方法；

题目链接

lintcode 494: http://www.lintcode.com/en/problem/implement-stack-by-two-queues/;

Java代码

/**
 * 用两个队列实现一个栈
 * http://www.lintcode.com/en/problem/implement-stack-by-two-queues/
 * @author yzwall
 */
import java.util.ArrayDeque;
class Stack {
    private ArrayDeque queue1;
    private ArrayDeque queue2;
    int top;
    
    Stack() {
        this.queue1 = new ArrayDeque<>();
        this.queue2 = new ArrayDeque<>();
    }
    
    // queue1始终负责实现栈的push操作
    public void push(int element) {
        queue1.offer(element);
    }
    
    // 将from队列元素出队，并依次入队到to队列，直到from队列中只有一个元素
    public void move(ArrayDeque from,
                     ArrayDeque to) {
        while (from.size() > 1) {
            to.offer(from.poll());
        }
    }
    
    public void pop() {
        if (!isEmpty()) {
            if (!queue1.isEmpty()) {
                move(queue1, queue2);
                // queue1队列pop后为空
                queue1.poll();
            } else if (!queue2.isEmpty()) {
                move(queue2, queue1);
                // queue1队列pop后为空
                queue2.poll();
            }
        }
    }
    
    public int top() {
        if (!isEmpty()) {
            if (!queue1.isEmpty()) {
                move(queue1, queue2);
                // 获取模拟栈顶元素，清空栈顶所在队列
                top = queue1.peek();
                queue2.offer(queue1.poll());
            } else if (!queue2.isEmpty()) {
                move(queue2, queue1);
                // 获取模拟栈顶元素，清空栈顶所在队列
                top = queue2.peek();
                queue1.offer(queue2.poll());
            }
            return top;
        }
        return 0;
    }
    
    public boolean isEmpty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

idc机房托管专线服务两个主体用一个域名两个域名用一个空间用java实现一个线程池两个栈

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

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

剑指offer/LintCode40_用两个栈模拟队列

摘要：剑指用两个栈模拟队列声明文章均为本人技术笔记，转载请注明出处解题思路实现功能用两个栈模拟实现一个队列的，和操作解题思路假设有两个栈队列实现始终用入栈实现队列和实现由于依次出栈并压入中，恰好保证中顺序与模拟队列顺序一致，始终保证栈顶元素为模拟剑指offer/LintCode40_用两个栈模拟队列声明文章均为本人技术笔记，转载请注明出处https://segmentfault.com...

bawn 2019-08-14 18:12 评论0 收藏0
剑指offer/LintCode12_最小栈

摘要：剑指最小栈声明文章均为本人技术笔记，转载请注明出处解题思路实现功能实现一个最小栈，要求操作均为复杂度，解题思路用栈存储数据用最小栈存储中最小元素，保证栈顶元素与栈顶元素同步，表示此时最小值将与此时最小值比较，将更小的一方压栈，保证中栈顶始终剑指offer/LintCode12_最小栈声明文章均为本人技术笔记，转载请注明出处https://segmentfault.com/u/yz...

Betta 2019-08-14 18:12 评论0 收藏0
剑指offer_二叉树的打印合集(C++_上下打印.换行打印.之字打印_bfs+栈与队列+用表格模拟

摘要：队列存放的是树节点的指针，其类型为打印完这个节点后将队列中的这个节点指向的左右子树入队，再把这个节点指针出队。注意一定要在有左右子树的时候在进队。选择二维数组形式返回，数组内以一维数组的形式储存。一行数据出队完毕后为。 ...

glumes 2021-10-08 10:04 评论0 收藏0
【转】《剑指Offer》JavaScript实战——用两个栈实现队列

摘要：题目描述用两个栈来实现一个队列，完成队列的和操作。队列中的元素为类型。下面是实现代码。题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。解题方法 let stack1=[],//两个数组模拟栈的行为 stack2=[]; function push(node) { // write code here //...

senntyou 2019-08-23 16:22 评论0 收藏0
【剑指offer】6.用两个栈实现队列

摘要：题目用两个栈来实现一个队列，完成队列的和操作。队列中的元素为类型。基本思路栈用于入队列存储栈出队列时将栈的数据依次出栈，并入栈到栈中栈出栈即栈的底部数据即队列要出的数据。注意栈为空才能补充栈的数据，否则会打乱当前的顺序。题目用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。基本思路栈1: 用于入队列存储栈2: 出队列时将栈1的数据依次出栈，并...

fredshare 2019-08-23 14:44 评论0 收藏0