JavaScript数据结构与算法—— 栈

2019-02-14 admin

我们可以在数组的任何位置上删除或者添加元素,但有时候我们还需要在元素的添加或删除时有更多控制的数据结构,有两种数据结构类似于数组,但在添加或删除元素时更为可控,它们就是栈和队列。 本节主要介绍栈。

1.栈数据结构

栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的同一端,叫做栈顶,另一端叫栈底。在栈中,新元素靠近栈顶,旧元素接近栈底。如下图所示: clipboard.png

2.创建栈

// 首先创建一类表示栈
function Stack(){
    let items = []; // 选择数组来保存栈中的元素 
    //各种属性和方法
}

下面要为栈声明一些方法:

push()  //  添加一个或多个新元素到栈顶
pop()  //  移除栈顶元素,同时返回被移除的元素
peek()  // 仅仅返回栈顶元素,不对栈做任何修改
isEmpty()  //  如果栈中没有元素返回true,否则返回false
clear()  // 移除栈中所有元素
size()  // 返回栈中元素的个数(和数组length类似) 

2.1 向栈添加元素

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

2.2 从栈移除元素

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

2.3 查看栈顶元素

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

2.4 查看栈是否为空

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

2.5 清空和打印栈元素

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

经过上述的方法的添加,我们就完整的创建了一了个栈 Stack。

3.栈的应用—十进制转N进制

首先我们写出将十进制转为二进制:

function divideBy2(decNum) {
    var remStack = new Stack(),
        rem,
        binaryString = '';
    // 将十进制数除2的余数放入一个stack中    
    while(decNum > 0) {
        // 取余
        rem = Math.floor(decNum % 2);
        // 入栈
        remStack.push(rem);
        decNum = Math.floor(decNum / 2);
    }    
    // 从栈中取出转化为字符串然后连接起来构成二进制
    while(!remStack.isEmpty()) {
        // 出栈
        binaryString += remStack.pop().toString();
    } 
    return binaryString;
}

下面十进制转化N进制算法

function divideByN(decNum, n) {
    var remStack = new Stack(),
        rem,
        binaryString = '',
        digits = '0123456789ABCDEF';
    // 将十进制数除N的余数放入一个stack中    
    while(decNum > 0) {
        // 取余
        rem = Math.floor(decNum % n);
        // 入栈
        remStack.push(rem);
        decNum = Math.floor(decNum / n);
    }    
    // 从栈中取出转化为字符串然后连接起来构成二进制
    while(!remStack.isEmpty()) {
        // 出栈 使用digits方便在16进制中做个对应转化
        binaryString += digits[remStack.pop()];
    } 
    return binaryString;
}

[转载]原文链接:https://segmentfault.com/a/1190000018144952

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-53699.html

文章标题: JavaScript数据结构与算法—— 栈

相关文章
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
javascript是什么意思
avaScript是Netscape开发的一个对象脚本语言,它使用在世界各地数以百万计的网页和服务器应用程序上。 网景的JavaScript是ecma - 262版的标准脚本语言,和公布的标准只有轻微的差异。 与广为流行的错误理解相反,Ja...
2015-11-12
21天学通javascript
简介: 本书是Javascript入门教程。Javascript是Web开发中应用最早、发展最成熟、用户最多的脚本语言。其语法简洁,代码可读性在众多脚本语言中最好,它在使用时不用考虑数据类型,是真正意义上的动态语言。本书总分为四篇,共21章...
2015-11-16
Node.js学习(1)----HTTP服务器与客户端
Node.js 标准库提供了 http 模块,其中封装了一个高效的 HTTP 服务器和一个简易的HTTP 客户端。http.Server 是一个基于事件的 HTTP 服务器,它的核心由 Node.js 下层 C++部分实现,而接口由 Jav...
2015-11-12
JavaScript的组成
一个完整的JavaScript由3个部分组成:核心(ECMAScript) 文档对象模型(DOM) 浏览器对象模型(BOM) ECMAScript 描述了该语言的语法和基本对象 ; DOM 描述了处理网页内容的方法和接口 ; BOM 描...
2015-11-12
JavaScript 事件流、事件处理程序及事件对象总结
JS与HTML之间的交互通过事件实现。事件就是文档或浏览器窗口中发生的一些特定的交互瞬间。可以使用监听器(或处理程序)来预定事件,以便事件发生时执行相应的代码。这种在传统软件工程中被称为观察员模式,支持页面的行为与页面的外观之间的松散耦合。...
2017-04-05
javaScript+turn.js实现图书翻页效果实例代码
为了实现图书翻页的效果我们在网上可以看到很多教程 在这里推荐turn.js 网上的turn.js 有api 不过是英文的  很多人看起来不方便 .关于代码也是奇形怪状在这里我将详细讲解如何使用turn.js实现翻页效果 ,本篇文章只是讲解 ...
2017-03-16
JavaScript变量的声明
声明变量 变量在脚本中的首次亮相是在其声明中。 在变量首次出现时将会在内存中设置它,因此您稍后可在脚本中引用它。 应在使用变量之前先声明变量。 可以使用 var 关键字实现此目的。 <span id=“mt9” class=“sent...
2015-11-12
7个提高效率的JavaScript调试工具
鐜板湪鐨凧avaScript浜嬪疄涓婂凡鐒舵垚涓轰簡娴佽�岀殑web璇�瑷€锛屽嵆浣垮畠骞朵笉瀹岀編銆傚緢澶氱▼搴忓憳涓嶅枩娆㈢敤JavaScript鍐欎唬鐮侊紝鏄�鍥犱负鍐欏埌鍚庢潵鎬讳細鍑虹幇鍚勭�嶈帿鍚嶅叾濡欑殑bug锛岃€屼笖鍦ㄥ紑...
2015-11-11
JavaScript短路原理精简代码
js中||和&&的特性帮我们精简了代码的同时,也带来了代码可读性的降低,虽然高效,但请灵活使用。 在js逻辑运算中,0、""、null、false、undefined、NaN都会判为false,其他都为t...
2015-11-12
回到顶部