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

思路

参考

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

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

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

实现思路

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
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()
}

测试

1
2
3
4
5
6
7
8
9
10
11
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
image-20200725134752097

分析

时间复杂度:

这里我们主要分析出队列的时间复杂度,因为入队列操作仅是一个入栈操作,时间复杂度:
$$
\mathcal{O}(1)
$$
出队列方面,因为两端出队列思想相似,所以仅分析其中一边即可。

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

空间复杂度:

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

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

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

参考博客文章:点此跳转

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
/*
* 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
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
* 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)
}
}

分析

时间复杂度:

这里所有复杂度都均摊到了每一个操作上,不会出现某些情况时间复杂度激升的情况,综合时间复杂度:
$$
\mathcal{O}(1)
$$
空间复杂度:
$$
\mathcal{O}(N)
$$

总结

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

Github

Github