栈

栈数据结构

栈是一种遵从后进先出原则的有序集合. 新添加的或待删除的元素都保存在栈的同一端, 称作栈顶, 另一端就叫栈底. 在栈里, 新元素都靠近栈底, 旧元素都接近栈底.

生活中栈的例子: 一摞书, 堆放的盘子.

栈也被用在编程语言的编译器和内存中保存变量,方法调用等.

创建栈

创建一个类来表示栈. 先声明这个类:

function Stack() {
  // 各种属性和方法的声明
}

使用数组数据结构来保存栈里的元素

let items = []

声明栈的方法

push(element(s)): 添加一个(或几个)新元素到栈顶

pop(): 移除栈顶的元素, 同时返回被移除的元素

peek(): 返回栈顶的元素, 不对栈做任何修改 (这个方法不会移除栈顶元素, 仅仅返回它)

isEmpty(): 如果战力没有任何元素就返回 true, 否则返回 false

clear(): 移除栈里所有元素

size(): 返回栈里元素个数. 和数组 length 属性类似

向栈添加元素

push 方法向栈里添加新元素, 只添加元素到栈顶, 也就是栈的末尾

this.push = function (element) {
  items.push(element)
}

从栈移除元素

pop 方法用来移除栈里的元素. 栈遵从 LIFO 原则, 因此移出的是最后添加进去的元素

  this.pop = function () {
    return item.pop()
  }

只能用 push 和 pop 方法添加和删除栈中的元素, 栈自然就遵从了 LIFO 原则

查看栈顶元素

peek 方法返回栈顶元素

  this.peek = function () {
    return items[items.length - 1]
  }

检查栈是否为空

isEmpty 如果栈为空返回 true, 否则返回 false. 因为栈内部使用数组保存元素, 所以能简单地返回栈的长度

  this.isEmpty = function () {
    return items.length == 0
  }

清空栈元素

clear 方法用来移除栈里所有元素. 也可以多次调用 pop 方法, 把数组中的元素全部移除, 这样也能实现 clear 方法

  this.clear = function () {
    items = []
  }

打印栈元素

print 方法把栈里的所有元素都输出到控制台

  this.print = function () {
    console.log(items.toString())
  }

使用 Stack 类

function Stack() {
  let items = []

  this.push = function (element) {
    items.push(element)
  }

  this.pop = function () {
    return items.pop()
  }

  this.peek = function () {
    return items[items.length - 1]
  }

  this.isEmpty = function () {
    return items.length == 0
  }

  this.size = function () {
    return items.length
  }

  this.clear = function () {
    items = []
  }

  this.print = function () {
    console.log(items)
    // console.log(items.toString()) 
  }

}

let stack = new Stack()
console.log(stack.isEmpty()) // true

stack.push(5)
stack.push(8)

// 8 是栈里最后添加的一个元素
console.log(stack.peek()) // 8

stack.push(11)
console.log(stack.size())  // 3
console.log(stack.isEmpty()) // false

stack.push(15)

// 调用两次 pop 移除两个元素
stack.pop()
stack.pop()
console.log(stack.size()) // 2
stack.print() // [5,8]

ECMAScript 和 Stack 类

用 ES6 语法声明 Stack 类

class Stack {
  constructor () {
    this.items = []
  }
  push (element) {
    this.items.push(element)
  }
}

在类的其他函数里使用 this.nameofVariable 就可以引用这个变量

1. 用 ES6 的限定作用域 Symbol 实现类

ES6 新增了一种叫做 Symbol 的基本类型, 它是不可变的, 可以用作对象的属性.

let _items= Symbol()

class Stack {
  constructor () {
    this[_items] = []
  }
  push (element) {
    this[_items].push(element)
  }

  pop () {
    return this[_items].pop()
  }

  peek () {
    return this[_items][this[_items].length - 1]
  }

  isEmpty () {
    return this[_items].length == 0
  }

  size () {
    return this[_items].length
  }

  clear () {
    this[_items] = []
  }

  print () {
    console.log(this[_items])
    // console.log(this[_items].toString()) 
  }
}

上面代码中声明了 Symbol 类型的变量 _items , 在类的 constructor 函数中初始化它的值. 要访问 _items, 只需把所有的 this.items 都换成 this[_items]

这种方法创建了一个假的私有属性, 因为 ES6 新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性. 下面是一个破坏 Stack 类的例子

let stack = new Stack()
stack.push(5)
stack.push(8)
let objectSymbols = Object.getOwnPropertySymbols(stack)
console.log(objectSymbols.length) // 1
console.log(objectSymbols) // [ Symbol() ]
console.log(objectSymbols[0]) // Symbol()
stack[objectSymbols[0]].push(1) 
stack.print() // [ 5, 8, 1 ]

2.用ES6的WeakMap实现类

WeakMap 数据类型可以确保属性私有, WeakMap 可以存储键值对,其中键是对象,值可以是任意数据类型.

用 WeakMap 来存储 items 变量, Stack 类如下

const items = new WeakMap() // {1}

class Stack{
  constructor() {
    items.set(this, []) // {2}
  }
  push(element) {
    let s = items.get(this) // {3}
    s.push(element)
  }
  pop() {
    let s = items.get(this)
    let r = s.pop()
    return r
  }
  // 其他方法
}

行 {1}, 声明一个 WeakMap 类型的变量 items.

行 {2}, 在 constructor 中, 以 this (Stack 类自己的引用) 为键, 把代表栈的数组存入 items.

行 {3}, 从 WeakMap 中取值, 即以 this 为键 (行{2}设置的)从 items 中取值.

现在 items 在 Stack 类里是真正的私有属性了, 还有一件事情要做, items 现在仍然是在 Stack 类以外声明的, 因此谁都可以改动它. 我们要用一个闭包 (外层函数) 把 Stack 类包起来, 这样就只能在这个函数里访问 WeakMap:

let Stack = (function () {
  const items = new WeakMap() // {1}

  class Stack{
    constructor() {
      items.set(this, []) // {2}
    }
    push(element) {
      let s = items.get(this) // {3}
      s.push(element)
    }
    pop() {
      let s = items.get(this)
      let r = s.pop()
      return r
    }
    // 其他方法
  }
  return Stack // {5}
})()

当 Stack 函数里面的构造函数被调用时, 会返回 Stack 类的一个实例 (行{5})

3.3 用栈解决问题

从十进制到二进制

把十进制转化成二进制, 可以将十进制数字和2整除(二进制是满二进一), 知道结果为0为止. 把十进制的数字10转化成二进制的数字,过程如下

算法描述

function divideBy2(decNumber) {
  let remStack = new Stack()
  let rem = null
  let binaryString = ''

  while (decNumber > 0) { // {1}
    rem = Math.floor(decNumber % 2)  // {2}
    remStack.push(rem)  // {3}
    decNumber = Math.floor(decNumber / 2)  // {4}
  }

  while (!remStack.isEmpty()) {  // {5}
    binaryString += remStack.pop().toString()
  }

  return binaryString
}

console.log(divideBy2(10)) // 1010

当结果满足和2做整除的条件时 (行{1}) , 会获得当前结果和2的余数,放到栈里(行{2}, {3}). 让结果和2做整除(行 {4}). 注意: JavaScript 有数字类型, 但是它不会区分究竟是整数还是浮点数. 因此, 要使用 Math.floor 函数让除法的操作仅返回整数部分. 最后, 用 pop 方法把栈中的元素都移除, 把出栈的元素变成连接字符串 (行{5})

进制转化算法

很容易修改之前的算法, 使之能把十进制转换成任何进制.除了让十进制数字和2整除转成二进制数,还可以传入其他任意进制的基数为参数, 算法如下:

function baseConverter(decNumber, base) {
  let remStack = new Stack()
  let rem = null
  let baseString = ''
  let digits = '0123456789ABCDEF' // {6}

  while (decNumber > 0) {
    rem = Math.floor(decNumber % base)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / base)
  }

  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()] // {7}
  }

  return baseString
}

console.log(baseConverter(10, 2)) // 1010
console.log(baseConverter(11, 2)) // 1011

只需要修改一个地方. 在将十进制转换成二进制时, 余数是0和1;在将十进制转成八进制时,余数是0和7之间的数; 但是将十进制转换成16进制时, 余数是0到9之间的数字加上 A, B, C, D, E 和 F (对应10, 11, 12, 13, 14 和 15). 因此, 对栈中的数字做个转化即可(行 {6} 和 行 {7}) .