数据结构与开发应用之栈

发表于 | 分类于

栈（stack）又名堆栈，是一种遵从后进先出（LIFO）原则的有序集合。新添加的元素都保存在栈的末尾，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

理解栈

栈，要搞清楚这个概念，首先要明白“栈”原来的意思，如此才能把握本质。“栈”者，存储货物或供旅客住宿的地方，可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈顶、栈底如下图所示：

栈顶、栈底示意图

出栈、入栈如下图所示：

出栈、入栈示意图

入栈顺序如下：

1
1 -> 2 -> 3 -> 4

1最先入栈，4最后入栈。

出栈顺序如下：

1
4 -> 3 -> 2 -> 1

4最先出栈，1最后出栈。

栈的实现

基于栈的特性，可以用数组做线性表进行存储。

一个简单的Stack类实现如下：

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
class Stack {
  constructor () {
    this.data = []
  }
  
  push (val) {
    this.data.push(val)
  }
  
  pop () {
    return this.data.pop()
  }
  
  clear () {
    this.data = []
  }
  
  size () {
    return this.data.length
  }
  
  isEmpty () {
    return this.data.length === 0
  }
}

上面Stack类实现了下面的基本功能：

  • push：入栈函数
  • pop：出栈函数
  • clear：清空栈
  • size：获取栈的大小
  • isEmpty：是否为空栈

栈的应用

栈是一种简单的数据结构，和数组结构较为相似，是一种常见且应用广泛的结构。

反转字符串

字符串反转实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function reverse (string) {
  const stack = new Stack()
  
  for (var i = 0, len = string.length; i < len; i++) {
    stack.push(string.charAt(i))
  }

  let result = ''

  while(!stack.isEmpty()) {
    result += stack.pop()
  }
  
  return result
}

测试结果如下：

1
2
3
var str = 'abc';

reverse(str) // => 'cba'

校验字符串中的括号是否合法

有些特殊符号必须成对出现，如：（）、《》、“”等，以括号为例使用栈辅助检验其合法性的步骤如下：

  • 遍历字符串
  • 遇到左括号“(”时，将其压入栈内
  • 遇到右括号“)”时，如果栈为空则不合法返回false，如果栈不为空执行退栈操作
  • 遍历结束后，如果栈为空则合法返回true，反之不合法返回false

校验字符串中的括号是否合法，实现如下

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
function isLegalString (string) {
  const stack = new Stack()
  
  for (var i = 0, len = string.length; i < len; i++) {
    const letter = string.charAt(i)
    
    // 遇到左括号'('时，压栈
    if (letter === '(') {
      stack.push(letter)
    }
    
    // 遇到右括号'('时，如果栈为空则不合法，如果栈不为空则出栈
    if (letter === ')') {
      if (stack.isEmpty()) {
        return false
      } else {
        stack.pop()
      }
    }
  }
  
  // 最后，如果栈为空则合法，反之不合法
  return stack.isEmpty()
}

var a = '()';
var b = '(()';
var c = '(()())';

isLegalString(a) // => true
isLegalString(b) // => false
isLegalString(c) // => true