数据结构	是否为线性结构
数组（Array）	是
链表（LinkedList）	是
栈（Stack）	受限的
队列（Queue）	受限的

一、数组

1、认知

  数组（Array）是几乎每种编程语言都会提供的一种原生的数据结构（语言自带）。

  并且，我们可以借助数组结构来实现其他的数据结构，如：

• 栈（Stack）
• 队列（Queue）
• 堆（Heap）
• ……

2、特点

  通常数组的内存是连续的，所以在知道下标值的情况下，查找、删除效率是非常高的。

  通过上图，我们可以知道在数组中插入操作的效率并不高

JavaScript 中为我们提供了封装好的 splice()方法供我们方便的进行插入操作，更多数组方法可以查阅：MDN-Array (opens new window)

3、栈和队列

  数组、链表是一种线性结构，而栈、队列称为受限制的线性结构，因为后者对某些操作进行了一些限制

比如：不能在任意位置进行插入和删除操作

提示

  栈 和 队列的实现，我们可以采用数组 和 链表两种方案。以下是推荐的方式：

• 栈：数组方式实现
• 队列：链表方式实现

二、栈结构

参考：https://www.raulmelo.me/en/blog/data-structure-in-javascript-stack

1、图示

  特点：后进先出

2、栈定义

方法	描述		方法	描述
push	尾部添加		peek	尾部 element
pop	尾部删除		isEmpty	栈内是否为空
			size	栈内元素个数
			clear	清空栈内元素

import { IStack } from '../types/IList'
// 定义
class ArrayStack<T> implements IStack<T> {
  private data: T[] = []

  push(element: T): void {
    this.data.push(element) // 末尾追加
  }

  pop(): T | undefined {
    return this.data.pop() // 末尾删除
  }

  peek(): T | undefined {
    return this.data[this.data.length - 1] // 末尾element
  }

  get length(): number {
    return this.data.length
  }

  isEmpty(): boolean {
    return this.data.length === 0
  }

  clear(): void {
    this.data = []
  }
}

export default ArrayStack

3、练习：有效的括号

LeetCode：有效的括号 (opens new window)

function isValid(s: string): boolean {
  const stack: string[] = []

  for (let i = 0; i < s.length; i++) {
    const chat = s[i]
    switch (chat) {
      case '(':
        stack.push(')')
        break
      case '[':
        stack.push(']')
        break
      case '{':
        stack.push('}')
        break
      default:
        if (chat !== stack.pop()) return false
    }
  }
  return stack.length == 0
}

三、队列结构

参考：https://dmitripavlutin.com/javascript-queue/

1、图示

  特点：先进先出

2、队列定义

方法	描述		方法	描述
enqueue	尾部添加		peek	头部查看
dequeue	头部删除		isEmpty	栈内是否为空
			size	栈内元素个数
			clear	清空栈内元素

import { IQueue } from '../types/IList'
// 定义
class ArrayQueue<T> implements IQueue<T> {
  private data: T[] = []

  enqueue(element: T): void {
    this.data.push(element) // 末尾追加
  }

  dequeue(): T | undefined {
    return this.data.shift() // 头部删除
  }

  peek(): T | undefined {
    return this.data[0] // 头部element
  }

  get length(): number {
    return this.data.length
  }

  isEmpty(): boolean {
    return this.data.length === 0
  }

  clear(): void {
    this.data = []
  }
}

export default ArrayQueue

3、练习：约瑟夫环

剑指 Offer 62：圆圈中最后剩下的数字 (opens new window)

提示

  虽然这里使用队列可以解决问题，但当 num 过大时，性能消耗会非常大。

使用动态规划会更好一点。

动态规划解决

function iceBreakingGame(num: number, target: number): number {
  let position = 0

  for (let i = 2; i <= num; i++) {
    position = (position + target) % i
  }

  return position
}

function iceBreakingGame(num: number, target: number): number {
  const queue: number[] = []

  for (let i = 0; i < num; i++) {
    queue.push(i)
  }

  while (queue.length > 1) {
    for (let i = 1; i < target; i++) {
      queue.push(queue.shift())
    }
    queue.shift()
  }

  return queue.shift()! // 返回索引值
}

三、高阶队列

1、双端队列

  双端队列（Double-ended queue (opens new window)）：允许在队列的两端添加（入队）和删除（出队）元素

LeetCode：滑动窗口最大值 (opens new window)

  图示：

import ArrayQueue from './ArrayQueue'

// 定义
class ArrayEnqueue<T> extends ArrayQueue<T> {
  addFront(element: T) {
    this.data.unshift(element)
  }
  removeBack(): T | undefined {
    return this.data.pop()
  }
}

export default ArrayEnqueue

2、优先级队列

  优先级队列（priority queue）：赋予每个元素一个优先权

  最为便利、高效的就是使用 堆 来进行实现：

import BinaryHeap from '../06_Heap/BinaryHeap'

class PriorityQueue<T> {
  private heap: BinaryHeap<T> = new BinaryHeap()

  enqueue(element: T): void {
    this.heap.insert(element) // 末尾追加
  }

  dequeue(): T | undefined {
    return this.heap.extractMax() // 头部删除
  }

  peek(): T | undefined {
    return this.heap.getMax() // 头部element
  }

  get length(): number {
    return this.heap.size
  }

  isEmpty(): boolean {
    return this.heap.isEmmpty()
  }
}

export default PriorityQueue