JavaScript数据结构之栈结构_js中能使用的栈结构

前言

随着前端的兴起，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);
            // }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

控制台：

---

总结

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

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