江小鱼

# 栈

静态图片

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

# 栈的特点

栈（stack）,是一种受限的线性表，后进先出（LIFO）

  • 仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，另一端被称为栈底
  • LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间（类似于自动餐托盘，最后放上的托盘，往往先拿出去使用）
  • 向一个栈插入新元素称作进栈（入栈，压栈），它是把新元素放到栈顶元素的上面，使之成为新的顶元素
  • 从一个栈删除元素又被称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

静态图片

栈结构示意图

# 栈结构的一道题目

有六个元素 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

答案是：C

解析

A：6 5 进栈， 5 出栈，4 进栈出栈，3进栈出栈， 6出栈，2 1 进栈， 1出栈， 2出栈

B：6 5 4 进栈，4 出栈， 5 出栈， 3 进栈出栈， 2 进栈出栈， 1 进栈出栈， 6 出栈

D：6 5 4 3 2 进栈， 2 出栈， 3 出栈， 4 出栈， 1 进栈出栈， 5 出栈， 6 出栈

# 基于数组实现栈

  • push(element): 添加一个新元素到栈顶
  • pop(): 移除栈顶的元素，同时返回被移除的元素
  • peek(): 返回栈顶的元素，不对栈做任何修改
  • isEmpty(): 栈里没有任何元素就返回 true, 否则返回 false
  • size() : 返回栈元素的个数
  • toString: 将栈结构的内容以字符形式返回
// 基于数组实现栈结构
class Stack {
    constructor() {
        this.items = []
    }
    // 1、将元素压入栈
    push(element) {
        this.items.push(element)
    }
    // 2、从栈中取元素
    pop(){
        return this.items.pop() // 弹出最后一个元素
    }
    // 3、查看下栈顶元素
    peek() {
        return this.items[this.items.length - 1]
    }
    // 4、判断栈是否为空
    isEmpty() {
        return this.items.length === 0
    }
    // 5、获取栈中元素的个数
    size() {
        return this.items.length
    }
    // 6、toString 方法
    toString() {
        let resultString = ''
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i] + ' '
        }
        return resultString
    }
}
// 栈的使用
let s = new Stack()
s.push(1)
s.push(2)
s.push(100)
s.push(89)
console.log(s, 's')
// s.pop()
console.log(s.peek())
console.log(s.isEmpty())
console.log(s.size())
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

栈-代码实现

# 栈的应用

# 函数调用栈

函数之间相互调用，A中调用B，B中调用C，C中调用D，这样在执行过程中，会先将A压入栈， 在A的执行过程中调用了B，A没有执行完，不会出栈，此时会将B压入栈，此时B在栈顶，A在栈底。 B在执行中调用了C，C会压入栈，C调用了D，D会压入栈,此时D在栈顶。即当前栈的顺序是 (栈底)A->B->C->D(栈顶)。

D执行完会出栈，出栈顺序是D->C->B->A

静态图片

函数调用栈

# 十进制转成二进制

要把十进制转化成二进制，可以将十进制数字和2整除，直到结果是0为止。

  • 原理图：

静态图片

  • 代码实现：
// 十进制转成二进制
function dec2bin (decNumber) {
  // 1.定义一个栈对象
  let stack = new Stack()

  // 2.循环操作
  while(decNumber > 0) {
    // 2.1.获取余数，并且放到栈中
    stack.push(decNumber % 2)
    // 2.2.获取整除后的结果，作为下一次运算的数字
    decNumber = Math.floor(decNumber / 2)
  }
  // 3.栈里存放着结果，取出0和1
  let binaryString = ''
  while(!stack.isEmpty()) {
    binaryString += stack.pop()
  }
  return binaryString
}

console.log(dec2bin(100)) // 1100100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

或者使用 toString() 进行转化

(100).toString(2) // 1100100
1

← 队列 →