数据结构：栈

定义

后进者先出，先进者后出。eg: 平时放餐盘，是从下往上一个个放，然后从上往下一个个取。不会直接从中间抽离一个出来

操作特性

“操作受限”的线性表，只允许在一端插入和删除数据。相比于数据结构：数组和数据结构：链表，更少的操作结构，意味着更加可控，不易出错的状态。

顺序栈：由数组实现的栈

class ArrayStack {
  private items: string[]; // 数组
  private count: number; // 栈中元素的数量
  private n: number; // 栈的大小
 
  // 初始化数组，申请一个大小为 n 的数组空间
  constructor(n: number) {
    this.items = [];
    this.count = 0;
    this.n = n;
  }
 
  // 入栈操作
  push(element: string): boolean {
    // 数组空间不够了，直接返回 false，入栈失败
    if (this.count === this.n) return false;
    // 将 item 放到下标为 count 的位置，并且 count 加一
    this.items[this.count] = element;
    this.count++;
    return true;
  }
 
  // 出栈操作
  pop(): string | null {
    // 栈为空，则直接返回 nukk
    if (this.count === 0) return null;
    // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一
    const tmp = this.items[this.count - 1];
    this.count--;
    return tmp;
  }
}

应用

• 函数调用栈
• 表达式求知
• 括号匹配
• 浏览器的前进后退