主页 / 网络编程 /

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

网络编程 2021-07-04 21:48www.168986.cn编程入门
这篇文章主要介绍了JavaScript中数据结构与算法(一)栈,本文讲解了栈的结构、什么是回文以及递归等内容,讲解的不错,通俗易懂,需要的朋友可以参考下

序

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

git代码下载

栈结构

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

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

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

实现一个栈的实现类

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

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

实现一个清理方法 clear

栈内元素总量查找 length

查找是否还存在元素 empty

代码如下:

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

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

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

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

function clear(){
    this. = 0
}

function length(){
    return this.
}

回文

回文就是指一个单词，数组，短语，从前往后从后往前都是一样的 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叠加

上一篇：JavaScript中数据结构与算法(二)：队列 下一篇：JQuery中模拟image的ajaxPrefilter与ajaxTransport处理

编程语言

Copyright © 2016-2025 www.168986.cn 狼蚁网络 版权所有 Power by