栈

定义： 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。

举个例子，假设栈S=(a1，a2，a3，…an)，栈中元素按a1，a2，a3，…an的次序压栈，则a1称为栈底元素，an为栈顶元素，弹栈的第一个元素应为栈顶元素。换句话说，栈的修改是按先进后出的原则进行的。

上溢和下溢

当栈满时再压栈会产生空间溢出，简称“上溢”;当栈空时再弹栈也会产生溢出，简称“下溢”。上溢是一种出错状态，应该避免；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。

顺序栈

由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈。可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和弹栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。

初始状态：

由于 JS 中数组可以自动扩容并且对象没有限制，所以以下两种方式实现的栈结构就没有上溢的问题。

完整代码

基于 JS 数组实现
由于原生 JS 数组本就支持栈方法，所以使用数组实现栈很轻松。

class ArrayStack {
  constructor() {
    this.stack = [];
  }
  // 压栈
  push(item) {
    return this.stack.push(item);
  }
  // 弹栈
  pop() {
    return this.stack.pop();
  }
  // 取栈顶元素
  peek() {
    if (this.stack.length >= 1)
      return this.stack[this.stack.length - 1];
  }
  // 清空栈
  clear() {
    this.stack = [];
  }
  // 判断栈是否为空
  isEmpty() {
    return this.stack.length === 0;
  }
}

基于 JS 对象实现
实现思路是每次的栈顶指针的值作为建，数据作为值，压栈后栈顶指针就加一，弹栈后就减一，保证键唯一。

class ObjectStack {
  constructor() {
    this.stack = {};
    this.top = -1;
  }
  // 压栈
  push(item) {
    return this.stack[++this.top] = item;
  }
  // 弹栈
  pop() {
    if (this.top > -1) {
      const res = this.stack[this.top];
      delete this.stack[this.top--]
      return res;
    }
    return null;
  }
  // 取栈顶元素
  peek() {
    if (this.top > -1) {
      return this.stack[this.top];
    }
    return null;
  }
  // 清空栈
  clear() {
    this.stack = {};
    this.top = -1;
  }
  // 判断栈是否为空
  isEmpty() {
    return this.top === -1;
  }
}

链栈

定义： 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作。栈顶指针就是链表的头指针。

压栈

得到如下结果，再弹栈

最后得到如下结果

链栈特点：

• 链式栈无栈满问题，空间可扩充。
• 插入与删除仅在栈顶处执行，链式栈的栈顶在链头。

节点结构

节点结构分为两部分：数据域和指针域，数据域保存数据，指针域保存指向下一节点的指针。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

完整代码

class LinkStack {
  constructor() {
    this.top = null;
    this.count = 0;
  }
  // 压栈
  push(item) {
    const node = new Node(item);
    node.next = this.top;
    this.top = node;
    this.count++;
  }
  // 弹栈
  pop() {
    if (this.count > 0) {
      const res = this.top.value;
      this.top = this.top.next;
      this.count--;
      return res;
    }
    return null;
  }
  // 清空栈
  clear() {
    this.top = null;
    this.count = 0;
  }
  // 取栈顶元素
  peek() {
    if (this.count > 0) {
      return this.top.value;
    }
    return null;
  }
  // 判断栈是否为空
  isEmpty() {
    return this.count === 0;
  }
}

我是孤城浪人，一名正在前端路上摸爬滚打的菜鸟，欢迎你的关注。