JavaScript 栈
栈是一种遵从先进后出(LIFO)原则的有序集合。
新添加或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。
在栈里,新元素都靠近栈顶,旧元素都接近栈底
昨天因为有点事没有更新,今天打算给大家讲讲 JavaScript 实现的数据结构
数据结构与算法是程序语言的灵魂,是解决一切编程问题的基础
以前学 C/C++ 的时候,感觉算法还是非常重要的,但是前端涉及的并不多
不管怎样,作为技术人员,理解一些基本数据结构和算法应该是必须的
而且我们的 JavaScript 实现数据结构和算法更加容易
下面我们就先来看看其中一个最基本的
栈的理解
栈这种数据结构其实很好理解
可以把它想象成一个刚好能容下书大小的小箱子
推栈 / 压栈就是把一本书书放在箱子中,但是只能放在箱子的最上面
弹栈 / 出栈就是从箱子中拿出一本书
栈顶是箱子中最顶上的书
栈底是箱子中对低下的书
生活中栈的例子比比皆是,比如堆放盘子,子弹夹推子弹等等
这可以帮助我们更好的理解栈
栈也被用在我们编程语言的编译器和内存中保存变量、方法调用等等
栈的创建
那么现在我们来用 JavaScript 实现一个栈
首先我们需要考虑一种数据结构来保存栈元素,毫无疑问数组是合适的选择
然后我们要实现栈的功能,同样以装书为例
毫无疑问如果箱子里有很多书我们不能直接把箱子低下的书拿出来 所以我们不能直接操作栈底
也许我们有很多这样的箱子,有很多栈 ,所以我们最好把它声明为一个 "类",完整代码如下
- function Stack() {
- var items = [];
- this.push = function(ele) {
- items.push(ele);
- }; //推栈
- this.pop = function() {
- return items.pop();
- }; //弹栈
- this.peek = function() {
- return items[items.length - 1];
- }; //查看栈顶元素
- this.isEmpty = function() {
- return items.length === 0;
- }; //判断栈是否为空
- this.size = function() {
- return items.length;
- }; //栈大小
- this.clear = function() {
- items = [];
- }; //清空栈
- this.print = function() {
- console.log(items.toString());
- }; //打印栈
- }
- var stack = new Stack(); //声明栈的实例
栈的应用
下面我们就用栈解决一些问题
比如把十进制转化为二进制
要把十进制转化为二进制,可以把这个数字和 2 整除,直到 0 为止
比如把 50 转化为二进制就是 10010
下面是算法实现
- function convertBinary(decNum) { //十进制转换为二进制
- var remStack = new Stack(),
- rem,
- binaryStr = '';
- while (decNum) {
- rem = Math.floor(decNum % 2);
- decNum = Math.floor(decNum / 2);
- remStack.push(rem); //余数放到栈中
- }
- while (!remStack.isEmpty()) {
- binaryStr += remStack.pop(); //利用pop把栈内元素逐一弹出,将余数拼接成为一个字符串
- }
- return binaryStr;
- }
- console.log(convertBinary(50)); //输出10010
还可以修改这个算法,让这个函数能够把十进制转化为任何进制
- function baseConverter(decNum, base) { //十进制转换为任意进制
- var base = (base >= 2 && base <= 16) ? base : 10,
- remStack = new Stack(),
- rem,
- baseStr = '',
- digits = '0123456789ABCDEF';
- while(decNum) {
- rem = Math.floor(decNum % base);
- decNum = Math.floor(decNum / base);
- remStack.push(rem); //余数放到栈中
- }
- while(!remStack.isEmpty()) {
- baseStr += digits[remStack.pop()]; //利用pop把栈内元素逐一弹出,将余数拼接成为一个字符串
- }
- return baseStr;
- }
其实用数组也可以实现,为了练习一下栈,就用栈来实现这个算法
通过这个小应用我们可以简单理解栈
来源: