JavaScript数据结构与算法—— 栈

王岩威发布于2019-08-23 15:11 / 2714人阅读

摘要：栈数据结构栈是一种遵循后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的同一端，叫做栈顶，另一端叫栈底。在栈中，新元素靠近栈顶，旧元素接近栈底。

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

1.栈数据结构

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

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;
}

混合云专线服务 javascript全栈视频 javascript全栈教程 javascript全栈开发 javascript快速全栈开发

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101649.html

学习JavaScript数据结构与算法（一）：栈与队列

摘要：之数组操作接下来就是数据结构的第一部分，栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素，元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法，栈与队列本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第...

Flink_China 2019-08-19 17:23 评论0 收藏0
JavaScript的数据结构与算法（一） —— 栈

摘要：栈是一种遵从后进先出原则的有序集合。新添加的或待删除的元素都保存在栈的末尾。称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。提供可操作的方法入栈出栈，但是会移掉栈中的数据。栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾。称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都靠近栈底。 javascript提供可操作的...

quietin 2019-08-21 17:12 评论0 收藏0
JavaScript 数据结构与算法之美 - 栈内存与堆内存、浅拷贝与深拷贝

摘要：栈内存与堆内存浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。栈内存与堆内存中的变量分为基本类型和引用类型。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言想写好前端，先练好内功。栈内存与堆内存、浅拷贝与深拷贝，可以说是前端程序员的内功，要知其然，知其所以然。笔者写的 JavaScrip...

dailybird 2019-08-23 18:26 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

Jonathan Shieber 2019-08-29 12:33 评论0 收藏0
CSS技巧 - 收藏集 - 掘金

摘要：笔者作为一位，将工作以来用到的各种优秀资料神器及框架整理在此，毕竟好记性不如烂键盘，此前端知识点大百科全书前端掘金，，不定期更新技巧前端掘金技巧，偶尔更新。计算数组的极值技巧使你的更加专业前端掘金一个帮你提升技巧的收藏集。 CSS 样式画各种图形 - 前端 - 掘金下面是一些我在 CSS 中经常用到的图案，还有一些是在css-tricks看到的。记录一下，以后会用到。会持续更新… 一、...

SHERlocked93 2019-08-22 11:04 评论0 收藏0