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

bawn 发布于2019-08-14 18:12 / 3114人阅读

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

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

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

解题思路 实现功能：

用两个栈模拟实现一个队列的push(element)，pop()和top()操作；

解题思路

假设有两个栈stack1, stack2

队列push(element)实现：始终用stack1入栈实现

队列pop()和top()实现：由于stack1依次出栈并压入stack2中，恰好保证stack2中顺序与模拟队列顺序一致，始终保证stack2栈顶元素为模拟队列队首

当stack2为空时，stack1中全部元素依次出栈并入栈stack2，最后直接弹出栈顶或者只返回栈顶数据；

当stack2不空时，直接弹出栈顶或者只返回栈顶数据；

注意点

对空栈进行pop()和top()操作时考虑异常情况；

实现栈弃用java.util.stack，选用java.util.ArrayDeque实现；

题目链接

lintcode 40: http://www.lintcode.com/en/problem/implement-queue-by-two-stacks/

剑指offer 面试题7

Java代码

import java.util.ArrayDeque;

/**
 * 用两个栈实现一个队列
 * http://www.lintcode.com/en/problem/implement-queue-by-two-stacks/
 * @author yzwall
 */
class MyQueue {
    private ArrayDeque stack1;
    private ArrayDeque stack2;
    
    MyQueue() {
        this.stack1 = new ArrayDeque<>();
        this.stack2 = new ArrayDeque<>();
    }
    
    public void push(int element) {
        stack1.push(element);
    }
    
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int top() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }            
        }
        return stack2.peek();
    }
}

GPU云服务器云服务器两个栈 python 模拟栈 java 栈队列 java 栈队列面试

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

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

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

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

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

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

Betta 2019-08-14 18:12 评论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