码云笔记前端博客
Home > JavaScript > Javascript中你应该知道的栈

Javascript中你应该知道的栈

2019-06-29 分类:JavaScript 作者:码云 阅读(10130)

本文共计2140个字,预计阅读时长需要6分钟。

什么是栈

栈(stack)又名堆栈,是一种遵循后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的末尾,称作栈顶,另一端称作栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

现实记忆:好比我们把一摞叠起来的盘子都可以看做一个栈,我们想要拿出最底下的盘子,一定要现将上面的移走才可以。

栈结构的代码实现

在Javascript中我们可以使用数组的原生方法实现一个栈/队列的功能,鉴于学习目的,我们也使用类来实现一个栈,下面分别进行讲解

数组实现一个栈结构

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
51
52
53
54
55
56
57
58
function Stack() {

  /**
   * 用数组来模拟栈
   */
  var items = [];

  /**
   * 将元素送入栈,放置于数组的最后一位
   */
  this.push = function(element) {
    items.push(element);
  };

  /**
   * 弹出栈顶元素
   */
  this.pop = function() {
    return items.pop();
  };

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

  /**
   * 确定栈是否为空
   * @return {Boolean} 若栈为空则返回true,不为空则返回false
   */
  this.isAmpty = function() {
    return items.length === 0
  };

  /**
   * 清空栈中所有内容
   */
  this.clear = function() {
    items = [];
  };

  /**
   * 返回栈的长度
   * @return {Number} 栈的长度
   */
  this.size = function() {
    return items.length;
  };

  /**
   * 以字符串显示栈中所有内容
   */
  this.print = function() {
    console.log(items.toString());
  };
}

类实现一个栈结构

类实现

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
class Stack {

    constructor() {
        this.items = []
    }

    // 入栈
    push(element) {
         this.items.push(element)
    }

    // 出栈
    pop() {
        return this.items.pop()
    }

    // 末位
    get peek() {
        return this.items[this.items.length - 1]
    }

    // 是否为空栈
    get isEmpty() {
        return !this.items.length
    }

    // 栈长度
    get size() {
        return this.items.length
    }

    // 清空栈
    clear() {
        this.items = []
    }

    // 打印栈数据
    print() {
        console.log(this.items.toString())
    }
}

使用栈类

1
2
3
4
5
6
7
8
9
10
11
12
13
// 实例化一个栈
const 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

栈在实际开发中的应用

二进制转为十进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* decNumber 要转换的十进制数字
* base      目标进制基数
*/
function baseConverter(decNumber, base) {
    var remStack = new Stack(),
        rem,
        baseString = '',
        digits = '0123456789ABCDEF';
    white (decNumber > 0) {
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }
   
    white(JSON.stringify(remStack) != "{}") {
        baseString += digits[remStack.pop()];
    }
   
    return baseString;
}

JS中的函数调用

栈也被用在编程语言的编译器和内存中保存变变量、函数调用。调用栈(Call Stack)

调用栈(Call Stack)是一个基本的计算机概念,这里引入一个概念:栈帧。

栈帧是指为一个函数调用单独分配的那部分栈空间。

当运行的程序从当前函数调用另外一个函数时,就会为下一个函数建立一个新的栈帧,并且进入这个栈帧,这个栈帧称为当前帧。而原来的函数也有一个对应的栈帧,被称为调用帧。每一个栈帧里面都会存入当前函数的局部变量。

栈帧结构示意图

当函数被调用时,就会被加入到调用栈顶部,执行结束之后,就会从调用栈顶部移除该函数。并将程序运行权利(帧指针)交给此时栈顶的栈帧。这种后进后出的结构也就是函数的调用栈。而在JavaScript里,可以很方便的通过console.trace()这个方法查看当前函数的调用帧

栈帧结构示意图

说明:从上面的调用可以看出来,函数的调用也是有成本的,如果函数嵌套调用的越多所消耗的资源,栈数据也就越大

「除特别注明外,本站所有文章均为码云笔记原创,转载请保留出处!」

赞(5) 打赏

觉得文章有用就打赏一下文章作者

支付宝
微信
5

觉得文章有用就打赏一下文章作者

支付宝
微信

上一篇:

下一篇:

你可能感兴趣

共有 0 条评论 - Javascript中你应该知道的栈

博客简介

码云笔记网 mybj123.com,一个专注Web前端开发技术的博客,主要记录和总结博主在前端开发工作中常用的实战技能及前端资源分享,分享各种科普知识和实用优秀的代码,以及分享些热门的互联网资讯和福利!码云笔记网有你更精彩!
更多博客详情请看关于博客

精彩评论