在生活中也能发现很多栈的例子。例如,厨房里堆放的盘子,总是叠在上方的先被使用;输入框内容进行删除时,总是最后输入的先删除;弹夹中的子弹,越后装入的,越先发射......
首先,创建一个类来表示栈
function Stack () { }
我们需要选择一种数据结构来保存栈里的元素,可以选择数组
function Stack(){ var items = []; //用来保存栈里的元素}
接下来,为栈添加一些方法
push(element(s)); //添加新元素到栈顶pop(); //移除栈顶的元素,同时返回被移除的元素peek(); //返回栈顶的元素,不对栈做任何修改isEmpty(); //如果栈里没有任何元素就返回true,否则falseclear(); //移除栈里的所有元素size(); //返回栈里的元素个数,类似于数组的length属性
我们需要实现的第一个方法时 push
。用来往栈里添加新元素,有一点很重要:该方法只添加到栈顶,也就是栈的末尾。所以,可以这样写:
this.push = function (element) { items.push(element);}
利用数组的 push 方法,就可以实现在栈顶末尾添加新的元素了。
接着,来实现 pop
方法,用来实现移除栈里的元素。栈遵从 LIFO(后进先出)原则。移出去的是最后添加进去的元素。因此,可以使用数组的 pop 方法。
this.pop = function () { return items.pop();}
这样一来,这个栈自然就遵从了 LIFO 原则
现在,再来为这个栈添额外的辅助方法。
如果想知道栈里最后添加的元素是什么,可以用 peek
方法。这个方法将返回栈顶的元素
this.peek = function () { return items[items.length-1];}
因为类内部是用数组保存元素的,所以这里访问数组最后一个元素用 length-1
下一个要实现的方法是 isEmpty
, 如果栈为空的话,就返回 true,否则返回 false:
this.isEmpty = function () { return items.length == 0;}
使用 isEmpty 方法,就能简单地判断栈内部是否为空。
类似于数组地 length 属性,我们也可以实现栈地 length。
this.size = function () { return items.length;}
因为栈地内部使用数组保存元素,所以数组地 length 就是栈的长度。
实现 clear
方法,clear 方法用来清空栈中所有的元素。最简单的实现方法是:
this.clear = function () { items = [];}
其实多次调用 pop 方法也可以,但是没有这个方法来的简单快捷。
最后,为了检查栈里的内容,还需要实现一个辅助方法: print
。它会把栈里的元素都输出到控制台:
this.print = function () { console.log(items.toString());}
至此,我们就完整地创建了一个栈!
function Stack(){ var 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()); }}
栈已经创建好了,我们来测试一下
首先,来初始化 Stack 类。然后,验证一下栈是否为空
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
我们往栈里又添加了 11。如果调用 size 方法,输出为 3,因为栈里有三个元素(5,8 和 11)。如果这时候调用 isEmpty 方法,会看到输出了 false(因为此时栈不为空)。最后,再来往里面添加一个元素:
stack.push(15);
然后,调用两次 pop 方法从栈里移除两个元素:
stack.pop();stack.pop();console.log(stack.size()); //控制台输出2stack.print(); //控制台输出[5,8]
到这里,整个栈的功能测试完成。
使用栈来完成进制转换。
现实生活中,我们主要用 10 进制,但在计算科学中,二进制非常重要,因为计算机里所有的内容都是用二进制数字 0 和 1 来表示的。大学的计算机课都会先教进制转换。以二进制为例:
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(520)); //输出1000001000console.log(divideBy2(10)); //输出1010console.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); //{3} decNumber = Math.floor(decNumber / base); } while (!remStack.isEmpty()) { baseString += digits[remStack.pop()]; //{7} } return baseString;}
在将十进制转成二进制时,余数是 0 或 1;在将十进制转成八进制时,余数时 0-8 之间的数;但是将十进制转成十六进制时,余数时 0-9 之间的数字加上 A、B、C、D、E、F(对应 10、11、12、13、14 和 15)。因此,需要对栈中的数字做个转化才可以(行 {6}、{7})。
来测试一下输出结果:
console.log(baseConverter(1231,2)); //输出10011001111console.log(baseConverter(1231,8)); //输出2317console.log(baseConverter(1231,16)); //输出4CF
显然是正确的。
我们用 js 代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多,比如平衡圆括号和汉诺塔。感兴趣可以自行百度去了解
原文:https://hx-dl.github.io/hx-dl.github.io/2018/06/15/如何用JavaScript手动实现一个栈/ 作者:行无忌
觉得本文对你有帮助?请分享给更多人。