数据结构 是否为线性结构
数组(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
更新于 : 7/8/2024, 10:21:14 AM