JS数据结构及算法（一） 堆栈
2024-08-30 01:29:55
最近在看《学习JavaScript数据结构与算法》这本书，感觉自己又涨知识了 哈哈... 现在将自己看的做个总结，也是巩固理解。
栈：先进后出，新添加和待删除的元素都保存在栈顶。可以用数组的push方法入栈，pop出栈。
class Stack {
constructor () {
this.items = [];
}
push(element){
this.items.push(element);
}
pop(){
return this.items.pop();
}
peek(){
return this.items[this.items.length-1];
}
isEmpty(){
return this.items.length == 0;
}
size(){
return this.items.length;
}
clear(){
this.items = [];
}
print(){
console.log(this.toString());
}
toString(){
return this.items.toString();
}
}
栈的实际应用：二进制转十进制、十进制转换任意进制（二进制、八进制、十六进制）；平衡圆括号、汉诺塔问题
/**
* 十进制转二进制
* @param num --十进制数据
* @returns {string} 转换后的二进制数
*/
function devideBy2(num) {
let stack = new Stack();
let rem;
let binaryStr='';
while(num>0){
rem = num%2;
stack.push(rem);
num = Math.floor(num/2);
}
while (!stack.isEmpty()){
binaryStr +=stack.pop().toString();
}
return binaryStr;
} /**
* 十进制转换为任意进制
* @param num
* @param base
* @returns {string}
*/
function baseConvert(num,base) {
let stack = new Stack();
let rem;
let baseStr='';
let digit='0123456789ABCDEF'; //十六进制会转换
while(num>0){
rem = num%base;
stack.push(rem);
num = Math.floor(num/base);
}
while (!stack.isEmpty()){
baseStr +=digit[stack.pop()];
}
return baseStr;
}
检查括号是否匹配：左括号入栈，当检测到右括号时，进行出栈，看出栈的左括号与右括号是否可以配对，以此类推，直到栈为空。
/**
* 括号配对
* @param str 包含括号的字符串
* @returns {boolean|*} 配对成功返回true，失败返回false
*/
function checkSymbol(str) {
let openers = '([{',
closers = ')]}',
balanced = true,
index = 0,
tmp,
stack = new Stack(),
arr = str.split('');
while (balanced && index < arr.length) {
if (openers.indexOf(arr[index]) !== -1) {
stack.push(arr[index]); //左括号入栈
}
else {
if (stack.isEmpty()) {
balanced = false;
}
else {
tmp = stack.pop();
if (openers.indexOf(tmp) !== closers.indexOf(arr[index])) {
balanced = false;
}
} }
index++;
}
return (balanced && stack.isEmpty());
}
最新文章
- CSS 的命名和书写
- Linux 系统编程
- Help View修复
- C errors recods
- JAVA GUI学习 - JSplitPane分屏组件学习
- Linux的环境变量总结
- （翻译）使用Api分析器与Windows兼容包来编写智能的跨平台.NET Core应用
- Gradle学习之基础篇
- 关于如何通过kali linux 攻击以及破解WPA/WPA2无线加密
- .NETCore 下支持分表分库、读写分离的通用 Repository
- my.ini的路径分隔符
- vueSSR全栈(项目实战 mac)
- SQL： 某个时间段范围内，产品有价格，且求平均数
- spring cloud+.net core搭建微服务架构：服务发现（二）
- Unity Chan 3D Asset
- day30 __hash__ 计算哈希值
- spring boot(十三)小技巧
- shell实现linux回收站的功能
- 【CF891C】Envy 离线+最小生成树
- myDate97用法