题目详解
相关链接
思路
- 两个队列互相倒腾：
- pop时将队列1中的元素队列并入队到队列2，剩最后一个即pop的目标元素
- 如果pop时队列为空，则将队列2与队列1内容互换
看完代码随想录之后的想法
- 学会了只用一个队列也能实现栈
实现过程中遇到的困难
代码
一个队列实现栈
TypeScript 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/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/
class MyStack {
queue: number[]
constructor() {
this.queue = []
}
push(x: number): void {
this.queue.push(x)
}
pop(): number {
let len = this.queue.length
while (--len) this.queue.push(this.queue.shift())
return this.queue.shift()
}
top(): number {
const top = this.pop()
this.queue.push(top)
return top
}
empty(): boolean {
return !this.queue.length
}
}两个队列实现栈
TypeScript 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/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/
class MyStack {
queue1: number[]
queue2: number[]
constructor() {
this.queue1 = []
this.queue2 = []
}
push(x: number): void {
this.queue1.push(x)
}
pop(): number {
if (!this.queue1.length) [this.queue1, this.queue2] = [this.queue2, this.queue1]
while (this.queue1.length > 1) this.queue2.push(this.queue1.shift())
return this.queue1.shift()
}
top(): number {
const top = this.pop()
this.queue1.push(top)
return top
}
empty(): boolean {
return !this.queue1.length && !this.queue2.length
}
}
收获
- 学会了极致的的代码复用。本题中
top函数就完全复用了pop函数逻辑