题目 | 难度 |
---|---|
剑指 Offer 09. 用两个栈实现队列 | 简单 |
剑指 Offer 30. 包含min函数的栈 | 简单 |
剑指 Offer 31. 栈的压入、弹出序列 | 中等 |
# 1. 用两个栈实现队列:
题目
用两个栈实现一个队列。
队列的声明如下,请实现它的两个函数 appendTail
和 deleteHead
,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead
操作返回-1
)
思路:
pop
(尾删除)push
(尾插入)
两个栈实现队列,所以只能用push
和pop
方法。
使用A
栈来进行添加的操作,使用B
栈来进行辅助
- 添加元素时,将元素
push
进A
栈 - 删除元素时,先看
B
栈中是否有值,若有值,直接pop
栈并返回 - 若
B
栈中无值,将A
栈中元素全部pop
出,并push
进B
栈 B
栈在pop
出一个元素即可,若B
栈中无元素,返回-1
这样才能满足最先push
进A
栈的元素,在B
栈的最顶层,所以先从B
栈中pop
出,满足先入先出特性。
class CQueue {
constructor() {
this.stackA = [];
this.stackB = [];
}
appendTail(value) {
this.stackA.push(value);
}
deleteHead() {
if (this.stackB.length) {
return this.stackB.pop();
} else {
while (this.stackA.length) {
this.stackB.push(this.stackA.pop());
}
if (!this.stackB.length) {
return -1;
} else {
return this.stackB.pop();
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 2. 包含min函数的栈
题目
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min
函数在该栈中,调用 min
、push
及 pop
的时间复杂度都是 O(1)
。
思路:
pop()
:正常弹出顶部元素top()
:正常获取顶部元素push()
:每次push
的是一个对象,对象上有两个属性:val
和min
。val
就是当前元素的值,min
是当前栈中的最小值。每次push()
,相应的min
都重新计算,保证栈顶元素的min
属性,一直都是最小值。- 若栈空,
min
就是val
- 若栈不空,
min
是栈顶元素的min
属性和当前val
的较小者
- 若栈空,
getMin()
:返回栈顶元素的min
属性即可,为常数时间。
Math.min
方法用来获取给定的一组数值中的最小值,不接受数组作为参数
class MinStack {
constructor() {
this.stack = [];
}
push(value) {
this.stack.push({
val: value,
min: this.stack.length ? Math.min(value, this.min()) : value,
});
}
pop() {
this.stack.pop();
}
top() {
return this.stack[this.stack.length - 1].val;
}
min() {
//返回 数组最后一个对象里的min属性
return this.stack[this.stack.length - 1].min;
}
}
const a = new MinStack();
a.push(1);
a.push(-2);
a.push(2);
a.push(3);
a.push(-1);
console.log("栈中最小值",a.min());
console.log(a);
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
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
# 3. 栈的压入、弹出序列:
题目
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列{1,2,3,4,5}
是某栈的压栈序列,序列{4,5,3,2,1}
是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2}
就不可能是该压栈序列的弹出序列。
思路:
- 新建另一个栈,
index=0
,将pushed
数组中的数,依次推入栈 - 入栈后,
while
判断popped[index]
与新建的栈 栈顶元素是否相等 - 若相等,则弹出栈顶,
index++
- 最后判断栈是否为空
const validateStackSequences = (pushed, popped) => {
const stack = [];
let index = 0;
for (let i = 0; i < pushed.length; i++) {
stack.push(pushed[i]);
//当popped[index]===栈顶元素时
while (popped[index] !== undefined && popped[index] === stack[stack.length - 1]) {
stack.pop();
index++;
}
}
return !stack.length;
};
var pushed = [1,2,3,4,5];//进栈顺序
var popped = [4,5,3,2,1]//出栈顺序
console.log(validateStackSequences(pushed, popped));//true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
例如:
输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
1
2
2