- 栈是一种后入先出(LIFO,last-in-first-out)的数据结构
- 栈使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop)
- 在javascript中,栈可以看成是数组的子集
![](https://img.haomeiwen.com/i3373227/36db9c83b8fcb1a0.jpg)
1、实现
class Stack{
constructor() {
this.stack= [];
}
push(item) {
this.stack.push(item);
}
pop() {
this.stack.pop();
}
}
2、应用
数制间的相互转换
可以利用栈将一个数字从一种数制转换成另一种数制。假设想将数字 n 转换为以 b 为基数 的数字,实现转换的算法如下:
- 最高位为 n % b,将此位压入栈
- 使用 n/b 代替 n
- 重复步骤 1 和 2,直到 n 等于 0,且没有余数
- 持续将栈内元素弹出,直到栈为空,依次将这些元素排列,就得到转换后数字的字符 串形式
function mulBase(num, base) {
const s = new Stack();
do {
s.push(num % base);
num = Math.floor(num /= base);
} while (num > 0);
let converted = "";
while (s.length() > 0) {
converted += s.pop();
}
return converted;
}
括号匹配
/**
* @param {string} s
* @return {boolean}
*/
function isValid(s) {
const stack = [];
const mapping = {
')': '(',
'}': '{',
']': '['
};
for (v of s) {
if (v in mapping) {
let top_el = stack.pop();
if (top_el !== mapping[v]) {
return false;
}
} else {
stack.push(v)
}
}
return stack.length === 0;
};
网友评论