实现 JavaScript 栈机制

JavaScript 4月前 30

什么是栈数据结构？

栈是保存元素列表的数据结构。栈基于 LIFO 原则（先进后出）工作，这意味着最近添加的元素是第一个要删除的元素。

栈有两个仅在堆栈顶部发生的主要操作：push 和 pop。 push 操作将一个元素放在栈顶，而 pop 操作从栈顶移除一个元素。

为了更好地理解，我们可以将栈视为一组相互堆叠的物理物品（卡片组、书籍），只有一个限制：我们只能从顶部放置或取出物品。

JavaScript 有一种机制，解释器可以跟踪它在调用多个函数的脚本中的位置——当前正在运行什么函数以及从该函数中调用了哪些函数。它被称为Call Stack，它实现了所有的堆栈原则（每当我们调用一个函数时，它都会自动添加到Call Stack的顶部。一旦函数执行完所有代码，它就会自动从 Call Stack 的顶部移除）

让我们实现我们自己的栈

我们将从创建我们的 Stack 类开始

class Stack {
    constructor() {
        this.stackItems = [];
    }
}

我们的 Stack 类将具有以下方法：

push(item) — 将一个项目添加到栈的顶部
pop — 从栈中删除一个元素，如果在空栈上调用该函数，则表示“下溢”
peek — 返回栈顶元素而不将其从栈中移除
isEmpty — 检查栈是否为空
print — 打印所有栈中的元素项

class Stack {
    constructor() {
        this.stackItems = [];
    }
    push(item) {
        this.stackItems.push(item);
    }
    pop() {
        if (this.stackItems.length === 0) {
            return "Underflow";
        }
        return this.stackItems.pop();
    }
    peek() {
        return this.stackItems[this.stackItems.length - 1];
    }
    isEmpty() {
        return this.stackItems.length === 0;
    }
    print() {
        return this.stackItems.join(', ');
    }
}

将栈用于“undo”选项

我们已经实现了自己的栈。现在我们可以将它用于诸如撤消选项之类的事情。

实现撤消方法（以及重做）的常用方法有两种：备忘录模式(Memento Pattern)和命令模式(Command Pattern)。在本文中，我们将使用备忘录模式。

在应用操作之前，我们将当前状态的快照保存到数组中。那个快照就是 备忘录。

如果用户想要撤消，我们只需弹出最后一个备忘录并应用它。程序返回到应用最后一个操作之前的状态。

这种模式在效率方面是有限的。每个备忘录都比较大，因为它捕获了整个当前状态，但它可以用于演示。

带有撤消选项的输入 React 实现

import * as React from "react";
import { Stack } from "./utils/stack";
export const BufferedInput = () => {
  const [value, setValue] = React.useState("");
  const snapshots = React.useRef(new Stack());
  React.useEffect(() => {
    snapshots.current.push(value);
  }, [value]);
  const handleChange = (e) => {
    setValue(e.target.value);
  };
  const undo = () => {
    const previousSnapshot = snapshots.current.pop();
    setValue(previousSnapshot);
  };
  return (
    <div>
      <input type="text" value={value} onChange={handleChange} />
      <button onClick={undo}>Undo</button>
    </div>
  );
};

这个实现会在每个按键上生成输入值的快照，这可能不是那么有用，并且对用户体验也不是很友好，所以让我们使用 debounce 技术对其进行更新：

import * as React from "react";
import debounce from "lodash/debounce";
import { Stack } from "./utils/stack";
export const BufferedInput = () => {
  const [value, setValue] = React.useState("");
  const [debouncedState, setDebouncedState] = React.useState("");
  const snapshots = React.useRef(new Stack());
  React.useEffect(() => {
    snapshots.current.push(value);
  }, [debouncedState]);
  const handleChange = (e) => {
    setValue(e.target.value);
    debouncedSnapshot(e.target.value);
  };
  const debouncedSnapshot = React.useCallback(
    debounce((value) => {
      setDebouncedState(value);
    }, 500),
    []
  );
  const undo = () => {
    setValue(snapshots.current.pop());
  };
  return (
    <div>
      <input type="text" value={value} onChange={handleChange} />
      <button onClick={undo}>Undo</button>
    </div>
  );
};