JavaScript中数据结构与算法(一)：栈

序

数据结构与算法JavaScript这本书算是讲解得比较浅显的，优点就是用javascript语言把常用的数据结构给描述了下，书中很多例子来源于常见的一些面试题目，算是与时俱进，业余看了下就顺便记录下来吧

git代码下载：https://github.com/JsAaron/data_structure.git

栈结构

特殊的列表，栈内的元素只能通过列表的一端访问，栈顶

后入先出(LIFO,last-in-first-out)的数据结构

javascript提供可操作的方法, 入栈 push, 出栈 pop，但是pop会移掉栈中的数据

实现一个栈的实现类

底层存数数据结构采用 数组

因为pop是删除栈中数据，所以需要实现一个查找方法 peek

实现一个清理方法 clear

栈内元素总量查找 length

查找是否还存在元素 empty

代码如下:

function Stack(){
    this.dataStore = []
    this.top    = 0;
    this.push   = push
    this.pop    = pop
    this.peek   = peek
    this.length = length;
}

function push(element){
    this.dataStore[this.top++] = element;
}

function peek(element){
    return this.dataStore[this.top-1];
}

function pop(){
    return this.dataStore[--this.top];
}

function clear(){
    this.top = 0
}

function length(){
    return this.top
}

回文

回文就是指一个单词，数组，短语，从前往后从后往前都是一样的 12321.abcba

回文最简单的思路就是, 把元素反转后如果与原始的元素相等，那么就意味着这就是一个回文了

这里可以用到这个栈类来操作

代码如下:

function isPalindrome(word) {
    var s = new Stack()
    for (var i = 0; i < word.length; i++) {
        s.push(word[i])
    }
    var rword = "";
    while (s.length() > 0) {
        rword += s.pop();
    }
    if (word == rword) {
        return true;
    } else {
        return false;
    }
}

isPalindrome("aarra") //false
isPalindrome("aaraa") //true

看看这个isPalindrome函数，其实就是通过调用Stack类，然后把传递进来的word这个元素给分解后的每一个组成单元给压入到栈了，根据栈的原理，后入先出的原则，通过pop的方法在反组装这个元素，最后比较下之前与组装后的，如果相等就是回文了

递归

用递归实现一个阶乘算法

5! = 5 * 4 * 3 * 2 * 1 = 120

用递归

代码如下:

function factorial(n) {
    if (n === 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

用栈操作

代码如下:

function fact(n) {
    var s = new Stack()
    while (n > 1) {
        //[5,4,3,2]
        s.push(n--);
    }
    var product = 1;
    while (s.length() > 0) {
        product *= s.pop();
    }
    return product;
}

fact(5) //120

通过while把n = 5 递减压入栈，然后再通过一个循环还是根据栈的后入先出的原则，通过pop方法把最前面的取出来与product叠加

赞 (0)

相关推荐

  • JavaScript数据结构与算法之栈详解

    JavaScript数据结构与算法之栈详解

    在上一篇博客介绍了下列表,列表是最简单的一种结构,但是如果要处理一些比较复杂的结构,列表显得太简陋了,所以我们需要某种和列表类似但是更复杂的数据结构---栈.栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样操作很快,而且容易实现. 一:对栈的操作. 栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端陈为栈顶.比如餐馆里面洗盘子,只能先洗最上面的盘子,盘子洗完后,也只能螺到这一摞盘子的最上面.栈被称为 "后入先出"(LIFO)的数据结构. 由于栈具有后入先出的特点

  • JavaScript数据结构学习之数组、栈与队列

    前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法

  • 使用JavaScript实现链表的数据结构的代码

    链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)   - 维基百科 上面是维基百科对 链表 的解读.下面我们用 JavaScript 代码对链表的数据结构进行实现 实现Node类表示节点 /** * Node 类用来表示节点 * element 用来保存节点上的数据 * next 用来保存指向下一个节点的链接 */ function Node(element) { this.elemen

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript数据结构中栈的应用之表达式求值问题详解

    本文实例讲述了JavaScript数据结构中栈的应用之表达式求值问题.分享给大家供大家参考,具体如下: 下面来谈一个比较经典的表达式求值问题,这个问题主要是设计到操作符的优先级.我们通常看到的表达式都是中缀表达式,存在很多优先级差别,而后缀表达式则没有这些优先级问题.下面先看看两种表达式的区别. 中缀表达式:a*b+c*d-e/f      后缀表达式:ab*cd*+ef/- 从中缀表达式转换到后缀表示式是很难实现的,我们这里可以通过栈的思想来实现.下面进行详细的介绍是什么样的思想: 在对一个中

  • 利用JavaScript实现栈的数据结构示例代码

    前言 本文主要给大家介绍的是关于JavaScript实现栈的数据结构的相关内容,分享出来供大家参考学习,话不多少,来一起看看详细的介绍: 堆栈(英语:stack),也可直接称栈,在计算机科学中,是一种特殊的串列形式的数据结构,它的特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入数据(push)和输出数据(pop)的运算.另外栈也可以用一维数组或连结串列的形式来完成. 由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First

  • JavaScript数组实现数据结构中的队列与堆栈

    JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • JavaScript中数据结构与算法(一)：栈

    JavaScript中数据结构与算法(一)：栈

    序 数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记录下来吧 git代码下载:https://github.com/JsAaron/data_structure.git 栈结构 特殊的列表,栈内的元素只能通过列表的一端访问,栈顶 后入先出(LIFO,last-in-first-out)的数据结构 javascript提供可操作的方法, 入栈 push,

  • JavaScript中数据结构与算法(二)：队列

    队列是只允许在一端进行插入操作,另一个进行删除操作的线性表,队列是一种先进先出(First-In-First-Out,FIFO)的数据结构 队列在程序程序设计中用的非常的频繁,因为javascript单线程,所以导致了任何一个时间段只能执行一个任务,而且还参杂了异步的机制, 那么带来的问题: 1. 在异步操作执行的时候,同步代码还在继续,那么同步代码依赖异步,自然就会出错 2. 多个同步的任务在不同的时间段被调用 jQuery的动画中,我们经常写一段连续的动画代码 $book.animate({

  • JavaScript中数据结构与算法(三)：链表

    JavaScript中数据结构与算法(三)：链表

    我们可以看到在javascript概念中的队列与栈都是一种特殊的线性表的结构,也是一种比较简单的基于数组的顺序存储结构.由于javascript的解释器针对数组都做了直接的优化,不会存在在很多编程语言中数组固定长度的问题(当数组填满后再添加就比较困难了,包括添加删除,都是需要把数组中所有的元素全部都变换位置的,javascript的的数组确实直接给优化好了,如push,pop,shift,unshift,split方法等等-) 线性表的顺序存储结构,最大的缺点就是改变其中一个元素的排列时都会引起

  • JavaScript中数据结构与算法(四)：串(BF)

    JavaScript中数据结构与算法(四)：串(BF)

    串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的.线性表更关注的是单个元素的操作CURD,串则是关注查找子串的位置,替换等操作. 当然不同的高级语言对串的基本操作都有不同的定义方法,但是总的来说操作的本质都是相似的.比如javascrript查找就是indexOf, 去空白就是trim,转化大小写toLowerCase/toUpperCase等等 这里主要讨论下字符串模式匹配的几种经典的算法:BF.BM

  • JavaScript中数据结构与算法(五)：经典KMP算法

    JavaScript中数据结构与算法(五)：经典KMP算法

    KMP算法和BM算法 KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同 前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右 后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右. 通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上蛋疼的KMP是讲解很多,基本都是走的高大上路线看的你也是一头雾水,我试图用自己的理解用最接地气的方式描述 KMP KMP也是一种优化版的

  • Java数据结构与算法之栈(动力节点Java学院整理)

    stack,中文翻译为堆栈,其实指的是栈,heap,堆.这里讲的是数据结构的栈,不是内存分配里面的堆和栈. 栈是先进后出的数据的结构,好比你碟子一个一个堆起来,最后放的那个是堆在最上面的. 队列就是排队买苹果,先去的那个可以先买. 栈 public class Stack { private int array[]; private int max; private int top; public Stack(int max){ this.max = max; array = new int[m

  • JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

    排序算法的介绍 排序也称排序算法 (Sort Algorithm),排序是将 一组数据 , 依指定的顺序 进行 排列的过程 . 排序的分类 1)  内部排序 : 指将需要处理的所有数据都加载 到 内部存储器(内存) 中进行排序. 2) 外部排序法: 数据量过大,无法全部加载到内 存中,需要借助 外部存储(文件等) 进行 排序. 常见的排序算法分类 算法的时间复杂度 度量一个程序(算法)执行时间的两种方法 1.事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,

  • Java数据结构与算法之栈(Stack)实现详解

    Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

随机推荐