JavaScript 算法

【数据结构与算法】栈（JavaScript版详解）

By yesmore on 2021-08-12
阅读时间 12 分钟
文章共 3.1k 字
阅读量 次

要点：栈（顺序栈、链栈）概念、栈结构的5大应用

先知：数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。但是有时候，我们为了实现某些功能，必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。

一、什么是栈

1.1 栈

栈（stack）是一种运算受限的线性表：

1、LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间。类似于自动餐托盘，最后放上的托盘，往往先把拿出去使用。

2、其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

3、向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；

4、从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

如下图所示：
image

栈的特点：先进后出，后进先出。

常见问题：数制转换 表达式求值 括号匹配的检验 八皇后问题 行编辑程序 函数调用 迷宫求解 递归调用的实现

1.2 顺序栈&链栈

栈 是线性表的特例，其具备先进后出 FILO 特性

1.2.1 顺序栈

可以使用线性表的顺序存储结构（即数组）实现栈，将之称之为 顺序栈

1.2.2 链栈

可以使用单链表结构实现栈，将之称之为 链栈

1.2.3 顺序栈&链栈的异同

同【时间复杂度】

顺序栈和链栈的时间复杂度均为 $O(1)$

异【空间性能】
a顺序栈

顺序栈需要事先确定一个固定的长度（数组长度）

可能存在内存空间浪费问题，但它的优势是存取时定位很方便

b链栈

要求每个元素都要配套一个指向下个结点的指针域

增大了内存开销，但好处是栈的长度无限

因此，如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好使用链栈;

反之，如果它的变化在可控范围内，则建议使用顺序栈

1.3 栈的内部实现原理

栈的内部实现原理其实就是数组或链表的操作

而之所以引入 栈 这个概念，是为了将程序设计问题模型化

用高层的模块指导特定行为（栈的先进后出特性），划分了不同关注层次，使得思考范围缩小

更加聚焦于我们致力解决的问题核心，简化了程序设计的问题

二、程序中的栈结构

函数调用栈：A(B(C(D())))：
即 A 函数中调用 B，B 调用 C，C 调用 D；在 A 执行的过程中会将 A 压入栈，随后 B 执行时 B 也被压入栈，函数 C 和 D 执行时也会被压入栈。所以当前栈的顺序为：A->B->C->D（栈顶）；函数 D 执行完之后，会弹出栈被释放，弹出栈的顺序为 D->C->B->A;

递归
为什么没有停止条件的递归会造成栈溢出？比如函数 A 为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数 A 压入栈，最后造成栈溢出（Queue Overfloat）。

浏览器中的栈

栈在很多地方都有着应用，比如大家熟悉的浏览器就有很多栈，其实浏览器的执行栈就是一个基本的栈结构，从数据结构上说，它就是一个栈。 这也就解释了，我们用递归的解法和用循环+栈的解法本质上是差不多的。

比如如下 JS 代码：

1
2
3
4
5
6
7
8
9
10
11
function bar() {
  const a = 1;
  const b = 2;
  console.log(a, b);
}
function foo() {
  const a = 1;
  bar();
}

foo();

真正执行的时候，内部大概是这样的：

basic-data-structure-call-stack

栈常见的应用有进制转换，括号匹配，栈混洗，中缀表达式（用的很少），后缀表达式（逆波兰表达式）等。

合法的栈混洗操作也是一个经典的题目，这其实和合法的括号匹配表达式之间存在着一一对应的关系，也就是说 n 个元素的栈混洗有多少种，n 对括号的合法表达式就有多少种。

三、练习

题目1：

有 6 个元素 6，5，4，3，2，1 按顺序进栈，问下列哪一个不是合法的出栈顺序？

A：5 4 3 6 1 2 （√）

B：4 5 3 2 1 6 （√）

C：3 4 6 5 2 1 （×）

D：2 3 4 1 5 6 （√）

题目所说的按顺序进栈指的不是一次性全部进栈，而是有进有出，进栈顺序为 6 -> 5 -> 4 -> 3 -> 2 -> 1。

解析：

A 答案：65 进栈，5 出栈，4 进栈出栈，3 进栈出栈，6 出栈，21 进栈，1 出栈，2 出栈（整体入栈顺序符合 654321）。

B 答案：654 进栈，4 出栈，5 出栈，3 进栈出栈，2 进栈出栈，1 进栈出栈，6 出栈（整体的入栈顺序符合 654321）。

C 答案：6543 进栈，3 出栈，4 出栈，之后应该 5 出栈而不是 6，所以错误。

D 答案：65432 进栈，2 出栈，3 出栈，4 出栈，1 进栈出栈，5 出栈，6 出栈。符合入栈顺序。

题目2：

1

题目3：

2

四、栈结构实现

4.1 栈常见的操作

push() 添加一个新元素到栈顶位置。

pop() 移除栈顶的元素，同时返回被移除的元素。

peek() 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。

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

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

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

4.2 JavaScript 代码实现栈结构

顺序存储

用js内置对象Array实现

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
// 栈结构的封装
class Map {
  constructor() {
    this.items = [];
  }

  // push(item) 压栈操作，往栈里面添加元素
  push(item) {
    this.items.push(item);
  }

  // pop() 出栈操作，从栈中取出元素，并返回取出的那个元素
  pop() {
    return this.items.pop();
  }

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

  // isEmpty() 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

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

  // toString() 返回以字符串形式的栈内元素数据
  toString() {
    let result = "";
    for (let item of this.items) {
      result += item + " ";
    }
    return result;
  }
}

链式存储

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
59
60
61
62
63
64
65
66
67
68
69
function LinkedStack() {
    let Node = function (ele) {
        this.ele = ele;
        this.next = null;
    }

    let length = 0,
        top; //栈顶指针

    //压栈操作
    this.push = function (ele) {
        let node = new Node(ele);
        top ? node.next = top : top = node;
        top = node;
        length++;
        return true;
    }

    //退栈操作
    this.pop = function () {
        let current = top;

        if (top) {
            top = current.next;
            current.next = null;
            length--;
            return current;
        } else {
            return 'null stack';
        }

    }

    this.top = function () {
        return top;
    }
    this.size = function () {
        return length;
    }
    //toString 从栈顶到栈底
    this.toString = function () {
        let string = '';
        current = top;
        while (current) {
            string += current.ele + ' ';
            current = current.next;
        }
        return string;
    }
    this.clear = function () {
        top = null;
        length = 0;
        return true;
    }
}

//使用
let myStack = new LinkedStack();
myStack.push('1')
myStack.push('2')
myStack.push('3')
myStack.push('4')
console.log(myStack.toString()) // 4 3 2 1
myStack.pop()
console.log(myStack.toString()) // 3 2 1
myStack.pop()
myStack.pop()
console.log(myStack.pop()) // Node { ele: '1', next: null }
console.log(myStack.pop()) // null stack

4.3 测试封装的栈结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// push() 测试
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.items); //--> [1, 2, 3]

// pop() 测试
console.log(stack.pop()); //--> 3

// peek() 测试
console.log(stack.peek()); //--> 2

// isEmpty() 测试
console.log(stack.isEmpty()); //--> false

// size() 测试
console.log(stack.size()); //--> 2

// toString() 测试
console.log(stack.toString()); //--> 1 2

五、栈结构的简单应用

5.1 进制转换

利用栈结构的特点封装实现十进制转换为二进制的方法。

原理：

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function dec2bin(dec) {
  // new 一个 Map，保存余数
  const stack = new Map();

  // 当不确定循环次数时，使用 while 循环
  while (dec > 0) {
    // 除二取余法
    stack.push(dec % 2); // 获取余数，放入栈中
    dec = Math.floor(dec / 2); // 除数除以二，向下取整
  }

  let binaryString = "";
  // 不断地从栈中取出元素（0 或 1），并拼接到一起。
  while (!stack.isEmpty()) {
    binaryString += stack.pop();
  }

  return binaryString;
}

测试

1
2
3
// dec2bin() 测试
console.log(dec2bin(100)); //--> 1100100
console.log(dec2bin(88)); //--> 1011000

5.2 进制转换进阶

把十进制转化为任何进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function baseConverter(decNum, base) {	//十进制转换为任意进制		
	var base = (base >= 2 && base <= 16) ? base : 10,
		remStack = new Stack(),
		rem,
		baseStr = '',
		digits = '0123456789ABCDEF';
	while(decNum) {
		rem = Math.floor(decNum % base);
		decNum = Math.floor(decNum / base);
		remStack.push(rem);		//余数放到栈中
	}
	while(!remStack.isEmpty()) {
		baseStr += digits[remStack.pop()];	//利用pop把栈内元素逐一弹出，将余数拼接成为一个字符串
	}
	return baseStr;
}

5.3 用栈判断回文

回文是这样一种现象：一个单词，短语或者数字，从前往后和从后往前写都是一样的。比如单词“dad”，“racecar”就是回文；如果忽略空格和标点符号，下面这个句子也是回文，“A man, a plan, a canal: Panama”，数字1001也是回文。

使用栈可以轻松的判断一个字符是否是回文。我们将拿到的字符串的每个字符按照从左至右的顺序入栈，当所有字符都入栈之后站内就保存了一个反转后的字符串，最后的字符在栈顶，第一个在栈尾。字符串完全压入站内后，通过持续弹出栈中的每个字母就可以的大一个新的字符串，该字符串刚好与原来的字符串顺序相反。我们只要比较这两个字符串即可，如果他们相等就说明这个是一个回文。代码如下：

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
function isPalindrome(word){
    var s = new Stack();
    for (var i=0; i<word.length; ++i) {
        s.push(word[i]);
    }
    var reword = "";
    while(s.length()>0){
        reword += s.pop();
    }
    if(word == reword){
        return true;
    }else{
        return false;
    }    
}

var word = "hello";
if(isPalindrome(word)){
    document.writeln(word + " is a palindrome.");
}else{
    document.writeln(word + " is not a palindrome");
}
word = "racecar";
if(isPalindrome(word)){
    document.writeln(word + " is a palindrome.");
}else{
    document.writeln(word + " is not a palindrome");
}

输出结果如下：

hello is not a palindrome
racecar is a palindrome.

5.4 用栈实现递归

计算阶乘可以使用递归算法，如下：

1
2
3
4
5
6
7
8
function factorial(n) {
    if (n === 0) {
        return 1;
    }
    else {
        return n * factorial(n-1);
    }
}

使用栈来模拟阶乘过程，例如：首先将5到1压入栈内，然后使用给一个循环，将数字一次弹出连乘就得到正确的答案，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
function fact(n){
    var s = new Stack();
    while (n>1){
        s.push(n--);
    }
    var product = 1;
    while (s.length()>0){
        product *= s.pop();
    }
    return product;
}
document.writeln(fact(5)); // 120

5.5 使用栈判断表达式中的括号是否完整

表达式中的{和}，(和)，[和]必须是匹配的，不然的话表达式就会出现语法错误，使用栈可以判断表达式中的括号是否左右匹配。思路是遇到左括号就入栈，遇到右括号就和当前栈顶元素匹配，如果匹配成功就将栈顶元素出栈，最后判断栈中元素个数，如果是0就代表是完整的，否则就是不完整的。代码如下：

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
function isMatch(str){
    var left = "({[";
    var right = ")}]";
    var s = new Stack();
    var i = 0;
    while (str[i]){
        //左符号入栈
        if(left.indexOf(str[i])>-1){
            s.push(str[i])
        }
        //遇到右括号
        else if( right.indexOf(str[i])>-1 && right.indexOf( str[i] ) == left.indexOf( s.peek()) ){
            s.pop();
        }
        i++
    }
    
//    document.writeln( s.peek() );
    if(s.length() == 0){
        document.writeln(str + " is match success");
    }else{
        document.writeln(str + " is not match");
    }
}

isMatch("2.3 + {23 / 12 + (3.14159×0.24)");

Tips: Please indicate the source and original author when reprinting or quoting this article.

特色标签
JavaScript 算法
链友
ESC