编辑
2020-07-24
algorithm4
00
请注意,本文编写于 1370 天前,最后修改于 477 天前,其中某些信息可能已经过时。

目录

思路
参考
实现思路
三个栈实现双向队列(虚假的$\mathcal{O}(1)$)
测试
分析
六个栈实现单向队列(真正的$\mathcal{O}(1)$)
测试
分析
总结
Github

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

思路

参考

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

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

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

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

实现思路

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

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

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

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

三个栈实现双向队列(虚假的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())

image-20200725134752097

分析

时间复杂度:

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

O(1)\mathcal{O}(1)

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

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

O(N/N)=O(1)\mathcal{O}(N/N)\\\\ = \mathcal{O}(1)

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

空间复杂度:

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

O(N)\mathcal{O}(N)

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

因为双向会更加绕,所以这里选用单项队列进行讲解,主要方向是右进左出。当然,这里的思想跟上面的有些许不同,三个栈的情况是存在单次操作O(N)\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) } }

分析

时间复杂度:

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

O(1)\mathcal{O}(1)

空间复杂度:

O(N)\mathcal{O}(N)

总结

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

Github

Github

如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:xmmmmmovo

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 许可协议。转载请注明出处!