1. 首页
  2. IT资讯

「数据结构基础」栈简介(使用ES6)

“u003Cdivu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp3.pstatp.comu002Flargeu002Fpgc-imageu002F5ddd9db98e194af68f0b06370a9c4c1b” img_width=”1080″ img_height=”667″ alt=”「数据结构基础」栈简介(使用ES6)” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E开篇u003Cu002Fpu003Eu003Cpu003E数据结构这词大家都不陌生吧,这可是计算机专业人员的必修专业课之一,如果想成为专业的开发人员,必须深入理解这门课程,在这系列文章里,笔者将使用ES6,让大家熟悉数据结构这门专业课的内容。u003Cu002Fpu003Eu003Cpu003E到底什么是数据结构?数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关(来源百度百科)。更多关于数据结构的介绍,大家可以先看看笔者的这篇文章《JavaScript 数据结构:什么是数据结构?》。u003Cu002Fpu003Eu003Cpu003E本篇文章笔者将从数据结构最基础的结构开始介绍——stack(栈),笔者将从以下几个方面进行介绍:u003Cu002Fpu003Eu003Culu003Eu003Cliu003E什么是栈?u003Cu002Fliu003Eu003Cliu003E如何用JS简单的实现栈?u003Cu002Fliu003Eu003Cliu003E创建更高效的基于对象Stack类u003Cu002Fliu003Eu003Cliu003E实际应用举例u003Cu002Fliu003Eu003Cliu003E练习题u003Cu002Fliu003Eu003Cu002Fulu003Eu003Cpu003E本篇文章阅读时间预计u003Cstrongu003E10u003Cu002Fstrongu003E分钟。u003Cu002Fpu003Eu003Cpu003Eu003Cstrongu003E01 什么是栈?u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E栈是一种高效的数据结构(后进先出(LIFO)原则的有序集合),因为数据只能在栈顶添加或删除,所以这样的操作很快,而且容易实现。栈的使用遍布程序语言实现的方方面面。编程语言中的编译器也会使用到堆栈,计算机内存也会使用堆栈来存储变量和方法调用,浏览器的后退功能。除了计算机方面有诸多栈的应用,现实中也有实际例子,比如我们从一摞书中拿一本书,吃自助餐从一摞盘子里拿最上面的盘子,等等:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002F6632b8413db74d1397fb0f7f305b31ca” img_width=”900″ img_height=”636″ alt=”「数据结构基础」栈简介(使用ES6)” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003Eu003Cstrongu003E02 如何用JS简单的实现栈?u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E我们如何使用JS模拟一个简单的栈呢,首先我们创建一个stack-array.js文件,声明一个StackArray类,代码如下:u003Cu002Fpu003Eu003Cpreu003Eclass StackArray {u003Cbru003E constructor() {u003Cbru003E this.items = []; u003Cbru003E }u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E接下来该怎么做?我们需要一个能够存储堆栈元素的数据结构,我们可以使用数组结构来完成,同时还需要我们在堆栈中添加和移除数据元素,由于堆栈后进先出的原则,我们的添加和删除方法稍微特别些,Stack这个类的实现包含以下几个方法:u003Cu002Fpu003Eu003Culu003Eu003Cliu003Epush(element(s)): 此方法将新添加的元素添加至堆栈的顶部u003Cu002Fliu003Eu003Cliu003Epop():此方法删除栈顶的元素,同时返回已删除的元素u003Cu002Fliu003Eu003Cliu003Epeek(): 返回堆栈的顶部元素u003Cu002Fliu003Eu003Cliu003EisEmpty(): 判断堆栈是否为空,如果为空,返回True, 否则返回False。u003Cu002Fliu003Eu003Cliu003Eclear(): 清空堆栈所有的元素。u003Cu002Fliu003Eu003Cliu003Esize(): 此方法返回堆栈元素的数量,类似数组的长度。u003Cu002Fliu003Eu003Cliu003EtoArray(): 以数组的形式返回堆栈的元素。u003Cu002Fliu003Eu003Cliu003EtoString():以字符串的形式输出堆栈内容。u003Cu002Fliu003Eu003Cu002Fulu003Eu003Cpu003Eu003Cstrongu003Epush()u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E此方法负责向堆栈添加新元素,其中最重要的特点就是:只能将新元素添加到栈顶,即堆栈的末尾,我们可以使用数组的push方法正好符合这个需求,代码如下:u003Cu002Fpu003Eu003Cpreu003Epush(element) {u003Cbru003E this.items.push(element);u003Cbru003E} u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cstrongu003Epop()u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E接下来我们来实现pop()方法,此方法实现删除栈顶的元素,由于遵循LIFO原则,删除的是最后的元素,我们可以使用数组自带的pop方法,代码如下:u003Cu002Fpu003Eu003Cpreu003Epop() {u003Cbru003E return this.items.pop();u003Cbru003E} u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cstrongu003Epeek()、isEmpty()、size()、clear()u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E核心的添加和删除已经完成,现在我们来实现相关的辅助方法, peek()方法让我们获取堆栈最后的一个元素,实现代码如下:u003Cu002Fpu003Eu003Cpreu003Epeek() {u003Cbru003E return this.items[this.items.length – 1];u003Cbru003E} u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003EisEmpty()的方法也十分简单,判断堆栈数组的长度是否为0即可,代码如下:u003Cu002Fpu003Eu003Cpreu003EisEmpty() {u003Cbru003E return this.items.length === 0;u003Cbru003E} u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Esize()方法更简单,使用数组的length方法即可,代码如下:u003Cu002Fpu003Eu003Cpreu003Esize() {u003Cbru003E return this.items.length;u003Cbru003E} u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E最后实现最简单的清空方法clear(),将堆栈变量重新置空赋值即可:u003Cu002Fpu003Eu003Cpreu003Eclear() {u003Cbru003E this.items = [];u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E最终完成的stack-array.js代码如下:u003Cu002Fpu003Eu003Cpreu003Eexport default class StackArray {u003Cbru003E constructor() {u003Cbru003E this.items = [];u003Cbru003E }u003Cbru003E push(element) {u003Cbru003E this.items.push(element);u003Cbru003E }u003Cbru003E pop() {u003Cbru003E return this.items.pop();u003Cbru003E }u003Cbru003E peek() {u003Cbru003E return this.items[this.items.length – 1];u003Cbru003E }u003Cbru003E isEmpty() {u003Cbru003E return this.items.length === 0;u003Cbru003E }u003Cbru003E size() {u003Cbru003E return this.items.length;u003Cbru003E }u003Cbru003E clear() {u003Cbru003E this.items = [];u003Cbru003E }u003Cbru003E toArray() {u003Cbru003E return this.items;u003Cbru003E }u003Cbru003E toString() {u003Cbru003E return this.items.toString();u003Cbru003E }u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E接下来我们创建一个stackdemo.js的文件,引入我们的stack-array.js文件,我们一起来实践下如何使用我们创建好的StackArray类,代码如下:u003Cu002Fpu003Eu003Cpreu003Eimport StackArray from ‘stack-array.js’;u003Cbru003Econst stack = new StackArray();u003Cbru003Econsole.log(‘stack.isEmpty() => ‘, stack.isEmpty()); u002Fu002F outputs trueu003Cbru003Estack.push(5);u003Cbru003Estack.push(8);u003Cbru003Econsole.log(‘stack after push 5 and 8 => ‘, stack.toString());u003Cbru003Econsole.log(‘stack.peek() => ‘, stack.peek()); u002Fu002F outputs 8u003Cbru003Estack.push(11);u003Cbru003Econsole.log(‘stack.size() after push 11 => ‘, stack.size()); u002Fu002F outputs 3u003Cbru003Econsole.log(‘stack.isEmpty() => ‘, stack.isEmpty()); u002Fu002F outputs falseu003Cbru003Estack.push(15);u003Cbru003Estack.pop();u003Cbru003Estack.pop();u003Cbru003Econsole.log(‘stack.size() after push 15 and pop twice => ‘, stack.size()); u002Fu002F outputs 2u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E我们可以新建一个stackdemo.html,引入stackdemo.js(<script type=”module” src=”stackdemo.js”><u002Fscript>),打开stackdemo.html即可,堆栈的运行示意如下图所示:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp3.pstatp.comu002Flargeu002Fpgc-imageu002Fa9b10278472a4538843289d3e91590ad” img_width=”900″ img_height=”352″ alt=”「数据结构基础」栈简介(使用ES6)” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E执行完push后的堆栈u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp3.pstatp.comu002Flargeu002Fpgc-imageu002Fe699e3f675e74fb0be959504821e960e” img_width=”900″ img_height=”533″ alt=”「数据结构基础」栈简介(使用ES6)” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E执行完pop后的堆栈u003Cu002Fpu003Eu003Cpu003Eu003Cstrongu003E03 创建更高效的基于对象Stack类u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E上一小节我们基于数组快速实现了栈,我们清楚数组是有序数组,如果存储大数据,内容过多的话,长度过大的话,会消耗更多的计算机内存,算法的复杂度就会增加(O(n),后面的文章将会介绍),为了解决这个问题,我们使用更原始的方法进行实现。首先我们在stack.js文件里声明stack类,代码如下:u003Cu002Fpu003Eu003Cpreu003Eclass Stack {u003Cbru003E constructor() {u003Cbru003E this.count = 0;u003Cbru003E this.items = {};u003Cbru003E }u003Cbru003E u002Fu002F methodsu003Cbru003E} u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cstrongu003Epush()u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E在JS中,对象是一组键值对,我们可以将使用count变量作为items对象的键,元素是其值,添完新元素后,count变量加1,代码实现如下:u003Cu002Fpu003Eu003Cpreu003Epush(element) {u003Cbru003E this.items[this.count] = element;u003Cbru003E this.count++;u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E比如我们可以向空的栈里添加新元素5和8,代码如下:u003Cu002Fpu003Eu003Cpreu003Econst stack = new Stack();u003Cbru003Estack.push(5);u003Cbru003Estack.push(8);u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E如果输出Stack对象的items和count,效果如下:u003Cu002Fpu003Eu003Cpreu003Eitems = {u003Cbru003E 0: 5,u003Cbru003E 1: 8u003Cbru003E};u003Cbru003Ecount = 2;u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cstrongu003EisEmpty()u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E判断栈是否空,我们只需要判断count变量是否为0即可,代码如下:u003Cu002Fpu003Eu003Cpreu003EisEmpty() {u003Cbru003E return this.count === 0;u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cstrongu003Epop()u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E改写这个方法,我们首先需要验证堆栈是否为空,如果未空返回undefined,如果不为空,我们将变量count的值减1,同时删除对应的属性,代码如下:u003Cu002Fpu003Eu003Cpreu003Epop() {u003Cbru003E if (this.isEmpty()) {u003Cbru003E return undefined;u003Cbru003E }u003Cbru003E this.count–;u003Cbru003E const result = this.items[this.count];u003Cbru003E delete this.items[this.count];u003Cbru003E return result;u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E接下来我们改写其他的方法,完整代码如下:u003Cu002Fpu003Eu003Cpreu003Eexport default class Stack {u003Cbru003E constructor() {u003Cbru003E this.count = 0;u003Cbru003E this.items = {};u003Cbru003E }u003Cbru003E push(element) {u003Cbru003E this.items[this.count] = element;u003Cbru003E this.count++;u003Cbru003E }u003Cbru003E pop() {u003Cbru003E if (this.isEmpty()) {u003Cbru003E return undefined;u003Cbru003E }u003Cbru003E this.count–;u003Cbru003E const result = this.items[this.count];u003Cbru003E delete this.items[this.count];u003Cbru003E return result;u003Cbru003E }u003Cbru003E peek() {u003Cbru003E if (this.isEmpty()) {u003Cbru003E return undefined;u003Cbru003E }u003Cbru003E return this.items[this.count – 1];u003Cbru003E }u003Cbru003E isEmpty() {u003Cbru003E return this.count === 0;u003Cbru003E }u003Cbru003E size() {u003Cbru003E return this.count;u003Cbru003E }u003Cbru003E clear() {u003Cbru003E u002F* while (!this.isEmpty()) {u003Cbru003E this.pop();u003Cbru003E } *u002Fu003Cbru003E this.items = {};u003Cbru003E this.count = 0;u003Cbru003E }u003Cbru003E toString() {u003Cbru003E if (this.isEmpty()) {u003Cbru003E return ”;u003Cbru003E }u003Cbru003E let objString = `${this.items[0]}`;u003Cbru003E for (let i = 1; i < this.count; i++) {u003Cbru003E objString = `${objString},${this.items[i]}`;u003Cbru003E }u003Cbru003E return objString;u003Cbru003E }u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E虽然我们类完成了,大家是不是觉得有点问题,由于我们创建的类的属性对于任何开发人员都是公开的,我们希望只能在栈顶添加元素,不希望在其他位置添加元素,但是我们在Stack类中声明的items和count属性不受保护,这是JS的规则问题,难道我们没有办法改变了吗?答案是可以,我们可以ES6加入的新类型Symbol数据类型作为对象的属性具有私有性的特点(关于Symbol数据类型,笔者的这篇文章有过介绍《【ES6基础】Symbol介绍:独一无二的值》),改写基于stack-array.js版本的代码,代码如下:u003Cu002Fpu003Eu003Cpreu003Econst _items = Symbol(‘stackItems’);u003Cbru003Eclass Stack {u003Cbru003E constructor() {u003Cbru003E this[_items] = [];u003Cbru003E }u003Cbru003E push(element) {u003Cbru003E this[_items].push(element);u003Cbru003E }u003Cbru003E pop() {u003Cbru003E return this[_items].pop();u003Cbru003E }u003Cbru003E peek() {u003Cbru003E return this[_items][this[_items].length – 1];u003Cbru003E }u003Cbru003E isEmpty() {u003Cbru003E return this[_items].length === 0;u003Cbru003E }u003Cbru003E size() {u003Cbru003E return this[_items].length;u003Cbru003E }u003Cbru003E clear() {u003Cbru003E this[_items] = [];u003Cbru003E }u003Cbru003E print() {u003Cbru003E console.log(this.toString());u003Cbru003E }u003Cbru003E toString() {u003Cbru003E return this[_items].toString();u003Cbru003E }u003Cbru003E}u003Cbru003Econst stack = new Stack();u003Cbru003Econst objectSymbols = Object.getOwnPropertySymbols(stack);u003Cbru003Econsole.log(objectSymbols.length); u002Fu002F 1u003Cbru003Econsole.log(objectSymbols); u002Fu002F [Symbol()]u003Cbru003Econsole.log(objectSymbols[0]); u002Fu002F Symbol()u003Cbru003Estack[objectSymbols[0]].push(1);u003Cbru003Estack.print(); u002Fu002F 5, 8, 1u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cstrongu003E04 实际应用举例u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E堆栈在实际的问题中有着各种各样的运用,比如我们会经常使用各种软件的撤销操作功能,尤其是Java和C#编程语言使用堆栈来变量存储和方法调用,并且可以抛出堆栈溢出异常,尤其是在使用递归算法时。接下来,我们亲自动手实现个10进制转2进制的功能。u003Cu002Fpu003Eu003Cpu003E我们已经熟悉十进制。 然而,二进制表示在计算机科学中非常重要,因为计算机中的所有内容都由二进制数字(0和1)表示。 如果没有在十进制和二进制数之间来回转换的能力,与计算机进行通信将会十分困难。要将10进制转换成2进制,我们需要将要转换数字除以2,再将结果除以2,如此循环直到结果为0为止,具体示意如图所示:u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002F6c7ba41824754419929f07f7d5f74a6a” img_width=”900″ img_height=”376″ alt=”「数据结构基础」栈简介(使用ES6)” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E2进制转换逻辑示意图u003Cu002Fpu003Eu003Cpu003E基于上图逻辑释义,完成的功能代码如下:u003Cu002Fpu003Eu003Cpreu003Efunction decimalToBinary(decNumber) {u003Cbru003E const remStack = new Stack();u003Cbru003E let number = decNumber;u003Cbru003E let rem;u003Cbru003E let binaryString = ”;u003Cbru003E while (number > 0) {u003Cbru003E rem = Math.floor(number % 2);u003Cbru003E remStack.push(rem);u003Cbru003E number = Math.floor(number u002F 2);u003Cbru003E }u003Cbru003E while (!remStack.isEmpty()) {u003Cbru003E binaryString += remStack.pop().toString();u003Cbru003E }u003Cbru003E return binaryString;u003Cbru003E}u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003E从上述代码我们定义了一个堆栈,使用循环处理待处理的数字,将取模的余数推入堆栈,然后逐个弹出,拼接成字符串进行输出。接着我们测试下,十进制转二进制是否符合预期,如下段测试代码:u003Cu002Fpu003Eu003Cpreu003Econsole.log(decimalToBinary(233)); u002Fu002F 11101001u003Cbru003Econsole.log(decimalToBinary(10)); u002Fu002F 1010u003Cbru003Econsole.log(decimalToBinary(1000)); u002Fu002F 1111101000u003Cbru003Eu003Cu002Fpreu003Eu003Cpu003Eu003Cstrongu003E05 练习题u003Cu002Fstrongu003Eu003Cu002Fpu003Eu003Cpu003E刚才我们实践了十进制转二进制,为了让其更有通用性,因为在实际应用中,不仅仅有二进制的转换需求,比如还有8进制、16进制等,现在笔者要给大家留作业了,实现函数baseConverter(decNumber, base),第一参数是要转换的10进制数,第二个参数是需要转换的进制,让其具备10进制数任意转换成2~36进制的需求,欢迎大家在留言区贴代码。u003Cu002Fpu003Eu003Cdiv class=”pgc-img”u003Eu003Cimg src=”http:u002Fu002Fp1.pstatp.comu002Flargeu002Fpgc-imageu002F33fe92834c2f4e128664b7354d5156a8″ img_width=”640″ img_height=”20″ alt=”「数据结构基础」栈简介(使用ES6)” inline=”0″u003Eu003Cp class=”pgc-img-caption”u003Eu003Cu002Fpu003Eu003Cu002Fdivu003Eu003Cpu003E本篇文章,我们了解了什么是数据结构,并深入学习了堆栈这个数据结构,以及如何用JS代码实现堆栈,并讲解了不同的实现方式,同时了解栈在计算机领域的应用,并一起实践了一个十进制数转二进制的练习,接下来本系列文章,笔者将带着大家一起深入学习和堆栈类似的队列结构,唯一不同的就是先进先出(FIFO),敬请期待。u003Cu002Fpu003Eu003Cu002Fdivu003E”

原文始发于:「数据结构基础」栈简介(使用ES6)

主题测试文章,只做测试使用。发布者:杀手梦三刀,转转请注明出处:http://www.cxybcw.com/10812.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code