算法练习(80): 两个栈实现的队列(1.4.27)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 两个栈实现的队列

题目

1.4.27 两个栈实现的队列。用两个栈实现一个队列，使得每个队列操作所需要的堆栈操作均摊后为一个常数。提示：如果将所有元素压入栈再弹出，它们的顺序就被颠倒了。如果再次重复这个过程，它们的顺序则会复原。

---

1.4.27 Queue with two stacks. Implement a queue with two stacks so that each queue operation takes a constant amortized number of stack operations. Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they’re now back in order.

分析

这道题要写出来不难，但要符合“均摊后是一个常数”比较复杂。下面我们演示一下优化过程。
首先，我们使用两个栈，暂且命名为stack1和stack2，我们可以这么操作：stack1用于存储数据，stack2用于缓存。因此不难得出如下代码：

public class QueueWithTowStacks<T> {
    private Stack<T> stack1 ;
    private Stack<T> stack2 ;

    public QueueWithTowStacks(){
        stack1 = new Stack<T>();
        stack2 = new Stack<T>();
    }

    public void enqueue(T item){
        stack1.push(item);
    }

    public T dequeue(){
        if (stack1.size() < 1 && stack2.size() < 1)
        {
            System.out.println("Queue is empty");
            return null;
        }
        //把stack1清空
        while (stack1.size() > 1){
           T element = stack1.pop();
           stack2.push(element);
        }
        T ele = stack1.pop();
        //把stack2 清空
        while (stack2.size() > 0){
            T element = stack2.pop();
            stack1.push(element);
        }
        return ele;
    }

    public static void main(String[] args){
        QueueWithTowStacks gfg = new QueueWithTowStacks();
        gfg.enqueue("我的");
        gfg.enqueue("名字");
        gfg.enqueue("叫");
        gfg.enqueue("顶级程序员不穿女装");
        gfg.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
        System.out.print(gfg.dequeue());
        System.out.print(gfg.dequeue());
        System.out.print(gfg.dequeue());
        System.out.print(gfg.dequeue());
        System.out.print(gfg.dequeue());
    }
}

以上代码在这里可以找到：QueueWithTowStacks.java

关于栈（Stack）的实现，如果大家还有疑问的，可以查看我之前的博客：算法练习(26):Stack概念(1.3.1-1.3.2)，里面给出了栈的具体实现。

我们可以发现，每次enqueue是常数级别的，但每次dequeue就比较复杂，需要遍历两个stack，假设Queue的总长度为N，那么每次dequeue需要线性级别的复杂度，所以跟题目的要求显然不符合，所以我们接着优化。
其实在做这一题之前，我们可以看到书中有类似的描述，关于均摊分析的：

书中关于均摊分析的描述中，说道了动态调整数组的平均次数为常数。所以我们可以把这个思想用到这道题中：
出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。这样一来避免了反复“倒”栈，仅在需要时才“倒”一次。

答案

public class QueueWithTwoStacksFaster<T> {
    private Stack<T> stack1 ;
    private Stack<T> stack2 ;

    public QueueWithTwoStacksFaster(){
        stack1 = new Stack<T>();
        stack2 = new Stack<T>();
    }

    public void enqueue(T item){
        stack1.push(item);
    }

    public T dequeue() throws Exception {
        if (stack1.size() < 1 && stack2.size() < 1)
        {
            throw new Exception("Queue is empty");
        }
        T ele = null;
        //Stack2为空，则将Stack1倒入Stack2
        if (stack2.size() < 1){
            while (stack1.size() > 1){
                T element = stack1.pop();
                stack2.push(element);
            }
            ele = stack1.pop();
        }else{
            ele = stack2.pop();
        }
        return ele;
    }

    public static void main(String[] args){
        QueueWithTwoStacksFaster queueWithTwoStacksFaster = new QueueWithTwoStacksFaster();
        queueWithTwoStacksFaster.enqueue("我的");
        queueWithTwoStacksFaster.enqueue("名字");
        queueWithTwoStacksFaster.enqueue("叫");
        queueWithTwoStacksFaster.enqueue("顶级程序员不穿女装");
        queueWithTwoStacksFaster.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
        try {
            System.out.print(queueWithTwoStacksFaster.dequeue());
            System.out.print(queueWithTwoStacksFaster.dequeue());
            System.out.print(queueWithTwoStacksFaster.dequeue());
            System.out.print(queueWithTwoStacksFaster.dequeue());
            System.out.print(queueWithTwoStacksFaster.dequeue());
        } catch (Exception e) {
            e.printStackTrace();
        }

    }
}

代码索引

QueueWithTwoStacksFaster.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。