数组

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

栈（stack）

  • 它是一种运算受限的线性表,后进先出(LIFO)
  • LIFO(Last In First Out)表示就是后进入的元素, 第一个弹出栈空间. 类似于自动餐托盘, 最后放上的托盘, 往往先把拿出去使用.
  • 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
  • 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
  • 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
    栈结构

生活中的栈结构：

  • 自助餐的托盘, 最新放上去的, 最先被客人拿走使用.
  • 装羽毛球，乒乓球的球筒

程序中的栈结构

  • 函数调用栈：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 压入栈，最后造成栈溢出（Stack Overfloat）

练习题

有 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 出栈。符合入栈顺序；

栈常见的操作

  • push（element）：添加一个新元素到栈顶位置；
  • pop（）：移除栈顶的元素，同时返回被移除的元素；
  • peek（）：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）；
  • isEmpty（）：如果栈里没有任何元素就返回 true，否则返回 false；
  • size（）：返回栈里的元素个数。这个方法和数组的 length 属性类似；
  • toString（）：将栈结构的内容以字符串的形式返回。

栈结构的实现

我们先来创建一个栈的类, 用于封装栈相关的操作

1
2
3
4
5
6
// 栈类
function Stack() {
  // 栈中的属性
  var items = []
  // 栈相关的方法
}

代码解析:

  • 我们创建了一个 Stack 构造函数, 用户创建栈的类.
  • 在构造函数中, 定义了一个变量, 这个变量可以用于保存当前栈对象中所有的元素.
  • 这个变量是一个数组类型. 我们之后无论是压栈操作还是出栈操作, 都是从数组中添加和删除元素.
  • 栈有一些相关的操作方法, 通常无论是什么语言, 操作都是比较类似的.

完整代码

通过 ES5 的实现方式

我们可以使用原型来封装方法，这样效率会更加高！

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
// 封装栈类
function Stack() {
  // 栈中的属性
  this.items = []
  // 栈的相关操作
  // 1.将元素压入栈
  Stack.prototype.push = function (e) {
    this.items.push(e)
  }
  // 2.从栈中取出元素
  Stack.prototype.pop = function () {
    return this.items.pop()
  }
  // 3.查看一下栈顶元素
  Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
  }
  // 4.判断栈是否为空
  Stack.prototype.isEmpty = function () {
    return this.items.length == 0
  }
  // 5.获取栈中元素的个数
  Stack.prototype.size = function () {
    return this.items.length
  }
  // 6.toString方法
  Stack.prototype.toString = function () {
    var resultString = ''
    for (var i = 0; i < this.items.length; i++) {
      resultString += this.items[i] + ' '
    }
    return resultString
  }
}

通过 ES6 的实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
export class Stack {
  constructor() {
    this.items = []
  }
  push(element) {
    this.items.push(element)
  }
  pop() {
    return this.items.pop()
  }
  peek() {
    if (this.items.length === 0) return null
    return this.items[this.items.length - 1]
  }
  isEmpty() {
    return this.items.length === 0
  }
  size() {
    return this.items.length
  }
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 栈的使用
let s = new Stack()
s.push(20)
s.push(10)
s.push(100)
s.push(77)
console.log(s)

console.log(s.pop())
console.log(s.pop())

console.log(s.peek())
console.log(s.isEmpty())

console.log(s.size())
console.log(s.toString())

测试结果

栈结构的应用

我们已经学会了如何使用 Stack 类，现在就用它解决一些计算机科学中的问题。

十进制转二进制

  • 为什么需要十进制转二进制?
    • 现实生活中，我们主要使用十进制。
    • 但在计算科学中，二进制非常重要，因为计算机里的所有内容都是用二进制数字表示的（0 和 1）。
    • 没有十进制和二进制相互转化的能力，与计算机交流就很困难。
  • 如何实现十进制转二进制?
    • 要把十进制转化成二进制，我们可以将该十进制数字和 2 整除（二进制是满二进一），直到结果是 0 为止。
    • 举个例子，把十进制的数字 10 转化成二进制的数字，过程大概是这样：

十进制转换二进制图解

实现代码

ES5 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var s = new Stack()
// 十进制转换二进制函数
function dec2bin(decNum) {
  // 1.定义栈对象
  var stack = new Stack()
  // 2.循环操作
  while (decNum > 0) {
    // 2.1.获取余数放入栈中
    stack.push(decNum % 2)
    // 2.2.获取整除后的结果，作为下一次运行的数字
    decNum = Math.floor(decNum / 2)
  }
  // 3.从数组中取出0和1
  var binaryString = ''
  while (!stack.isEmpty()) {
    binaryString += stack.pop()
  }
  return binaryString
}
//test code
console.log(dec2bin(10))
console.log(dec2bin(100))
console.log(dec2bin(1000))

ES6 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 十进制转换为二进制
export function dec2bin(num) {
  const stack = new Stack()
  // 循环取余数
  while (num > 0) {
    let remainder = num % 2
    num = Math.floor(num / 2)
    stack.push(remainder)
  }
  // 拼接字符串
  let binString = ''
  while (!stack.isEmpty()) {
    binString += stack.pop()
  }
  return binString
}

测试结果

总结

  • 栈结构的特点：后进先出 LIFO (Last In First Out)

  • 常见操作

    • push（element）：添加一个新元素到栈顶位置；
    • pop（）：移除栈顶的元素，同时返回被移除的元素；
    • peek（）：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）；
    • isEmpty（）：如果栈里没有任何元素就返回 true，否则返回 false；
    • size（）：返回栈里的元素个数。这个方法和数组的 length 属性类似；
    • toString（）：将栈结构的内容以字符串的形式返回。