美文网首页
两个栈实现队列

两个栈实现队列

作者: 越长越圆 | 来源:发表于2016-10-27 17:32 被阅读16次

两个栈实现队列

查看文章:http://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html

enter image description here
有三种思路:
  1. s1是入栈的,s2是出栈的。

    • 入队列时:如果s1为空,把s2中所有的元素倒出压到s1中;否则直接压入s1
    • 出队列时:如果s2不为空,把s2中的栈顶元素直接弹出;否则,把s1的所有元素全部弹出压入s2中,再弹出s2的栈顶元素
  2. s1是入栈的,s2是出栈的。保证所有元素都在一个栈里面

    • 入队列时:如果s1为空,把s2中所有的元素倒出压到s1中;否则直接压入s1
    • 出队列时:如果s2不为空,把s2中的栈顶元素直接弹出;否则,把s1的所有元素全部弹出压入s2中,再弹出s2的栈顶元素
  3. s1是入栈的,s2是出栈的

    • 入队列:直接压入s1即可
    • 出队列:如果s2不为空,把s2中的栈顶元素直接弹出;否则,把s1的所有元素全部弹出压入s2中,再弹出s2的栈顶元素

最优解是第三种方式

public class sQueue<T> {
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();

    public void appendTrail(T append) {
        s1.push(append);
    }

    public T deleteHead(Stack<T> s) {
        if (s2 == null) {
            while (s1.size() > 0) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
}

相关文章

  • 栈和队列

    两个栈实现队列 两个队列实现栈

  • 栈&队列

    一、栈&队列总结 栈/队列的应用接雨水验证栈序列滑动窗口的最大值 栈/队列的特殊实现用两个栈实现队列用两个队列实现...

  • 队列、栈

    两个队列实现一个栈 两个栈实现一个队列

  • 面试题9: 用两个栈实现队列

    9-1 用两个栈实现队列 9-2 用两个队列实现栈

  • 手撕栈队列

    【面试题07:用两个栈实现队列】 题目:利用两个栈实现队列的插入,取队首,判断非空等函数。拓展:用两个队列实现栈,...

  • 用两个栈实现队列,用两个队列实现堆栈

    参考:剑指Offer面试题7(Java版):用两个栈实现队列与用两个队列实现栈 用两个栈实现队列stack1作为入...

  • 栈和队列的相互实现

    两个栈实现队列: 一个栈用来入,一个栈用来出 两个队列实现栈: 入栈的时候正常存入一个队列,出栈的时候用另一个队列...

  • Swift-两个栈实现队列

    题目:两个栈实现队列,栈是先入后出,队列是先入先出,两个栈可以利用这个特点实现队列. 核心代码: `class ...

  • LeetCode 每日一题 [43] 用两个栈实现队列

    LeetCode 用两个栈实现队列 [简单] 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appen...

  • 剑指Offer

    09 用两个栈实现队列 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 del...

网友评论

      本文标题:两个栈实现队列

      本文链接:https://www.haomeiwen.com/subject/lslsuttx.html