• 数据结构之数组
• 数据结构之队列
• 数据结构之栈
• 数据结构之链表
• 数据结构之树
• 数据结构之图

栈是一种后进先出（LIFO）的有序的数据结构，新元素在栈顶，旧元素在栈底。可以利用数组来创建栈。

栈需要 push（插入栈顶）、pop（移除栈顶）、peek（返回栈顶）、isEmpty（查看栈是否为空）、clear（移除栈所有元素）、size（返回栈元素个数）、print（输出栈所有元素）等方法。

function Stack() {let items = []
  this.push = function(elem) {items.push(elem)
  }
  this.pop = function() {return items.pop()
  }
  this.peek = function() {return items[items.length - 1]
  }
  this.isEmpty = function() {return items.length === 0}
  this.clear = function() {items = []
  }
  this.size = function() {return items.length}
  this.print = function() {console.log(items.toString())
  }
}

let stack = new Stack()

这个 Stack 类声明了一个 items 私有变量，保证外界不能访问到 items（只能由 Stack 函数本身访问，所有实例都不能访问，因为 items 实际上是数组，如果外界能不通过我们定义的方法，直接拿到 items，那么实际上就破坏了栈，能用数组的方法操作 items。类的方法会给每个实例添加 items 副本，如果要创建多个 Stack 实例，无疑是不利于性能的。

利用 ES6 可以创造类，ES6 的类基于原型，虽然比基于函数更节省内存，也更适合创建多个实例，但是所有属性都是声明在类中的 constructor 中，且不能声明私有属性，那无疑对栈的结构产生巨大威胁，外界可以直接读出本质上是数组的 items。

可以利用 WeakMap 结构，结合 ES6 以及闭包，创建既适合创建多个实例，也足够安全（外界无法访问 items 私有变量）的栈：

let Stack = (function() {
  // 利用闭包，外界无法访问 items
  const items = new WeakMap() //items 是一个 WeakMap 数据结构，不再是数组
  class Stack {constructor() {items.set(this, []) // 将 this（Stack 类本身）映射成一个数组
    }
    push(elem) {let s = items.get(this) // 利用 WeakMap 的 get，拿到映射的值（数组）
      s.push(elem)
    }
    pop() {let s = items.get(this)
      return s.pop() }
    peek() {let s = items.get(this)
      return s[s.length - 1]
    }
    isEmpty() {let s = items.get(this)
      return s.length === 0
    }
    clear() {items.set(this, [])
    }
    size() {let s = items.get(this)
      return s.length
    }
    print() {let s = items.get(this)
      console.log(s.toString())
    }
  }
  return Stack // 当构造函数被调用，返回一个类的实例
})()let stack = new Stack()

应用与算法

1. 回溯问题，如存储访问过的任务或路径，撤销的操作等。在 JAVA 和 C# 中用栈来存储变量和方法调用。
2. 进制转换问题
3. 平衡圆括号问题
4. 汉诺塔问题