JavaScript数据结构之栈结构

时间:2021-1-18 作者:admin

JavaScript数据结构之栈结构

前言

随着前端的兴起,JavaScript这门语言也越来越受欢迎。接下来,让我们了解一下如何使用JavaScript来写数据结构中的栈结构吧!


一、栈结构是什么?

数组是一个线性结构,并且可以在数组的任意位置插入和删除元素。而栈就是比较常见的受限线性结构。无论是插入或是删除只能在栈顶进行操作。在栈中插入操作被称为压栈或是入栈,删除操作被称为出栈或是退栈。
栈的特点为先进后出后进先出(LIFO:last in first out)。

二、常见的栈结构使用:函数调用栈、递归等。

函数调用栈:如A函数中调用了B函数,B函数中又调用了C函数,这样在调用A函数时先将A函数压入栈,由于A函数中调用了B函数,所以将B函数再压入栈,以此类推,c函数也压入栈。这时栈顶是C函数,只有C函数执行完出栈后,B函数才能执行出栈,最后A函数出栈。这就是函数调用栈。
递归:递归是在函数内部调用自身,原理和函数调用栈类似。

三、栈的常见操作

push(element):添加一个新元素到栈顶位置;

pop():移除栈顶的元素,同时返回被移除的元素;

peek():返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它);

isEmpty():如果栈里没有任何元素就返回true,否则返回false;

size():返回栈里的元素个数。这个方法和数组的length属性类似;

toString():将栈结构的内容以字符串的形式返回。

四、使用步骤

1.创建Stack类:

function Stack() {
            // 以数组形式存储栈数据
            this.items = [];

            // (不推荐!!!因为在Stack对象添加方法,其他对象无法复用)
            // this.push = function (element) {
            //    this.item.push(element);
            // }

            // 在Stack类添加方法,可以使多对象复用
            // 入栈
            Stack.prototype.push = function (element) {
                this.items.push(element);
            }
            // 判断是否为空
            Stack.prototype.isEmpty = function () {
                return this.items.length == 0;
            }

            // 出栈
            Stack.prototype.pop = function () {
                return this.items.pop();
            }

            // 查看栈顶元素
            Stack.prototype.peek = function () {
                return this.items[this.items.length - 1]
            }

            // 获取栈中元素个数
            Stack.prototype.size = function () {
                return this.items.length;
            }

            // 以字符串形式输出元素
            Stack.prototype.toString = function () {
                // 加上空字符串隐式转换成字符串
                let result = '';
                for (let i of this.items) {
                    // 加上' '可以在元素中以空格隔开
                    result += i + ' ';
                }
                return result;
            }

            // 以上代码也可以写成ES6箭头函数形式如:
            // Stack.prototype.push = (element) => {
            //     this.item.push(element);
            // }
        }

2.使用栈:

let s = new Stack();

        // 将数据压入栈
        s.push(10);
        s.push(20);
        s.push(30);
        s.push(40);

        // 将栈顶元素出栈(40出栈)
        console.log(s.pop());

        // 查看栈顶元素(30)
        console.log(s.peek());

        // 查看栈是否为空(false,目前栈还有3个元素)
        console.log(s.isEmpty());

        // 查看栈元素个数(3)
        console.log(s.size());

        // 转化成以空格隔开的字符串形式(10 20 30)
        console.log(s.toString());

控制台:
JavaScript数据结构之栈结构


总结

看了这些,你是否对栈结构有了一定认识呢?

由于自身水平有限,本篇文章仅代表个人理解,如有错误,欢迎指正!与君共勉!

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。