常用数据结构《二》· 栈
栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据,也就是说,先插入的数据将被压入栈底,最后插入的数据在栈顶,读出数据时,从栈顶开始逐个读出。栈在汇编语言程序中,经常用于重要数据的现场保护。栈中没有数据时,称为空栈。
刘亚东;曲心慧编.C/C++常用算法手册:中国铁道出版社,2017.09
JavaScript实现栈结构
//@ 利用数组方法特性,根据栈只能在某一端添加或删除数据也就是先进后出原则实现栈
class Stack {
constructor() {
this.stack = [];
}
//* 数据进栈
push(item) {
this.stack.push(item);
}
//* 数据出栈
pop() {
this.stack.pop();
}
//* 返回栈尾数据
peek() {
return this.stack[this.getCount() - 1];
}
//* 返回栈的长度
getCount() {
return this.stack.length;
}
//* 是否为空栈
isEmpty() {
return this.getCount() === 0;
}
}
栈的应用·括号匹配
//@ 栈的应用--括号匹配
var isValid = function (s) {
let map = {
'(': -1,
')': 1,
'[': -2,
']': 2,
'{': -3,
'}': 3
};
//* 利用数组模拟栈结构
let stack = [];
//* 去除字符串中的字母和特殊字符后的数组
let arr = []
//* 去掉无用符号,利用正则表达式
let newStr = s.replace(/\t|\r|\n|\s|\f|\"|\u|\*|\\|\$/ig, "");
//* 删除字符串内的字母
for (const i of newStr) {
if (i < 'a' || i > 'z') {
arr.push(i);
}
}
s = arr;
//* 根据map将括号进行匹配,匹配成功进栈,失败出栈并返回false
for (let i = 0; i < s.length; i++) {
if (map[s[i]] < 0) {
stack.push(s[i]);
} else {
let last = stack.pop();
if (map[last] + map[s[i]] != 0) {
return false;
}
}
}
//* 站内还有未匹配的括号则返回 false
if (stack.length > 0) {
return false;
}
return true;
};
//@ 测试
console.log(isValid('[(dgy{$dg***}h**f)]')); // true
console.log(isValid('[(dgy{$dg**}hf])]')); // false