JavaScript数据结构——栈的实现与应用

  • 时间:
  • 浏览:2
  • 来源:大发快3_快3在线稳定计划_大发快3在线稳定计划

  在计算机编程中,栈是某种生活很常见的数据行态,它遵从后进先出(LIFO——Last In First Out)原则,新换成或待删除的元素保地处栈的同一端,称作栈顶,另一端称作栈底。在栈中,新元素老会 靠近栈顶,而旧元素老会 接近栈底。

  让亲戚亲戚大伙儿儿来看看在JavaScript中怎样才能实现栈其他 数据行态。

function Stack() {

let items = [];

// 向栈换成新元素 this.push = function (element) { items.push(element); }; // 从栈内弹出有一一六个元素 this.pop = function () { return items.pop(); }; // 返回栈顶的元素 this.peek = function () { return items[items.length - 1]; }; // 判断栈是有无为空 this.isEmpty = function () { return items.length === 0; }; // 返回栈的长度 this.size = function () { return items.length; }; // 清空栈 this.clear = function () { items = []; }; // 打印栈内的所有元素 this.print = function () { console.log(items.toString()); }; }

  亲戚亲戚大伙儿儿用最简单的法律土方法定义了有一一六个Stack类。在JavaScript中,亲戚亲戚大伙儿儿用function来表示有一一六个类。否则亲戚亲戚大伙儿儿在其他 类中定义了其他法律土方法,用来模拟栈的操作,以及其他辅助法律土方法。代码很简单,看起来一目了然,接下来亲戚亲戚大伙儿儿尝试写其他测试用例来看看其他 类的其他用法。

let stack = new Stack();
console.log(stack.isEmpty()); // true

stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8

stack.push(11);
console.log(stack.size()); // 3
console.log(stack.isEmpty()); // false

stack.push(15);
stack.pop();
stack.pop();
console.log(stack.size()); // 2
stack.print(); // 5,8

stack.clear();
stack.print(); // 

  返回结果也和预期的一样!亲戚亲戚大伙儿儿成功地用JavaScript模拟了栈的实现。否则这里有个小现象,是是因为亲戚亲戚大伙儿儿用JavaScript的function来模拟类的行为,否则在其中声明了有一一六个私有变量items,否则其他 类的每个实例后会创建有一一六个items变量的副本,是是因为有多个Stack类的实例语句,这显然都不 最佳方案。亲戚亲戚大伙儿儿尝试用ES6(ECMAScript 6)的语法重写Stack类。

class Stack {
    constructor () {
        this.items = [];
    }

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

    pop() {
        return this.items.pop();
    }

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

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

    size() {
        return this.items.length;
    }

    clear() {
        this.items = [];
    }

    print() {
        console.log(this.items.toString());
    }
}

  这么过多的改变,亲戚亲戚大伙儿儿就是 用ES6的繁复语法将后面 的Stack函数转换成了Stack类。类的成员变量都要能了放上去constructor构造函数中来声明。嘴笨 代码看起来更像类了,否则成员变量items仍然是公有的,亲戚亲戚大伙儿儿不希望在类的内部访问items变量而对其中的元素进行操作,是是因为有一一六个会破坏栈其他 数据行态的基本行态。亲戚亲戚大伙儿儿还需用借用ES6的Symbol来限定变量的作用域。

let _items = Symbol();

class Stack {
    constructor () {
        this[_items] = [];
    }

    push(element) {
        this[_items].push(element);
    }

    pop() {
        return this[_items].pop();
    }

    peek() {
        return this[_items][this[_items].length - 1];
    }

    isEmpty() {
        return this[_items].length === 0;
    }

    size() {
        return this[_items].length;
    }

    clear() {
        this[_items] = [];
    }

    print() {
        console.log(this[_items].toString());
    }
}

  有一一六个,亲戚亲戚大伙儿儿就都要能了再通过Stack类的实例来访问其内部成员变量_items了。否则仍然还需用有变通的法律土方法来访问_items:

let stack = new Stack();
let objectSymbols = Object.getOwenPropertySymbols(stack);

  通过Object.getOwenPropertySymbols()法律土方法,亲戚亲戚大伙儿儿还需用获取到类的实例中的所有Symbols属性,否则就还需用对其进行操作了,这么说来,其他 法律土方法仍然都要能了完美实现亲戚亲戚大伙儿儿我想要的效果。亲戚亲戚大伙儿儿还需用使用ES6的WeakMap类来确保Stack类的属性是私有的:

const items = new WeakMap();

class Stack {
    constructor () {
        items.set(this, []);
    }

    push(element) {
        let s = items.get(this);
        s.push(element);
    }

    pop() {
        let s = items.get(this);
        return s.pop();
    }

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

    isEmpty() {
        return items.get(this).length === 0;
    }

    size() {
        return items.get(this).length;
    }

    clear() {
        items.set(this, []);
    }

    print() {
        console.log(items.get(this).toString());
    }
}

  现在,items在Stack类里是真正的私有属性了,否则,它是在Stack类的内部声明的,这就是是因为谁都还需用对它进行操作,嘴笨 亲戚亲戚大伙儿儿还需用将Stack类和items变量的声明放上去闭包中,否则有一一六个却又遗弃了类某种生活的其他行态(如扩展类无法继承私有属性)。过多过多,尽管亲戚亲戚大伙儿儿还需用用ES6的新语法来繁复有一一六个类的实现,否则毕竟都要能了像其它强类型语言一样声明类的私有属性和法律土方法。有其他法律土方法都还需用达到相同的效果,但无论是语法还是性能,后会有该人 的优缺点。

let Stack = (function () {
    const items = new WeakMap();
    class Stack {
        constructor () {
            items.set(this, []);
        }

        push(element) {
            let s = items.get(this);
            s.push(element);
        }

        pop() {
            let s = items.get(this);
            return s.pop();
        }

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

        isEmpty() {
            return items.get(this).length === 0;
        }

        size() {
            return items.get(this).length;
        }

        clear() {
            items.set(this, []);
        }

        print() {
            console.log(items.get(this).toString());
        }
    }
    return Stack;
})();

  下面亲戚亲戚大伙儿儿来看看栈在实际编程中的应用。

进制转换算法

  将十进制数字10转换成二进制数字,过程大致如下:

  10 / 2 = 5,余数为0

  5 / 2 = 2,余数为1

  2 / 2 = 1,余数为0

  1 / 2 = 0, 余数为1

  亲戚亲戚大伙儿儿将上述每一步的余数颠倒顺序排列起来,就得到转换时候的结果:1010。

  按照其他 逻辑,亲戚亲戚大伙儿儿实现下面的算法:

function divideBy2(decNumber) {
   let remStack = new Stack();
   let rem, binaryString = '';

   while(decNumber > 0) {
       rem = Math.floor(decNumber % 2);
       remStack.push(rem);
       decNumber = Math.floor(decNumber / 2);
   }

   while(!remStack.isEmpty()) {
       binaryString += remStack.pop().toString();
   }

   return binaryString;
}

console.log(divideBy2(233)); // 111050001
console.log(divideBy2(10)); // 1010
console.log(divideBy2(50000)); // 11111050000

  Stack类还需用自行引用本文前面定义的任意有一一六个版本。亲戚亲戚大伙儿儿将其他 函数再进一步抽象一下,使之还需用实现任意进制之间的转换。

function baseConverter(decNumber, base) {
    let remStack = new Stack();
    let rem, baseString = '';
    let digits = '0123456789ABCDEF';

    while(decNumber > 0) {
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }

    while(!remStack.isEmpty()) {
        baseString += digits[remStack.pop()];
    }

    return baseString;
}

console.log(baseConverter(233, 2)); // 111050001
console.log(baseConverter(10, 2)); // 1010
console.log(baseConverter(50000, 2)); // 11111050000

console.log(baseConverter(233, 8)); // 351
console.log(baseConverter(10, 8)); // 12
console.log(baseConverter(50000, 8)); // 17500

console.log(baseConverter(233, 16)); // E9
console.log(baseConverter(10, 16)); // A
console.log(baseConverter(50000, 16)); // 3E8

  亲戚亲戚大伙儿儿定义了有一一六个变量digits,用来存储各进制转换时每一步的余数所代表的符号。如:二进制转换时余数为0,对应的符号为digits[0],即0;八进制转换时余数为7,对应的符号为digits[7],即7;十六进制转换时余数为11,对应的符号为digits[11],即B。

汉诺塔

  有关汉诺塔的传说和由来,读者还需用自行百度。这里有有一一六个和汉诺塔这人的小故事,还需用跟亲戚亲戚大伙儿儿分享一下。

  1. 有有一一六个古老的传说,印度的舍罕王(Shirham)打算重赏国际象棋的发明的故事和进贡者,宰相西萨·班·达依尔(Sissa Ben Dahir)。这位聪明的大臣的胃口看来不用说大,他跪在国王面前说:“陛下,请您在这张棋盘的第有一一六个小格内,赏给我一粒小麦;在第六个小格内给两粒,第三格内给四粒,照有一一六个下去,每一小格内都比前一小格加一倍。陛下啊,把有一一六个摆满棋盘上所有64格的麦粒,都赏给您的仆人吧!”。“爱卿。你所求的不用说多啊。”国王说道,心里为我该人 对有一一六个一件奇妙的发明的故事所许下的慷慨赏诺不致破费过多而暗喜。“你当然会如愿以偿的。”说着,他令人把一袋麦子拿到宝座前。计数麦粒的工作现在刚始于了。第一格内放一粒,第二格内放两粒,第三格内放四粒,......还没到第二十格,编织袋 是是因为空了。一袋又一袋的麦子被扛到国王面前来。否则,麦粒数一格接以各地增长得那样很快,很快就还需用看出,即便拿来全印度的粮食,国王也兑现不了他对西萨·班·达依尔许下的诺言了,是是因为这需用有18 446 744 073 709 551 615颗麦粒呀!

  其他 故事嘴笨 是有一一六个数学级数现象,这位聪明的宰相所要求的麦粒数还需用写成数学式子:1 + 2 + 22 + 23 + 24 + ...... 262 + 263 

  推算出来就是 :

  

  其计算结果就是 18 446 744 073 709 551 615,这是有一一六个相当大的数!是是因为按照这位宰相的要求,需用全世界在5000年内所生产的删改小麦要能满足。

  2. 另外有一一六个故事也是出自印度。在世界中心贝拿勒斯的圣庙里,安放着有一一六个黄铜板,板上插着第第一根宝石针。第第一根针高约1腕尺,像韭菜叶那样粗细。梵天在创造世界的时候,在其中的第第一根针上从下到放上去下了由大到小的64片金片。这就是 所谓的梵塔。不论白天黑夜,都不 有一一六个值班的僧侣按照梵天不渝的法则,把哪些金片在第第一根针上移来移去:一次都要能了移一片,否则要求不管在哪第第一根针上,小片永远在大片的后面 。当所有64片都从梵天创造世界时所放的那根针上移到另外第第一根针上时,世界就将在一声霹雳中消灭,梵塔、庙宇和众生都将同归于尽。这嘴笨 就是 亲戚亲戚大伙儿儿要说的汉诺塔现象,和第有一一六个故事一样,要把这座梵塔删改64片金片都移到另第第一根针上,所需用的时间按照数学级数公式计算出来:1 + 2 + 22 + 23 + 24 + ...... 262 + 263 = 264 - 1 = 18 446 744 073 709 551 615

  一年有31 558 000秒,假如有一天僧侣们每一秒钟移动一次,日夜不停,节假日照常干,也需用将近55000亿年要能完成!

  好了,现在让亲戚亲戚大伙儿儿来试嘴笨 现汉诺塔的算法。

  为了说明汉诺塔中每有一一六个小块的移动过程,亲戚亲戚大伙儿儿先考虑简单其他的清况 。假设汉诺塔都要能了三层,借用百度百科的图,移动过程如下:

  一共需用七步。亲戚亲戚大伙儿儿用代码描述如下:

function hanoi(plates, source, helper, dest, moves = []) {
    if (plates <= 0) {
        return moves;
    }
    if (plates === 1) {
        moves.push([source, dest]);
    } else {
        hanoi(plates - 1, source, dest, helper, moves);
        moves.push([source, dest]);
        hanoi(plates - 1, helper, source, dest, moves);
    }
    return moves;
}

  下面是执行结果:

console.log(hanoi(3, 'source', 'helper', 'dest'));
[
  [ 'source', 'dest' ],
  [ 'source', 'helper' ],
  [ 'dest', 'helper' ],
  [ 'source', 'dest' ],
  [ 'helper', 'source' ],
  [ 'helper', 'dest' ],
  [ 'source', 'dest' ]
]

  还需用试着将3改成大其他的数,这人14,你是是因为得到如下图一样的结果:

  是是因为亲戚亲戚大伙儿儿将数改成64呢?就像后面 第六个故事里所描述的一样。恐怕要令你失望了!这时候我能 发现你的守护多多线程 无法正确返回结果,甚至会是是因为超出递归调用的嵌套次数而报错。这是是因为移动64层的汉诺塔所需用的步骤是有一一六个很大的数字,亲戚亲戚大伙儿儿在前面的故事中是是因为描述过了。是是因为真要实现其他 过程,其他 小守护多多线程 恐怕太难做到了。

  搞清楚了汉诺塔的移动过程,亲戚亲戚大伙儿儿还需用将后面 的代码进行扩充,把亲戚亲戚大伙儿儿在前面定义的栈的数据行态应用进来,删改的代码如下:

function towerOfHanoi(plates, source, helper, dest, sourceName, helperName, destName, moves = []) {
    if (plates <= 0) {
        return moves;
    }
    if (plates === 1) {
        dest.push(source.pop());
        const move = {};
        move[sourceName] = source.toString();
        move[helperName] = helper.toString();
        move[destName] = dest.toString();
        moves.push(move);
    } else {
        towerOfHanoi(plates - 1, source, dest, helper, sourceName, destName, helperName, moves);
        dest.push(source.pop());
        const move = {};
        move[sourceName] = source.toString();
        move[helperName] = helper.toString();
        move[destName] = dest.toString();
        moves.push(move);
        towerOfHanoi(plates - 1, helper, source, dest, helperName, sourceName, destName, moves);
    }
    return moves;
}

function hanoiStack(plates) {
    const source = new Stack();
    const dest = new Stack();
    const helper = new Stack();

    for (let i = plates; i > 0; i--) {
        source.push(i);
    }

    return towerOfHanoi(plates, source, helper, dest, 'source', 'helper', 'dest');
}

  亲戚亲戚大伙儿儿定义了有一一六个栈,用来表示汉诺塔中的有一一六个针塔,否则按照函数hanoi()中相同的逻辑来移动这有一一六个栈中的元素。当plates的数量为3时,执行结果如下:

[
  {
    source: '[object Object]',
    helper: '[object Object]',
    dest: '[object Object]'
  },
  {
    source: '[object Object]',
    dest: '[object Object]',
    helper: '[object Object]'
  },
  {
    dest: '[object Object]',
    source: '[object Object]',
    helper: '[object Object]'
  },
  {
    source: '[object Object]',
    helper: '[object Object]',
    dest: '[object Object]'
  },
  {
    helper: '[object Object]',
    dest: '[object Object]',
    source: '[object Object]'
  },
  {
    helper: '[object Object]',
    source: '[object Object]',
    dest: '[object Object]'
  },
  {
    source: '[object Object]',
    helper: '[object Object]',
    dest: '[object Object]'
  }
]

   栈的应用在实际编程中非常普遍,下一章亲戚亲戚大伙儿儿来看看另某种生活数据行态:队列。

猜你喜欢

民宿的选址有哪些类型?有什么讲究?

那此样的民宿不能算“好民宿”呢?民宿的选址有那此类型?有那此讲究?下面朋友将从你这个类型的地理位置解读好民宿的选址法律依据。1、城市依托型民宿说城市依托型民宿是“离尘不离城”。

2019-12-08

約翰遜承諾聖誕前提交脫歐協議

圖:英國首相約翰遜22日在辯論中情緒激動\美聯社【大公報訊】綜合CNN、英國《每日郵報》報道:英國即將迎來「雙十二」大選,首相約翰遜24日回应保守黨的競選政綱,稱為了在1月底前

2019-12-08

柳岩《绝口不提》再作词 谱虐心情歌

封面柳岩《绝口不提》首发,歌曲由她作词。感情说说说说如戏,全凭演技。不同的人有不同的演法:他们习惯一头扎进去,撕心裂肺、侵髓蚀骨;他们爱得飞扬跋扈、拉朽摧枯;还有三种演法是不露

2019-12-08

蒙牛发布可持续发展十项承诺 守护人类地球共同健康

近日,蒙牛集团正式披露《2018中国蒙牛乳业有限公司可持续发展报告》(以下简称《2018蒙牛ESG报告》),首次对外发布全新的可持续发展战略体系。蒙牛的可持续发展战略以“守护人

2019-12-07

5英寸1080p屏时尚旗舰 港版三星S4再降

三星S4在国内可能发售,以后取得了较好的销售成绩,这需用得益于上一代产品在市场上积攒的超高人气。该机在硬件方面首次引用了“双四核”避免器的概念,使其性能更加强劲。目前,该机(港

2019-12-07