前端与数据结构和算法之栈

1940

前言

关于数据结构和算法，是前端或者说是整个技术界上技术进阶以及涨薪路上的最大难题。
不过任何难题，当你打算去细看和仔细动手实现一番时，它并没有你想象的那么难。
笔者也是正在路上的一枚小菜鸟罢了，这篇博文是自己的学习笔记，其中的内容我会以《数据结构与算法JavasCript描述》中的内容为主，会借鉴里面的一些概念。
概念的定义我凭空想是想不出来的，不过里面的实现代码可以用自己的方式实现一下，因为我看到里面的内容大多是用es5实现的，笔者更倾向于使用es6去实现。

栈的介绍（什么是栈）

栈是一种特殊的列表，栈内的元素是能通过列表的一端访问，这一端称之为栈顶。

栈的特点

栈是一种后入先出的数据结构。由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。

现实生活中的栈

洗碗时堆叠的盘子。只能从最上面取盘子，盘子洗干净后，也只能摞在这一摞盘子的最上面。

栈的操作

对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。

栈的实现

  1. 实现思路

入栈采用push方法，出栈使用pop方法。
需要一个peek方法预览栈顶元素，这个方法只返回栈顶元素而不删除它。
pop方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性的删除了。
使用top变量保存栈顶的位置，需要用length方法获取整个栈内元素的个数。
最后需要一个clear方法清除栈内所有元素。

  1. 自己实现需要满足一个特殊要求（这一点是自己加的）

需要满足设计模式中的设计原则：1. 开放封闭原则：对扩展开放，对修改封闭；2. 单一职责原则：实现类要职责单一；
实际上还有其他三个设计原则，因为js的语法限制其他三种设计原则用的不多，所以暂时就先满足这两种设计原则。
3. 具体实现

class Stack {
    constructor() {
        this.arr = [];
        this.top = 0;
    }
    // 入栈
    push(item) {
        this.arr[this.top++] = item;
    }
    // 出栈
    pop() {
        return this.arr[--this.top];
    }
    // 预览栈顶
    peek() {
        return this.arr[this.top - 1];
    }
    // 栈内元素个数
    length() {
        return this.top;
    }
    // 清空栈
    clear() {
        this.top = 0;
    }
}
复制代码
  1. 数据结构验证
const S = new Stack();
console.log(S.length()); //0
S.push("王二");
S.push("张三");
S.push("李四");
console.log(S.length()); // 3
console.log(S.peek()); // 李四
S.pop();
console.log(S.length()); // 2
console.log(S.peek()); // 张三
S.clear();
console.log(S.length()); // 0
console.log(S.peek()); // undefined
复制代码

综上所述：先进后出的数据结构基本满足，访问栈顶元素也能做到。 设计模式中的单一职责原则无论是对这个类中的方法，还是对于这整个类都适用。类里面的每一个函数都只做了一件事。

不足之处在于：未满足开放封闭原则

  1. 开放封闭原则校验：
const S = new Stack();
S.length = function() {
    return this.top - 10;
}
console.log(S.length); // ƒ () { return this.top - 10;}
// 由此打印看出原length方法被修改了，所以不满足开放封闭原则
复制代码
  1. 根据开放封闭原则进行修改：
// 对修改封闭
const S = function () {
    return new Stack();
};
S.length = function() {
    return this.top - 10;
}
console.log(S().length);// ƒ length() { return this.top; }
// 对扩展开放
S.a = 10;
console.log(S.a); // 10
// 由此可见，原length方法未被修改，则满足修改封闭
复制代码
  1. 这种写法存在的问题：

一般请情况下我们只关注它的数据结构是否满足先进先出的特点，不会去关注内部的值。但是因为我想看一下每个方法执行的情况，我就获取了一次arr的具体值，让我没想到的是，arr中的具体值根据这个写法，就算是出栈了，元素还在里面，原因是只改变了top的值，数组是没有任何改变的。给大家看一下打印结果就知道了

    class Stack {
        constructor() {
        	this.arr = [];
        	this.top = 0;
        }
        // 入栈
        push(item) {
            this.arr[this.top++] = item;
        }
        // 出栈
        pop() {
        	return this.arr[--this.top];
        }
        // 预览栈顶
        peek() {
        	return this.arr[this.top - 1];
        }
        // 栈内元素个数
        length() {
        	return this.top;
        }
        // 清空栈
        clear() {
        	this.top = 0;
        }
        // 获取栈内所有元素
        getStack() {
        	return this.arr;
        }
    }
    const S = new Stack();
    console.log(S.length());
    S.push("王二");
    S.push("张三");
    S.push("李四");
    console.log(S.length());
    console.log(S.peek());
    S.pop();
    console.log(S.length());
    console.log(S.peek());
    S.clear();
    console.log(S.length());
    console.log(S.peek());
    console.log(S.getStack()); //  ["王二", "张三", "李四"]
复制代码

8.方法的改写：

    class Stack {
    	constructor() {
    		this.arr = [];
    	}
    	push(item) {
    		this.arr.push(item);
    	}
    	pop() {
    		return this.arr.pop();
    	}
    	peek() {
    		return this.arr[this.arr.length - 1];
    	}
    	length() {
    		return this.arr.length;
    	}
    	clear() {
    		this.arr = [];
    	}
        getStack() {
        	return this.arr;
        }
    }
    const S = new Stack();
    console.log(S.length()); // 0
    S.push("王二");
    S.push("张三");
    S.push("李四");
    console.log(S.length()); //3
    console.log(S.peek()); // 李四
    S.pop();
    console.log(S.length()); // 2
    console.log(S.peek());
    S.clear();
    console.log(S.length()); // 张三
    console.log(S.peek()); // 0
    console.log(S.getStack()); // []
复制代码

注：一般情况下我们是不会关注栈内所有元素的具体情况的，只是后一种方法更严谨一些罢了。而且第二种写法是来自自己对第一种写法存在问题的思考自己写出来的，未来自任何视频或者书籍。

  1. 为什么使用pop移除元素，而不使用delete？
    class Stack {
    	constructor() {
    		this.arr = [];
    	}
    	push(item) {
    		this.arr.push(item);
    	}
    	del() {
    		delete this.arr[this.arr.length-1];
    	}
    	peek() {
    		return this.arr[this.arr.length - 1];
    	}
    	length() {
    		return this.arr.length;
    	}
    	clear() {
    		this.arr = [];
    	}
        getStack() {
        	return this.arr;
        }
    }
    const S = new Stack();
    S.push("张三");
    S.del();
    console.log(S.getStack()); //[empty]
复制代码
  1. delete会删除当前数组位置的值，但是会留下一个空位，也就是数组的长度不会发生改变，会留下empty这个空位，类似于占位符。
  2. 这个方法还需要返回被删除的值，这个delete也满足不了要求

应用场景（栈能解决什么问题）？

  1. 数字的进制转换：

概念补充：一般情况下用一个数去除以需要转换的进制，将其余数倒序输出及时对应进制的表示。如下是示意图：

进制转换.png

用栈解决该问题的思路，将数字与进制进行相除，其余数先依次进栈，然后再将栈内元素依次出栈，即可得到正确结果。解决方法如下：

    // 适用于2-9进制
    // num 为数值
    // base 为进制
    function mulBase(num, base) {
    	do {
            S.push(num % base);
            num = Math.floor(num / base); 
    	} while(num > 0);
    	let str = '';
    	while (S.length() > 0) {
            str += S.pop();
    	}
    	return +str;
    }
    console.log(mulBase(6, 2)); // 110
复制代码

空间复杂度为O(n)，时间复杂度为O(n)

  1. 阶乘

什么叫阶乘？

10! = 10*9*8*7*6*5*4*3*2*1 //这是10的阶乘，简单吧，看一眼就懂就不解释了
复制代码

用递归实现

function fn(n) {
    if(n === 0) {
        return 1;
    } else {
        return n * fn(n - 1);
    }
}
console.log(fn(3)); // 6 => 3*2*1
复制代码

es6中的实现：

function fn(n) {
    let num = n;
    for(let i = n - 1; i > 0; i--) {
            num *= i;
    }
    return num;
}
console.log(fn(3)); // 6 => 3*2*1
复制代码

注：由于js的数值计算的精度限制，70及以上的阶乘便无法计算，但是es6中有大整数可以解决这个问题，位数没有任何限制。在此提一下，详情可以看我在掘金的es6博客。在此不细讲。

用栈来实现：

function fn(n) {
    const S = new Stack();
    for(let i = 1; i <= n; i++) {
        S.push(i);
    }
    let num = 1;
    let len = S.length();
    for(let i = 0; i < len; i++) {
        num *= S.pop();
    }
    return num;
}
console.log(fn(3)); // 6 => 3*2*1
复制代码

空间复杂度为O(n),时间复杂度为O（n）

  1. 回文：

回文的定义：一串文字，不管是从左往右读，还是从右往左读都一模一样。

用栈的解决思路：文字依次进栈，再依次弹出栈，出栈后的文字串起来刚好与原文字相反！

const str = "风扇能扇风";
function isPalindrome(str) {
        const S = new Stack();
        for(let i = 0; i < str.length; i++) {
                S.push(str[i]);
        }
        let newStr = '';
        let len = S.length();
        for(let i = 0; i < len; i++) {
                newStr += S.pop();
        }
        return newStr == str;
}
console.log(isPalindrome(str)); // true;
复制代码

空间复杂度为O(n),时间复杂度为O（n）
4. 括号匹配校验
思路：遇见左括号进栈，出栈的右括号需要跟栈顶括号进行匹配，如果匹配则弹出栈，最后栈空了即为true。

function isMatching(str) {
    const S = new Stack();
    for(let i = 0; i < str.length; i++) {
            const c = str[i];
            if(c == '(' || c == '[' || c == '{') {
                    S.push(c);
            }
            // 此处采用暴力枚举
            if(
                    (c == ')' && S.peek() == '(') || 
                    (c == ']' && S.peek() == '[') || 
                    (c == '}' && S.peek() == '{')
            ) {
                    S.pop();
            }
    }
    return S.length() == 0;
}
console.log(isMatching('{[]}'));
复制代码

空间复杂度为O(n),时间复杂度为O（n）

注：最后提一句，js的函数调用就用的是函数调用栈，最后调用的函数最先执行。

时间空间复杂度：

  1. 时间复杂度：

用来定性描述算法的运行时间

表示方法：

一个函数，用大O表示，如O(1)、O(n)、O（logN）…

O(1): 永远只执行一次

let i = 1;
i +=1 ;
复制代码

O(n)：某一部分里面的代码执行了n次

for(let i = 0; i < n; i++) {
    console.log(i);
}
复制代码

O(1) + O(n) = O(n):先后排列进行相加，取增长趋势更快的

let i = 1;
i +=1 ;
for(let j = 0; j < n; j++) {
    console.log(j);
}
复制代码

O(n) * O(n) = O(n^2):嵌套用乘法，正常相乘

for(let i = 0; i < n; i++) {
    for(let j = 0; j < n; j++) {
        console.log(j);
    }
}
复制代码

O(logN):

let i = 1;
while(i < n) {
    console.log(i);
    i *= 2;
}
复制代码
  1. 空间复杂度：

用来描述算法在运行过程中临时占用存储空间大小的量度。

表示方法：

一个函数，用大O表示，如O(1)、O(n)、O（n^2）…

O(1): 单个变量占用的内存永远是1

let i = 1;
i +=1 ;
复制代码

O(n): 给数组中push了n个值，占用了n个内存单元

const arr = [];
for(let i = 0; i < n; i++) {
    arr.push(i);
}
复制代码

O(n^2): 二维数组，存储了n的2次方个变量

const arr = [];
for(let i = 0; i < n; i++) {
    arr.push([]);
    for(let j = 0; j < n; j++) {
        arr[i].push(j);
    }
}
复制代码

参考：

《数据结构与算法JavasCript描述》—— [美]麦克米伦

后记：

时间复杂度和空间复杂度这块儿看的视频，但我的判断可能不是特别准确，如有错误还望各位大佬批评指正。我只是一个在学习路上的小菜鸡，不是什么大佬。

© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
前端
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4202
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3895
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3842
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3406
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
相关推荐
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3135
手摸手教你实现vue的动态路由（addRoute版）-一一网
手摸手教你实现vue的动态路由（addRoute版）
手摸手教你实现vue的动态路由（addRoute版）
4年前 3118
Unity实用功能之使用TextMeshPro组件-一一网
Unity实用功能之使用TextMeshPro组件
Unity实用功能之使用TextMeshPro组件
4年前 3062
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …-一一网
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …...
4年前 2847
Windi CSS 在 Vue3 + Vite 项目中的使用-一一网
Windi CSS 在 Vue3 + Vite 项目中的使用
Windi CSS 在 Vue3 + Vite 项目中的使用
3年前 2728
vue3 使用 qrcode.vue 生成二维码-一一网
vue3 使用 qrcode.vue 生成二维码
vue3 使用 qrcode.vue 生成二维码
4年前 2621
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云