迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 编程语言 >

实现 JavaScript 栈机制

作者:迹忆客 最近更新:2022/06/13 浏览次数:

什么是栈数据结构?

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

栈有两个仅在堆栈顶部发生的主要操作:pushpop。 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>
  );
};

注意💡 :此代码仅用于演示来说明我们的栈的实现。 我不建议在生产环境中使用它。

除非注明转载,本站文章均为原创或翻译,欢迎转载,转载请以链接形式注明出处

本文地址:

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

热门文章

教程更新

热门标签

扫码一下
查看教程更方便