栈（Stack）

1. 栈**（Stack）**

认识

栈是一个线性数据结构，遵循后进先出（LIFO，Last In First Out）的原则

JavaScript中没有栈，但是可以用Array实现栈的所有功能。

JS实现

// 数组实现栈数据结构
const stack = []

// 入栈
stack.push(0)
stack.push(1)
stack.push(2)

// 出栈
const popVal = stack.pop() // popVal 为 2

使用场景

• 场景一：十进制转二进制
• 场景二：有效括号
• 场景三：函数调用堆栈

LeetCode题目

● 20 有效括号
● 144 二叉树的前序遍历

特点

1. 后进先出：栈的操作遵循“后进先出”的规则。最新加入栈的元素会最先被移除。
2. 只能在一端操作：栈只有一个端口进行操作，通常是栈顶（Top），也叫栈顶操作。
3. 两种基本操作：
   • push：将元素压入栈中。
   • pop：从栈顶弹出元素。

栈通常用于需要“撤回”或“回溯”的操作场景，例如：浏览器历史记录、撤销操作、递归的实现等。

基本操作

1. push：将元素放入栈中。
2. pop：将栈顶元素移除。
3. peek/top：查看栈顶元素，但不移除。
4. isEmpty：检查栈是否为空。
5. size：获取栈的大小。

栈的实现

在 JavaScript 中，我们可以通过数组来实现栈。数组本身提供了 push() 和 pop() 方法，可以直接用来模拟栈的行为。

class Stack {
  constructor() {
    this.items = []; // 存储栈元素
  }

  // 压入元素
  push(element) {
    this.items.push(element);
  }

  // 弹出栈顶元素
  pop() {
    if (this.isEmpty()) {
      return "栈为空，无法弹出";
    }
    return this.items.pop();
  }

  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return "栈为空";
    }
    return this.items[this.items.length - 1];
  }

  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 获取栈的大小
  size() {
    return this.items.length;
  }
}

// 使用栈
let stack = new Stack();
stack.push(10);  // 压入元素 10
stack.push(20);  // 压入元素 20
console.log(stack.peek());  // 输出栈顶元素: 20
console.log(stack.pop());   // 弹出栈顶元素: 20
console.log(stack.size());  // 输出栈的大小: 1
console.log(stack.isEmpty());  // 输出栈是否为空: false

使用场景

栈的应用非常广泛，特别是在需要反向操作的场合。以下是一些常见的使用场景：

1. 递归调用：递归在计算机内部通常是通过栈来实现的，栈保存了每一层函数的执行状态，调用栈的最后一个元素是当前正在执行的函数。
2. 表达式求值：栈常用于表达式的求值，如中缀表达式转后缀表达式（逆波兰表达式）时，或者是求解括号匹配的问题。
3. 浏览器历史记录：浏览器的“前进”和“后退”按钮实现的就是基于栈的。每当你访问一个新页面时，浏览器会将该页面推入栈中，当你点击“后退”时，栈顶的页面会被弹出。
4. 撤销操作：例如，在文本编辑器中，每当用户执行操作时，都会把这些操作压入栈中。如果用户点击撤销按钮，栈顶的操作就会被弹出，从而恢复之前的状态。
5. 括号匹配：在编程语言的语法分析中，检查括号是否匹配也是栈的一种应用。如果遇到左括号就压栈，遇到右括号就弹栈，最终栈是否为空来判断括号是否匹配。

栈的优缺点

优点：

1. 操作简单：栈的操作非常简单，只涉及到压栈、弹栈和查看栈顶元素等基本操作。
2. 空间高效：栈是一个线性数据结构，使用数组或链表存储数据，不需要额外的空间开销。

缺点：

1. 访问限制：栈只能通过栈顶进行访问，无法直接访问中间的元素，效率较低。
2. 溢出问题：如果栈的容量有限，当栈满时，再执行 push() 操作会导致栈溢出。