学习数据结构和算法十分重要。首要原因是数据结构和算法可以很高效地解决常见问题,这对今后的代码质量至关重要(也包括性能,要是用了不恰当的数据结构或算法,很可能会产生性能问题)。其次,对于计算机科学,算法是最基础的概念。数组是计算机科学中最常用的数据结构,我们知道,可以在数组的任意位置上删除或添加元素。然而,有时候还需要一种在添加或删除元素时有更多控制的数据结构。有两种数据结构类似于数组,但在添加和删除元素时更为可控。它们就是栈和队列。本文将详细介绍栈
栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
在现实生活中也能发现很多栈的例子。例如,下图里的一摞书或者餐厅里堆放的盘子
栈也被用在编程语言的编译器和内存中保存变量、方法调用等
下面将创建一个类来表示栈,先声明这个类:
- function Stack() {
- //各种属性和方法的声明
- }
使用一种数据结构来保存栈里的元素。可以选择数组:
let items = [];
接下来,为栈声明一些方法
- push(element(s)):添加一个(或几个)新元素到栈顶
- pop():移除栈顶的元素,同时返回被移除的元素
- peek():返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)
- isEmpty():如果栈里没有任何元素就返回true,否则返回false
- clear():移除栈里的所有元素
- size():返回栈里的元素个数。这个方法和数组的length属性很类似
【push】
push 方法负责往栈里添加新元素,有一点很重要:该方法只添加元素到栈顶,也就是栈的末尾
因为使用了数组来保存栈里的元素,所以可以数组的 push 方法来实现
- this.push = function(element) {
- items.push(element);
- };
【pop】
接着来实现 pop 方法。这个方法主要用来移除栈里的元素。栈遵从 LIFO 原则,因此移出的是最后添加进去的元素。因此,可以用数组的 pop 方法
- this.pop = function() {
- return items.pop();
- };
只能用 push 和 pop 方法添加和删除栈中元素,这样一来,栈自然就遵从了 LIFO 原则
【peek】
现在,为类实现一些额外的辅助方法。如果想知道栈里最后添加的元素是什么,可以用 peek 方法。这个方法将返回栈顶的元素:
- this.peek = function() {
- return items[items.length - 1];
- };
因为类内部是用数组保存元素的,所以访问数组的最后一个元素可以用 length - 1
在上图中,有一个包含三个元素的栈,因此内部数组的长度就是 3。数组中最后一项的位置是 2,length - 1(3 -1)正好是 2
【isEmpty】
下面要实现的方法是 isEmpty,如果栈为空的话将返回 true,否则就返回 false:
- this.isEmpty = function() {
- return items.length == 0;
- };
使用 isEmpty 方法,能简单地判断内部数组的长度是否为 0
【size】
类似于数组的 length 属性,也能实现栈的 length。对于集合,最好用 size 代替 length。因为栈的内部使用数组保存元素,所以能简单地返回栈的长度:
- this.size = function() {
- return items.length;
- };
【clear】
最后来实现 clear 方法。clear 方法用来移除栈里所有的元素,把栈清空。实现这个方法最简单的方式是:
- this.clear = function() {
- items = [];
- };
另外也可以多次调用 pop 方法,把数组中的元素全部移除,这样也能实现 clear 方法
栈已经实现。通过一个例子来应用它,为了检查栈里的内容,我们来实现一个辅助方法,叫 print。它会把栈里的元素都输出到控制台:
- this.print = function() {
- console.log(items.toString());
- };
这样,我们就完整创建了栈!
栈的完整代码如下
- function Stack() {
- let items = [];
- this.push = function(element) {
- 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());
- };
- this.toString = function() {
- return items.toString();
- };
- }
下面来学习如何使用 Stack 类。 首先,需要初始化 Stack 类。然后,验证一下栈是否为空(输出是 true,因为还没有往栈里添加元素)
- var stack = new Stack();
- console.log(stack.isEmpty()); //输出为true
接下来,往栈里添加一些元素(可以添加任意类型的元素)
- stack.push(5);
- stack.push(8);
如果调用 peek 方法,将会输出 8,因为它是往栈里添加的最后一个元素:
- console.log(stack.peek());//输出8
再添加一个元素:
- stack.push(11);
- console.log(stack.size()); //输出3
- console.log(stack.isEmpty()); //输出false
我们往栈里添加了 11。如果调用 size 方法,输出为 3,因为栈里有三个元素(5、8 和 11)。 如果调用 isEmpty 方法,会看到输出了 false(因为栈里有三个元素,不是空栈)。最后, 我们再添加一个元素:
stack.push(
15);
下图描绘了目前为止我们对栈的操作,以及栈的当前状态:
然后,调用两次 pop 方法从栈里移除 2 个元素:
- stack.pop();
- stack.pop();
- console.log(stack.size()); //输出2
- stack.print(); //输出[5, 8]
在两次调用 pop 方法前,我们的栈里有四个元素。调用两次后,现在栈里仅剩下 5 和 8 了。下图描绘这个过程的执行:
下面来花点时间分析一下代码,看看是否能用 ES6 的新功能来改进
我们创建了一个可以当作类来使用的 Stack 函数。JS 函数都有构造函数,可以用来模拟类的行为。我们声明了一个私有的 items 变量,它只能被 Stack 函数 / 类访问。然而,这个方法为每个类的实例都创建一个 items 变量的副本。因此,如果要创建多个 Stack 实例,它就不太适合了
下面用 ES6 新语法来声明 Stack 类
- class Stack {
- constructor() {
- this.items = [];
- }
- push(element) {
- this.items.push(element);
- }
- //其他方法
- }
我们只是用 ES6 的简化语法把 Stack 函数转换成 Stack 类。这种方法不能像其他语言 (Java、C++、C#) 一样直接在类里面声明变量,只能在类的构造函数 constructor 里声明,在类的其他函数里用 this.items 就可以引用这个变量
尽管代码看起来更简洁、更漂亮,变量 items 却是公共的。ES6 的类是基于原型的,虽然基于原型的类比基于函数的类更节省内存,也更适合创建多个实例,却不能声明私有属性 (变量) 或方法。而且,在这种情况下,我们希望 Stack 类的用户只能访问暴露给类的方法。否则,就有可能从栈的中间移除元素(因为我们用数组来存储其值),这不是我们希望看到的
ES6 语法有没有其他方法来创建私有属性呢?
【Symbol】
ES6 新增了一种叫作 Symbol 的基本类型,它是不可变的,可以用作对象的属性。看看怎么用它来在 Stack 类中声明 items 属性
- let _items = Symbol(); //{1}
- class Stack {
- constructor() {
- this[_items] = []; //{2}
- }
- //Stack方法
- }
在上面的代码中,我们声明了 Symbol 类型的变量_items(行 {1}),在类的 constructor 函数中初始化它的值(行 {2})。要访问_items,只需把所有的 this.items 都换成 this[_items]
这种方法创建了一个假的私有属性,因为 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[objectSymbols[0]] 是可以得到_items 的。并且,_items 属性是一个数组,可以进行任意的数组操作,比如从中间删除或添加元素。我们操作的是栈,不应该出现这种行为
【WeakMap】
有一种数据类型可以确保属性是私有的,这就是 WeakMap。WeakMap 可以存储键值对,其中键是对象,值可以是任意数据类型。
如果用 WeakMap 来存储 items 变量,Stack 类就是这样的:
- const items = new WeakMap(); //{1}
- class Stack {
- constructor() {
- items.set(this, []); //{2}
- }
- push(element) {
- let s = items.get(this); //{3}
- s.push(element);
- }
- pop() {
- let s = items.get(this);
- let r = s.pop();
- return r;
- }
- //其他方法
- }
行 {1},声明一个 WeakMap 类型的变量 items。行{2},在 constructor 中,以 this(Stack 类自己的引用)为键,把代表栈的数组存入 items。行{3},从 WeakMap 中取出值,即以 this 为键(行{2} 设置的)从 items 中取值
现在知道,items 在 Stack 类里是真正的私有属性了,但还有一件事要做。items 现在仍然是在 Stack 类以外声明的,因此谁都可以改动它。要用一个闭包(外层函数)把 Stack 类包起来,这样就只能在这个函数里访问 WeakMap:
- let Stack = (function() {
- const items = new WeakMap();
- class Stack {
- constructor() {
- items.set(this, []);
- }
- //其他方法
- }
- return Stack; //{5}
- })();
当 Stack 函数里的构造函数被调用时,会返回 Stack 类的一个实例(行 {5})
现在,Stack 类有一个名为 items 的私有属性。虽然它很丑陋,但毕竟实现了私有属性。然而,用这种方法的话,扩展类无法继承私有属性。鱼与熊掌不可兼得
栈的完整代码如下
- let Stack3 = (function() {
- const items = new WeakMap();
- class Stack3 {
- constructor() {
- items.set(this, []);
- }
- 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() {
- return items.get(this).length == 0;
- }
- size() {
- let s = items.get(this);
- return s.length;
- }
- clear() {
- items.set(this, []);
- }
- print() {
- console.log(this.toString());
- }
- toString() {
- return items.get(this).toString();
- }
- }
- return Stack3;
- })();
把上面的代码跟最初实现的 Stack 类做个比较,我们会发现有一些相似之处:
- function Stack() {
- let items = [];
- //其他方法
- }
事实上,尽管 ES6 引入了类的语法,仍然不能像在其他编程语言中一样声明私有属性或方法。有很多种方法都可以达到相同的效果,但无论是语法还是性能,这些方法都有各自的优点和缺点
哪种方法更好?这取决于在实际项目中如何使用算法,要处理的数据量,要创建的实例个数,以及其他约束条件
栈的实际应用非常广泛。在回溯问题中,它可以存储访问过的任务或路径、撤销的操作。Java 和 C# 用栈来存储变量和方法调用,特别是处理递归算法时,有可能抛出一个栈溢出异常
下面将学习使用栈的三个最著名的算法示例。首先是十进制转二进制问题,以及任意进制转换的算法;然后是平衡圆括号问题;最后,学习如何用栈解决汉诺塔问题
【十进制转二进制】
现实生活中,我们主要使用十进制。但在计算科学中,二进制非常重要,因为计算机里的所有内容都是用二进制数字表示的(0 和 1)。没有十进制和二进制相互转化的能力,与计算机交流就很困难
要把十进制转化成二进制,我们可以将该十进制数字和 2 整除(二进制是满二进一),直到结果是 0 为止。举个例子,把十进制的数字 10 转化成二进制的数字,过程大概是这样
下面是对应的算法描述:
- function divideBy2(decNumber) {
- var remStack = new Stack(),
- rem,
- binaryString = '';
- while (decNumber > 0) { //{1}
- rem = Math.floor(decNumber % 2); //{2}
- remStack.push(rem); //{3}
- decNumber = Math.floor(decNumber / 2); //{4}
- }
- while (!remStack.isEmpty()) { //{5}
- binaryString += remStack.pop().toString();
- }
- return binaryString;
- }
在这段代码里,当结果满足和 2 做整除的条件时(行 {1}),我们会获得当前结果和 2 的余数,放到栈里(行 {2}、{3})。然后让结果和 2 做整除(行 {4})。另外请注意:JavaScript 有数字类型,但是它不会区分究竟是整数还是浮点数。因此,要使用 Math.floor 函数让除法的操作仅返回整数部分。最后,用 pop 方法把栈中的元素都移除,把出栈的元素变成连接成字符串(行 {5})。
用刚才写的算法做一些测试,使用以下代码把结果输出到控制台里:
- console.log(divideBy2(233)); //输出11101001
- console.log(divideBy2(10)); //输出1010
- console.log(divideBy2(1000)); //输出1111101000
【进制转换算法】
我们很容易修改之前的算法,使之能把十进制转换成任何进制。除了让十进制数字和 2 整除 转成二进制数,还可以传入其他任意进制的基数为参数,就像下面算法这样:
- function baseConverter(decNumber, base) {
- var remStack = new Stack(),
- rem,
- baseString = '',
- digits = '0123456789ABCDEF'; //{6}
- while (decNumber > 0) {
- rem = Math.floor(decNumber % base);
- remStack.push(rem);
- decNumber = Math.floor(decNumber / base);
- }
- while (!remStack.isEmpty()) {
- baseString += digits[remStack.pop()]; //{7}
- }
- return baseString;
- }
我们只需要改变一个地方。在将十进制转成二进制时,余数是 0 或 1;在将十进制转成八进制时,余数是 0 到 7 之间的数;但是将十进制转成 16 进制时,余数是 0 到 9 之间的数字加上 A、B、C、D、E 和 F(对应 10、11、12、13、14 和 15)。因此,我们需要对栈中的数字做个转化才可以(行 {6} 和行{7})
可以使用之前的算法,输出结果如下:
- console.log(baseConverter(100345, 2)); //输出11000011111111001
- console.log(baseConverter(100345, 8)); //输出303771
- console.log(baseConverter(100345, 16)); //输出187F9
【平衡圆括号】
- function parenthesesChecker(symbols){
- let stack = new Stack(),
- balanced = true,
- index = 0,
- symbol, top,
- opens = "([{",
- closers = ")]}";
- while (index < symbols.length && balanced){
- symbol = symbols.charAt(index);
- if (opens.indexOf(symbol) >= 0){
- stack.push(symbol);
- console.log(`open symbol - stacking ${symbol}`);
- } else {
- console.log(`close symbol ${symbol}`);
- if (stack.isEmpty()){
- balanced = false;
- console.log('Stack is empty, no more symbols to pop and compare');
- } else {
- top = stack.pop();
- //if (!matches(top, symbol)){
- if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
- balanced = false;
- console.log(`poping symbol ${top} - is not a match compared to ${symbol}`);
- } else {
- console.log(`poping symbol ${top} - is is a match compared to ${symbol}`);
- }
- }
- }
- index++;
- }
- if (balanced && stack.isEmpty()){
- return true;
- }
- return false;
- }
- console.log(parenthesesChecker('{([])}')); //true
- console.log(parenthesesChecker('{{([][])}()}')); //true
- console.log(parenthesesChecker('[{()]')); //false
【汉诺塔】
- function towerOfHanoi(n, from, to, helper) {
- if (n > 0) {
- towerOfHanoi(n - 1, from, helper, to);
- to.push(from.pop());
- console.log('-----');
- console.log('Source: ' + from.toString());
- console.log('Dest: ' + to.toString());
- console.log('Helper: ' + helper.toString());
- towerOfHanoi(n - 1, helper, to, from);
- }
- }
- var source = new Stack();
- source.push(3);
- source.push(2);
- source.push(1);
- var dest = new Stack();
- var helper = new Stack();
- towerOfHanoi(source.size(), source, dest, helper);
- source.print();
- helper.print();
- dest.print();
来源: https://www.cnblogs.com/xiaohuochai/p/8174742.html