数据结构

栈（stack）

在前端路由中，常用的存储方式是栈(Stack)数据结构。
属于线性数据结构，具有先进后出，后进先出(LIFO)的特点。
只允许在一端进行插入或删除的线性表

使用栈数据结构来存储前端路由信息具有的优点：

• 快速分配和释放内存：由于栈的数据结构特点，分配和释放栈内存的操作非常高效，不会出现内存碎片问题。
• 快速访问：由于栈是一种简单的数据结构，访问和操作栈的速度非常快。
• 可扩展性：栈数据结构可以很容易地扩展到支持浏览器的前进和后退按钮

缺点：

• 有限大小：栈的大小是有限的，当栈空间不够用时会发生栈溢出。
• 局部性：栈上存储的数据只能在局部作用域中访问，不适合存储大量的数据或长期保存的数据。

常见操作

• 初始化一个空栈： 创建一个空数组
• 判断栈：为空返回true，否则返回false
• 进栈(push或unshift)：是元素成为新栈顶
• 出栈(pop或shift)：删除栈顶元素并返回删除的元素

示例：leetcode 503

function nextGreaterElements(nums: number[]): number[] {
  let res = [] 
  const len = nums.length
  let i=0
  while(i< len){
    const num = nums.findIndex(item => item >nums[0])
    const val = num === -1 ? -1 : nums[num]
    res.push(val) 
    nums.push(nums.shift()) // 符合条件就不断把栈顶的元素放在栈底
    i++
  }
  return res
};

堆（Heap）

用于动态内存分配的数据结构，用于存储复杂的数据结构和对象。在堆中分配的内存需要手动进行释放，否则会导致内存泄漏（memory leak）

优点：

• 无序存储：堆中存储的数据是无序的，数据之间的关系由指针来表示
• 动态分配：内存大小是动态分配的，不受限于栈的大小限制，可以存储大量的数据和复杂的数据结构
• 全局性：堆内存中的数据可以在全局作用域中访问，适合存储长期保存的数据和共享数据

缺点：

• 内存泄露：堆内存需要手动管理，如果忘记释放堆内存，会导致内存泄漏
• 分配和释放速度相对较慢：由于堆内存的动态分配和释放需要进行复杂的内存管理操作，分配和释放速度相对较慢。

在 JavaScript 的应用中

• 栈和堆的概念对于理解内存管理和变量存储非常重要。JavaScript 中的基本数据类型（如数字、字符串、布尔值等）通常存储在栈内存中，而复杂的数据结构和对象则存储在堆内存中。在实际开发中，合理地利用栈和堆内存，可以提高程序的性能和内存利用率。

队列（queue）

线性表，具有先进先出(FIFO)
只允许在一端进行插入操作(队尾)，而在另一端进行删除操作的线性表(队头)。

常见操作

• 初始化队列：构造一个空队列Q
• 判断队列： 为空返回true， 否则位false
• 入队(enqueue): 使元素称为新队尾
• 出队(dequeue): 删除对头元素，并返回删除的元素

宏/微任务

宏任务和微任务的区分主要是为了解决js引擎中不同任务之间的执行优先级问题。

宏任务(macrotask)

• setTimeout 和 setInterval 定时器
• DOM 事件处理程序
• AJAX 请求的回调函数
• script 标签的加载和执行

微任务(microtask)

• Promise 的 then 方法和 catch 方法
• async/await 中的 await 表达式
• MutationObserver 监听器
• js 引擎会将微任务和宏任务添加到任务队列中，但是微任务的执行在当前宏任务执行结束后立即进行，也就是说微任务具有更高的执行优先级，可以优先于下一个宏任务。宏任务的执行是当前任务执行完毕后按照顺序执行