数据结构——栈

一、什么是栈结构

1、栈是一种非常常见的数据结构，应用十分广泛

• 数组是一种线性结构，可以在任意位置添加和删除元素
• 栈和队列则是一种受限的线性结构，没有数组的任意性

2、结构示意图

栈结构只能从一端(栈顶)添加和删除元素，遵从后进先出的原则

二、栈的应用

函数调用栈

A调用B，B又调用C，C又调用D

那样在执行的过程中, 会先将A压入栈, A没有执行完, 所有不会弹出栈

在A执行的过程中调用了B, 会将B压入到栈, 这个时候B在栈顶, A在栈底

如果这个时候B可以执行完, 那么B会弹出栈. 但是B有执行完吗? 没有, 它调用了C

所以C会压栈, 并且在栈顶. 而C调用了D, D会压入到栈顶

所以当前的栈顺序是: 栈底A->B->C->D栈顶

D执行完, 弹出栈. C/B/A依次弹出栈.

所以我们有函数调用栈的称呼, 就来自于它们内部的实现机制(通过栈来实现的)

三、栈结构面试题

题目：6个元素6、5、4、3、2、1顺序进栈（不是一次性进栈），哪个是不合法的出栈序列(C)

• 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

四、栈的常见操作

push(element): 添加一个新元素到栈顶位置.

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

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

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

clear()：移除栈里的所有元素。

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

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

五、栈结构的实现

实现栈结构有两种是实现方式：

• 基于数组实现
• 基于链表实现

// 封装一个栈类
function Stack() {
  // 栈中的属性
  this.items = []
  /**
  *  相关操作
  */
  // 1、压栈
  Stack.prototype.push = function (element) {
    this.items.push(element)
  }
  // 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 () {
    let str = ''
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + ' '
    }
    return str
  }
}

// 使用
let s = new Stack()

s.push(20)
s.push(10)
s.push(100)
s.push(4)
console.log(s)  // Stack { items: [ 20, 10, 100, 4 ] }
s.pop()
console.log(s)  // Stack { items: [ 20, 10, 100 ] }
console.log(s.size())  // 3
console.log(s.isEmpty())  // false
console.log(s.toString()) // 20 10 100

六、栈的应用

实现十进制转二进制（使用上述封装的栈方法）

// 封装一个十进制转二进制的方法
function decTobin(decNumber) {
  // 定义一个栈对象保存过程中的余数
  let stack = new Stack()
  // 循环操作
  while (decNumber > 0) {
    // 获取余数存入栈中
    stack.push(decNumber % 2)
    // 获取整除结果作为下次求余的数字
    decNumber = Math.floor(decNumber / 2)
  }
  // 从栈中取出余数就是二进制结果
  let binsryString = ''
  while (!stack.isEmpty()) {
    binsryString += stack.pop()
  }
  return binsryString
}

console.log(decTobin(100))  // 1100100
console.log(decTobin(10))   // 1010
console.log(decTobin(1000)) // 1111101000