第一次看见的前面就标有极难的题目

思路

参考

本问题其实是有一篇论文作为参考的:

{% pdf https://ecommons.cornell.edu/bitstream/handle/1813/6273/80-433.pdf %}

这篇论文是以LISP作为实现语言的，我们本次依旧是使用kotlin进行实现。

当然，这里三个栈需要实现的是双向队列的API，六个栈实现的是单向队列。

实现思路

首先，先要说明一个事情——其实栈的实现大多数都是利用顺序表来进行实现的，但是根据算法第四版里面的实现方案，栈其实是利用链表来实现的，虽然不影响后面复杂度分析，但是底层区别首先在这里说清楚。

然而，队列的实现有着顺序表和链表两种解决方案，用顺序表虽然出队列也依旧是$\mathcal{O}(1)$的效率，但是随着标志位的后移，需要的空间会线性增长，但是如果不后移则会变成$\mathcal{O}(N)$的复杂度，所以衍生出了循环队列的中间方案。不过Java源码中，给出了一个非常巧妙的方案，它将Queue和Deque作为一个接口，让其他数据结构实现这个接口，这样无论是链表还是线性表，只要实现了这个接口，就可以作为队列来使用。

言归正传，回到这个问题，要分析多个栈实现队列，我们首先分析双栈情况，就是左右横跳，用另一个栈作为中间栈，每一次出队列先把所有的元素移动到另一个栈中再出栈，这样出栈时间复杂度$\mathcal{O}(N)$，入栈直接压入原栈，时间复杂度$\mathcal{O}(1)$，但如果我们再利用多个栈进行模拟，就可以把所有操作压缩到$\mathcal{O}(1)$的时间复杂度了。

根据算法第四版的题目描述，设定的是利用3个栈进行实现，但是这是均摊时间复杂度之后达到的$\mathcal{O}(1)$，不是真$\mathcal{O}(1)$，所以本文章又给出了第二种利用六个栈实现的方案。

三个栈实现双向队列(虚假的$\mathcal{O}(1)$)

主要实现Deque的几个方法，具体代码解释已经写到注释里面了，所以直接放代码了：

kotlin
package ds

/*
 * 使用三个栈实现队列
 * 使得所有操作都是O(1)
 *  @Author xmmmmmovo
 *  @Version 1.0
 **/
class StackDeque<T> {
    // 左栈
    private val lst = Stack<T>()

    // 右栈
    private val rst = Stack<T>()

    // 中间栈
    private val tst = Stack<T>()

    // 表示存储的栈位置
    private var tmpIsRight = false


    fun isEmpty(): Boolean =
            lst.isEmpty() && rst.isEmpty() && tst.isEmpty()

    /**
     * 入左队列
     * */
    fun pushLeft(element: T) {
        lst.push(element)
    }

    /**
     * 入右队列
     * */
    fun pushRight(element: T) {
        rst.push(element)
    }

    /**
     * 出左队列(对应的是入右队列
     * */
    fun popLeft(): T {
        return when {
            /*
            * 这里如果左栈有值的话就说明要么左边插入值了
            * 要么右边或者中转栈转移到了左栈，无论哪种情况都是栈顶就是最左
            * 直接出栈就可以
            * */
            lst.isNotEmpty() -> lst.pop()
            /**
             * 这里先判断中转栈内容是否是存的右栈的内容
             * 判断如果是右栈的内容，再判断中转栈是否是空的
             * 如果不是就说明右栈已经转移到中转栈中了
             * 相当于移动到了左栈，所以直接弹出中转栈
             * */
            tst.isNotEmpty() && tmpIsRight -> tst.pop()
            /**
             * 这里先判断中转栈内容是否是存的右栈的内容
             * 判断如果不是右栈的内容，再判断中转栈是否是空的
             * 如果不是就说明是左栈移动到了中栈了
             * 相当于移动到了右栈，所以先弹出到左栈再弹出左栈
             * */
            tst.isNotEmpty() && !tmpIsRight -> {
                while (tst.isNotEmpty())
                    lst.push(tst.pop())
                lst.pop()
            }
            /**
             * 这里如果是中转栈是空的并且右栈不为空
             * 就直接转移到中转栈再弹出中转栈
             * */
            tst.isEmpty() && rst.isNotEmpty() -> {
                while (rst.isNotEmpty())
                    tst.push(rst.pop())
                tmpIsRight = true // 存的是右栈
                tst.pop()
            }
            /**
             * 所有栈都没有内容，自然就抛出异常
             * */
            else -> throw NoSuchElementException("Stack underflow")
        }
    }

    /**
     * 出右队列(对应的是出左队列
     * */
    fun popRight(): T {
        return when {
            rst.isNotEmpty() -> rst.pop()
            tst.isNotEmpty() && !tmpIsRight -> tst.pop()
            tst.isNotEmpty() && tmpIsRight -> {
                while (!tst.isEmpty())
                    rst.push(tst.pop())
                rst.pop()
            }
            tst.isEmpty() && lst.isNotEmpty() -> {
                while (lst.isNotEmpty())
                    tst.push(lst.pop())
                tmpIsRight = false // 存的是左栈
                tst.pop()
            }
            else -> throw NoSuchElementException("Stack underflow")
        }
    }

    val size: Int
        get() = lst.size + rst.size + tst.size

    fun asList(): List<T> {
        val list = mutableListOf<T>()
        lst.forEach {
            list.add(it)
        }
        // 如果非空那就得判断tmp里面存储的是左还是右了
        // 但是右栈一定要翻转
        tst.run {
            if (tmpIsRight) this else reversed()
        }.forEach { list.add(it) }
        rst.reversed().forEach {
            list.add(it)
        }
        return list
    }

    override fun toString(): String = asList().toString()
}

测试

kotlin
val sq = StackDeque<String>()
sq.pushLeft("a")
sq.pushLeft("b")
sq.pushLeft("c")
sq.pushLeft("d")
sq.pushLeft("e")
println(sq.popRight())
sq.pushRight("f")
sq.pushRight("g")
sq.pushRight("h")
println(sq.asList())

分析

时间复杂度：

这里我们主要分析出队列的时间复杂度，因为入队列操作仅是一个入栈操作，时间复杂度：

出队列方面，因为两端出队列思想相似，所以仅分析其中一边即可。

可以看到，首先先说明一下，队列是先进先出的，所以是右进左出，左进右出，选择右进左出分析，可以看到出方向首先尝试从另一边栈进行出栈操作，如果成功就是$\mathcal{O}(1)$，如果失败就继续判断中转栈是否是右栈内容，尝试从中转栈进行出栈，成功依旧是$\mathcal{O}(1)$，当中转栈是左栈或者只有右栈不为空的时候，所需要的时间复杂度才为$\mathcal{O}(N)$，所以考虑N个元素，最差情况是便是左进右出情况，因为此时才会存在移栈，此时仅在第一次出队列时时间复杂度为$\mathcal{O}(N)$。所以均摊时间复杂度下，出队列操作的时间复杂度为：

可以看到是均摊后时间复杂度才达到$\mathcal{O}(1)$，所以是虚假的$\mathcal{O}(1)$。

空间复杂度：

虽然这里用到了三个栈，但是所有需求空间加起来是等于添加的总元素的，所以空间是成线性增长的，所以空间复杂度是：

六个栈实现单向队列(真正的$\mathcal{O}(1)$)

因为双向会更加绕，所以这里选用单项队列进行讲解，主要方向是右进左出。当然，这里的思想跟上面的有些许不同，三个栈的情况是存在单次操作$\mathcal{O}(N)$的，所以在这里我们将解决这个问题。

参考博客文章：点此跳转

根据上面的思路，我们发现了整个实现的思路就是均摊，作为双向队列，如果仅用三个栈的话，中间栈只能存储一个栈，所以我们无论如何都需要有一次进行单个栈所有元素转存的方案，所以无法均摊到单个操作上(如果有四个栈可能可行)，但是本次仅用作单项队列，所以对于出栈来说只是左栈需要转存，所以可以把转存操作均摊到每一个出栈操作上来。

整体思路上是在入队列的时候便使得左右两个栈尽量相等，然后在出栈的时候再进行判断。

kotlin
/*
 * Copyright (c) 2020. xmmmmmovo
 */
package ds

/**
 * 用六个栈实现单向队列
 * @author xmmmmmovo
 * @date 2020/7/28 16:43
 * @since version-1.0
 */
class StackDequeOpt<T> {
    /**
     * 左栈
     */
    private var lst = Stack<T>()

    /**
     * 右栈
     */
    private var rst = Stack<T>()

    /**
     * 左栈替换栈 用于复制时转换
     */
    private var tlst = Stack<T>()

    /**
     * 右栈替换栈 用于复制时候入队
     */
    private var trst = Stack<T>()

    /**
     * 左翻转栈，用于保护左栈原有数据
     */
    private var lstrev = Stack<T>()

    /**
     * 用于复制过程中的出栈操作
     */
    private var hlst = Stack<T>()

    /**
     * 判断是否在复制
     */
    private var isCopying = false

    /**
     * 需要复制数量
     */
    private var needCopy = 0

    /**
     * 队列是否为空
     * @author xmmmmmovo
     * @date 2020/7/29 16:54
     * @return 返回是否为空
     * @since version-1.0
     */
    fun isEmpty(): Boolean =
        lst.isEmpty() && rst.isEmpty() && tlst.isEmpty() && trst.isEmpty() && lstrev.isEmpty()


    /**
     * 入右队列
     * @author xmmmmmovo
     * @date 2020/7/29 16:55
     * @param element 入元素
     * @since version-1.0
     */
    fun pushRight(element: T) {
        when {
            /**
             * 左栈大于右栈
             */
            !isCopying && sizeDiff > 0 -> {
                needCopy = 0
                rst.push(element)
            }
            /**
             * 左右栈相等的时候，因为不知道下一步操作
             * 所以提前准备来进行复制操作
             */
            !isCopying && sizeDiff == 0 -> {
                rst.push(element)
                isCopying = true
                hlst = lst.clone()
                oneStep()
                oneStep()
            }
            /**
             * 如果还在复制直接 入栈到中转栈
             * 因为原栈需要别的用处
             */
            isCopying -> {
                tlst.push(element)
                oneStep()
                oneStep()
            }
        }
    }


    /**
     * 出左队列
     * @author xmmmmmovo
     * @date 2020/7/29 16:55
     * @return 返回队列第一个元素
     * @throws NoSuchElementException 没有元素时抛出
     * @since version-1.0
     */
    fun popLeft(): T {
        when {
            /**
             * 如果没有在copy的时候并且左大于右则直接左栈弹出
             */
            !isCopying && sizeDiff > 0 -> {
                return lst.pop()
            }
            /**
             * 如果没有在复制并且左栈刚好等于右栈，那么就直接弹出左栈
             * 这样左栈小于右栈，进入复制状态
             */
            !isCopying && sizeDiff == 0 -> {
                val t = lst.pop()
                hlst = lst.clone()
                isCopying = true
                oneStep()
                oneStep()
                return t
            }
            /**
             * 因为复制状态下，所有左栈元素会到hlst中所以直接hlst出栈
             */
            else -> {
                val t = hlst.pop()
                needCopy--
                oneStep()
                oneStep()
                return t
            }
        }
    }

    /**
     * 预览元素
     * @author xmmmmmovo
     * @date 2020/7/29 16:56
     * @return 返回队列第一个元素
     * @throws NoSuchElementException 没有元素时抛出
     * @since version-1.0
     */
    fun peekLeft(): T = if (isCopying) hlst.peek() else lst.peek()

    /**
     * 中间操作 这里是脱离了入栈出栈操作的额外操作
     * @author xmmmmmovo
     * @date 2020/7/29 20:32
     * @since version-1.0
     */
    private fun oneStep() {
        when {
            /**
             * 正在copy的时候左右栈都不是空的，这说明需要进行交换了
             * 本次这里右栈进入左栈中转栈
             * 左栈进入左栈反转栈(用于后面直接替换
             */
            isCopying && lst.isNotEmpty() && rst.isNotEmpty() -> {
                needCopy++
                tlst.push(rst.pop())
                lstrev.push(lst.pop())
            }
            /**
             * 此状态说明此时左栈已经完成转移，右栈还有剩余
             * 把右栈的元素移动到左栈中转栈中
             */
            isCopying && lst.isEmpty() && rst.isNotEmpty() -> {
                isCopying = true
                tlst.push(rst.pop())
            }
            /**
             * 此时说明左右栈都是空栈了
             * 但是需要复制的数量大于1
             * 就说明lstrev还有剩余可以转移的元素
             * 直接转移到左中转栈用于后面计算
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy > 1 -> {
                isCopying = true
                needCopy--
                tlst.push(lstrev.pop())
            }
            /**
             * 如果左右栈都为空， 并且仅有一个需要复制的
             * 那么就直接把最后一个元素并入左栈中转栈
             * 中转栈转为主栈 就完成了一个循环
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy == 1 -> {
                isCopying = false
                needCopy--
                tlst.push(lstrev.pop())
                lst = tlst
                rst = trst
                tlst = Stack()
                trst = Stack()
                lstrev = Stack()
                hlst = Stack()
            }
            /**
             * 同上
             */
            isCopying && lst.isEmpty() && rst.isEmpty() && needCopy == 0 -> {
                isCopying = false
                lst = tlst
                rst = trst
                tlst = Stack()
                trst = Stack()
                lstrev = Stack()
                hlst = Stack()
            }
        }
    }

    /**
     * 左栈-右栈大小的差值
     * @author xmmmmmovo
     * @date 2020/7/29 20:33
     * @since version-1.0
     */
    private val sizeDiff: Int
        get() = lst.size - rst.size

    /**
     * 队列总长度
     * @author xmmmmmovo
     * @date 2020/7/29 20:33
     * @since version-1.0
     */
    val size: Int
        get() = lst.size + rst.size + tlst.size + trst.size + lstrev.size
}

测试

kotlin
/*
 * Copyright (c) 2020. xmmmmmovo
 */

package fundamental

import ds.StackDequeOpt
import org.junit.jupiter.api.*

import org.junit.jupiter.api.Assertions.*
import org.junit.platform.commons.logging.LoggerFactory

internal class StackDequeOptTest {
    private val sdo = StackDequeOpt<Int>()

    companion object {
        private val log = LoggerFactory.getLogger(StackDequeOptTest::class.java)

        @BeforeAll
        @JvmStatic
        fun before() {
            log.info { "StackDequeOptTest start" }
        }

        @AfterAll
        @JvmStatic
        fun after() {
            log.info { "StackDequeOptTest end" }
        }
    }

    @Test
    fun isEmpty() {
        assertEquals(true, sdo.isEmpty())
        sdo.pushRight(1)
        assertEquals(false, sdo.isEmpty())
        sdo.popLeft()
        assertEquals(true, sdo.isEmpty())
    }

    @Test
    fun pushRight() {
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.popLeft())
        assertEquals(2, sdo.popLeft())
        assertEquals(1, sdo.popLeft())
    }

    @Test
    fun peekLeft() {
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.peekLeft())
        sdo.popLeft()
        assertEquals(2, sdo.peekLeft())
    }

    @Test
    fun getSize() {
        assertEquals(0, sdo.size)
        sdo.pushRight(1)
        assertEquals(1, sdo.size)
        sdo.popLeft()
        assertEquals(0, sdo.size)
        sdo.pushRight(1)
        sdo.pushRight(2)
        sdo.pushRight(3)
        assertEquals(3, sdo.size)
    }
}

分析

时间复杂度：

这里所有复杂度都均摊到了每一个操作上，不会出现某些情况时间复杂度激升的情况，综合时间复杂度：

空间复杂度：

总结

关于这个题目也是众说纷纭，有的人说作者已经将题目改成了有限个栈而非三个栈，但是官方网站上却标注着使用三个栈实现，然而因为疫情原因，纸质书依旧在学校里躺着，没法证明，但就从电子版来看，作者有很大可能也没有改题。其实这个题目在stackoverflow上面也有人询问(链接)，但是大多数人都暗示了使用三个栈是不可能存在真正的$\mathcal{O}(1)$的，当然也有一些抖机灵的解法——比如某些套娃栈的邪道解法，真的是天马行空。不管怎么说，对于一道存在这么个争议的题目，也就仅是能到这里了。

Github

Github