备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

为什么我要放弃javaScript数据结构与算法（第三章）—— 栈

2018-11-01 1162
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 有两种结构类似于数组，但在添加和删除元素时更加可控，它们就是栈和队列。第三章 栈栈数据结构栈是一种遵循后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称为栈顶，另一端就叫做栈底。

有两种结构类似于数组，但在添加和删除元素时更加可控，它们就是栈和队列。

第三章 栈

栈数据结构

栈是一种遵循后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，称为栈顶，另一端就叫做栈底。在栈里， 新元素都靠近栈顶，旧元素都接近栈底。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等。

创建栈

  1. 先声明这个类
   function Stack(){
       // 各种属性和方法的声明
   }
  1. 选择数组这种数据结构来保存栈里的元素
   let items = [];

  1. 为栈声明一些方法

    • push（element（s））： 添加一个（或者几个）新元素到栈顶
    • pop（）：移除栈顶的元素，同时返回被移除的元素
    • peek（）：返回栈顶的元素，不会对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）
    • isEmpty（）：如果栈里没有任何元素的就返回true，否则就返回false.
    • clear（）：移除栈里的所有元素
    • size（）：返回栈里的元素个数，这个方法和数组的length属性很类似。

向栈添加元素

我们要实现的第一个方法是 push,这个方法负责向栈里添加新元素，该方法只添加元素到栈顶，也就是栈的末尾。

this.push = function(element){
    return items.push(element);
}

只能用 push 和 pop 方法添加和删除栈中元素，这样一来，我们的栈就自然遵从了 LIFO 原则。

向栈移除元素

我们要实现的第一个方法是 pop,这个方法主要用来移除栈里的元素。栈遵从 LIFO 原则，因此移出的是最后添加进去的元素。栈的 pop 方法可以这么写

this.pop = function(){
    return items.pop();
}

只能用 push 和 pop 方法添加和删除栈中元素，这样一来，我们的栈就自然遵从了 LIFO 原则。

查看栈顶元素

现在为类实现一些额外的辅助方法，如果想知道栈里最后添加的元素是什么，可以用 peek 方法，这个方法将返回栈顶的元素。

this.peek = function(){
    return items[items.length-1];
}

因为类内部是用数组保存元素的，所以访问数组的最后一个元素可以用 length - 1

检查栈是否为空

isEmpty ,如果栈为空的话就返回true，否则就返回false

this.isEmpty = function(){
    return items.length == 0;
}

类似于数组的 length 属性，我们也能实现栈的 length,对于集合，最好用 size 代替 length。因为栈的内部使用数组保存元素，所以能简单地返回栈的长度。

this.size = function(){
    return items.length;
}

清空和打印栈元素

实现 clear 方法。clear 方法用来移除栈里所有的元素，把栈清空。实现这个方法最简单的方式是

this.clear = function(){
    items = [];
    return null;
}

打印出来栈里面的内容，通过实现辅助方法 print 来实现。

this.print = function(){
    console.log(items.toString());
}

实例

function Stack(){
        let items = [];
        this.push = function(element){
            return items.push(element);
        }
        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());
        }
    }
let stack = new Stack();
console.log(stack.isEmpty()); // true 判断是否为空
stack.push(5); // 往栈里添加元素 5
stack.push(8); // 往栈里添加元素 8
console.log(stack.peek()); // 查看最后一个元素 8
stack.push(11); // 往栈里添加元素 11
console.log(stack.size()); // 3 输出栈的元素个数
console.log(stack.isEmpty()); // false 判断是否为空
stack.push(15); // 往栈里添加元素 15
stack.print(); // 5,8,11,15 输出栈里的元素

下面是流程图

流程图

ECMAScript6 和 Stack 类

创建了一个可以当做类来使用的 Stack 函数。JavaScript 函数都有构造函数，可以用来模拟类的行为。我们声明一个私有的 items变量，它只能被 Stack 函数/类访问。然而，这个方法为每个类的实例都创建了一个 items 变量的副本。因此如果要创建多个 Stack实例，就不太适合。我们可以尝试用 ES6语法来声明 Stack 类。

用 ES6 声明 Stack 类

class Stack{
    constructor(){
        this.items = []; // {1}
    }
    push(elememt){
        this.items.push(element);
    }
    // 其他方法
}

只是用 ES6 的简化语法把 Stack 函数转换成 Stack 类。这种方法不能像其他语言（Java、C++、C#）一样直接在类里面声明变量，只能在类的构造函数 constructor 里声明，在类的其他函数里用 this.nameofVariable 就可以引用这个变量。

尽管代码看起来更加简洁、更漂亮，变量 items 却是公共的。ES6 类是基于原型的。虽然基于原型的类比基于函数的类更节省内存，也更适合创建多个实例，却不能够声明私有属性（变量）或方法。而且，在这种情况下，我们希望 Stack 类的用户只能访问暴露给类的方法。否则，就有可能从栈的中间移除元素（因为我们用数组来存储其值），这不是我们希望看到的。

用ES6的限定作用域 Symbol 实现类

ES6 新增了一种叫做 Symbol 的基本类型，它是不可变的，可以用作对象的属性。

let _items = Symbol(); // 声明了 Symbol 类型的变量
class Stack{
    constructor(){
        this[_items] = [] // 要访问 _items,只需把所有的 this.items都换成 this.[_items]
    }
    push(element){
        return 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[_items].toString());
    }
}

这种方法创建了一个假的私有属性，因为ES6 新增的Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性。下面是一个破坏 Stack 类的例子

let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1); 
stack.print(); // 5,8,1

很明显可以通过访问 stack[objectSymbol[0]] 得到 _items。并且 _items属性是一个数组，可以进行任意的数组操作，比如从中间删除或者是添加元素。我们操作的是栈，不应该有这种行为出现。

用ES6类的 WeakMap 实现类

有一种数据类型可确保属性是私有的，这就是 WeakMap。后面会深入探讨 Map 这种数据结构，现在只需要知道 WeakMap 可以存储键值对，其中键是对象，值可以是任意数据类型。

如果使用 WeakMap 来存储 items 变量，那么 Stack 类是这样的

const items = new WeakMap(); // 声明了一个 WeakMap 类型的变量 items
class Stack{
    constructor(){
        items.set(this, []) // 在 constructor 中，以this（Stack类自己引用）为键，把代表栈的数组存入 items
    }
    push(element){
        let s = items.get(this);
        s.push(element);
    }
    pop (){
        let s = items.get(this);
        let r = s.pop();
        return r;
    }
    peek (){
        let s = items.get(this);
        return s[s.length-1];
    }
    isEmpty (){
        let s = items.get(this);
        return s.length == 0;
    }
    size (){
        let s = items.get(this);
        let r = s.length
        return r;
    }
    clear (){
        items.set(this, [])
    }
    print (){
        let s = items.get(this);
        console.log(s.toString());
    }
}

现在 items 在 Stack 类里是真正的私有属性了，但是还有一件事要做， items 现在仍然是在 Stack 类以外声明的，因此任何谁都可以改动它。我们可以用一个闭包（外层函数）把 Stack 类包起来，这样就可以在这个函数里访问 WeakMap

let stack = (function(){
    const items = new WeakMap();
    class Stack {
        constructor(){
            items.set(this, []);
        }
        // 其他方法
    }    
    return Stack; // 当 Stack 函数里的构造函数被调用时，会返回 Stack 类的一个实例。
})()

现在，Stack 类有一个名为 items 的私有属性。然后用这种方法的话，扩展类无法继承其属性。将其与最开始用 function 实现的 Stack 类来做个比较，我们会发现一些相似之处。

事实上，尽管 ES6 引入了类的语法，我们仍然不能像在其他编程语言中一样声明私有属性或方法。有很多种方法都可以达到相同的效果，但无论是语法还是性能，这些方法都有各自的缺点和优点。

用栈解决问题

栈的实际应用非常广泛。在回溯问题中，它可以存储访问过的任务或是路径、撤销的操作。Java 和 C# 用栈来存储变量和方法调用，特别是处理递归算法时，有可能抛出一个栈溢出异常（stack overflow）

下面，学习使用栈的三个最著名的算法实例。首先是十进制转二进制的问题，以及任意进制转换的算法，然后是平衡圆括号问题，最后，会学习栈解决汉诺塔的问题。

从十进制到二进制

计算科学中，二进制非常重要，因为计算机里的所有内容都是用二进制数字表示（0和1）。没有十进制和二进制相互转化的能力，与计算机交流就很困难。要把十进制化成十进制，将该十进制数字和2整除，直到结果为0为止。

实例:数字10转为二进制的数字。

数字10转为二进制的数字

function divideBy2(decNumber){
    var remStack = new Stack(),
    rem,
    binaryString = '';
    while(decNumber > 0){
        rem = Math.floor(decNumber % 2); // 拿到被2整除的余数
        remStack.push(rem);
        decNumber = Math.floor(decNumber / 2) // 拿到被2整除的整数
    }
    while (! remStack.isEmpty()){
        binaryString += remStack.pop().toString();
    }
    return binaryString;
}

console.log(divideBy2(10)); // 1010
console.log(divideBy2(233)); // 11101001
console.log(divideBy2(100)); // 11101001

JavaScript有数字类型，但是不会区分究竟是整数还是浮点数，使用 Math.floor 让除法只返回整数部分。

进制转换算法

可以传入任意进制的基数作为参数

function baseConverter(decNumber, base){
    var remStack = new Stack(),
    rem,
    baseString = '',
    digits = '0123456789ABCDEF';
    while(decNumber > 0){
        rem = Math.floor(decNumber % base); // 拿到被base整除的余数
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base) // 拿到被base整除的整数
    }
    while (! remStack.isEmpty()){
        baseString += digits[remStack.pop()]; 
    }
    return baseString;
}
console.log(baseConverter(100345,2)); // 11000011111111001
console.log(baseConverter(100345, 8)); // 303771
console.log(baseConverter(100345, 16)); // 187F9

需要改动的地方：在将十进制转为二进制的时候，余数是0或者1，转为八进制的时候，余数为0~7，同理16进制是0~9加上A~F。所以要做个转换，通过定义 digits ，digits[remStack.pop()] 来实现转化。

小结

通过这一章，学习了栈这一数据结构的相关内容。可以用代码自己实现栈，还讲解了栈里面的相关方法。

书籍链接： 学习JavaScript数据结构与算法

文章标签：
算法
JavaScript
存储
前端开发
Java
C++
C#
编译器
关键词：
数据结构栈
算法栈
JavaScript算法
数据结构与算法栈
JavaScript数据结构
赖同学
目录
相关文章
Kevin_17
|
16天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列（二）：队列
深入理解栈和队列（二）：队列
Kevin_17
29 0
hhzz
|
1月前
|
JSON JavaScript 前端开发
解决js中Long类型数据在请求与响应过程精度丢失问题（springboot项目中）
解决js中Long类型数据在请求与响应过程精度丢失问题（springboot项目中）
hhzz
40 0
起飞的风筝
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
起飞的风筝
32 0
诡异森林。
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
诡异森林。
34 1
我是夜阑的狗
|
1月前
|
JavaScript 前端开发
JavaScript随手笔记 --- 对数据进行判断最大位数是否超过八位
JavaScript随手笔记 --- 对数据进行判断最大位数是否超过八位
我是夜阑的狗
24 1
鲜于言悠
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈，作为一种后进先出（LIFO）的数据结构，在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而，如果我们跳出传统思维的束缚，会发现栈的用途远不止于此。
鲜于言悠
58 0
GOTXX
|
1月前
|
C语言
数据结构之栈详解（C语言手撕）
数据结构之栈详解（C语言手撕）
GOTXX
35 1
时雨h
|
9天前
|
存储 算法 调度
数据结构期末复习（3）栈和队列
数据结构期末复习（3）栈和队列
时雨h
17 0
java开发-郭老师
|
16天前
|
JavaScript 前端开发
EasyUi js 加载数据表格DataGrid
EasyUi js 加载数据表格DataGrid
java开发-郭老师
15 0
阿森要自信
|
21天前
|
存储 缓存 算法
【算法与数据结构】栈的实现详解
【算法与数据结构】栈的实现详解
阿森要自信
18 0

热门文章

最新文章

  • 1
    数据结构期末复习（fengkao课堂）
  • 2
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 3
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 4
    【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
  • 5
    【C/C++ 数据结构 线性表】深入理解与实现栈：从基础到应用的全面探索
  • 6
    数据结构-概念版（七）
  • 7
    python学习-函数模块，数据结构，字符串和列表（下）
  • 8
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
  • 9
    数据结构：顺序表详解
  • 10
    【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）（二）
  • 1
    二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
    7
  • 2
    【数据结构与算法】归并排序（详解：递归与非递归的归并排序 | 赠：冒泡排序和选择排序）
    23
  • 3
    【数据结构与算法】快速排序（详解：快排的Hoare原版，挖坑法和双指针法|避免快排最坏时间复杂度的两种解决方案|小区间优化|非递归的快排）
    23
  • 4
    【数据结构与算法】直接插入排序和希尔排序
    19
  • 5
    数据结构与算法 经典排序方法（Python）
    24
  • 6
    数据结构与算法：链式二叉树
    31
  • 7
    数据结构与算法：单链表
    19
  • 8
    数据结构与算法：复杂度
    31
  • 9
    Java数据结构与算法-java数据结构与算法（五）
    48
  • 10
    Java数据结构与算法-java数据结构与算法（二）
    82

    • 相关课程

    更多
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • JavaScript入门与实战
  • JavaScript 自学手册文档教程
  • 神经网络概览及算法详解
  • PHP进阶教程 - 由浅入深掌握面向对象开发 - 第二阶段

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • Html5和Webpack2：Webpack5打包JS和样式表
  • TLS1.3的后量子算法集成
  • RSA非对称加密算法
  • 使用Java面向对象编写网络通信程序应用
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）