队列与链表

队列

🏢 提示

一种受限的线性结构，先进先出(FIFO,first in first out) 它只能在队列的前端(front)进行删除操作,在队列的后端(rear)进行插入操作 应用：

1. 多线程数据共享
2. 算法中会应用->二叉树层序遍历 实现方式：
3. 基于数组
4. 基于链表 —> 会更优

//还要整一个有初始化值的一个可迭代对象
interface IQueue<T=any> {
  enquque(el:T):void
  dequeue():T|undefined
  peek():T|undefined

  isEmpty():boolean
  get size(): number
}

class ArrayQueue<T> implements IQueue {
  private data:T[] = []
  enquque(el: T): void {
    this.data.unshift(el)
  }
  dequeue() {
    return this.data.pop()
  }
  peek() {
   return  this.data[this.data.length-1]
  }
  isEmpty(): boolean {
    return this.data.length>0
  }
  get size(): number {
    return this.data.length
  }
}

1. 约瑟夫环问题

import { ArrayQueue } from '../data_stuct/queue'

function josephus(n:number,m:number){
  const data = new ArrayQueue()
  for (let i = 1; i < n+1; i++) {
    data.enqueue(i)
  }
  while (data.size>1) {
    for (let j = 0; j < m; j++) {
      data.enqueue(data.dequeue())
    }
    // console.log('data.dequeue()', data.dequeue())
    data.dequeue()
  }
  console.log('data.peek()', data.peek())
}

josephus(12,9)

双端队列

循环队列

链表 LinkedList

🏢 提示

链表用于存储一系列的元素，但是实现机制和数组完全不同，链表的每个元素由自身的节点和指向下一个元素的引用（指针）组成 优点：

1. 链表中的元素在内存中不必是连续的内存空间，大小不必在创建时确定，可以无限延伸
2. 插入和删除操作时间复杂度低 O(1) 缺点：
3. 需要从头开始，才能访问任何一个元素（无法跳过第一个元素访问任何元素）
4. 无法通过下标访问元素

1. 基础实现

class LinkedNode<T> {
  next: LinkedNode<T> | null = null
  constructor(public value:T){}
}

class LinkedList<T>{
  head: LinkedNode<T>|null = null
  size = 0
  constructor(){}

  get length(){
    return this.size
  }
  }

1. append方法

 append(value:T){
    const newNode = new LinkedNode(value)
    if(!this.head){
      this.head = newNode
    } else {
      let currentNode = this.head
      while(currentNode.next){
        currentNode = currentNode.next
      }
      currentNode.next = newNode
    }
    this.size++ 

  }

1. insert方法

// 双指针法
insert(value:T,position:number):boolean {
    if(position<0|| position>this.size) return false
    
    const newNode = new LinkedNode(value)
    if(position===0){
      newNode.next = this.head
      this.head = newNode
    }else{
      let current = this.head,previous:LinkedNode<T>|null = null,index = 0
      while(index++<position && current){
        previous = current
        current =current.next
      }
      previous!.next = newNode
      newNode.next = current
    }
    this.size++
    return true
  }

1. getNode

private getNode(position:number): LinkedNode<T> | null{
    let current = this.head,index = 0
    while( index++ < position && current){
      current = current.next
    }
    return current
  }

1. removeAt

removeAt(position:number):LinkedNode<T>|null{
    let deleteNode = this.head
    if(position<0 || position>=this.size || this.head===null ) return deleteNode
    if(position===0){
     this.head = this.head?.next?? null
     deleteNode!.next = null
    } else {
      const tem = this.getNode(position-1)
      deleteNode = tem?.next ?? null
      tem!.next = deleteNode?.next?? null
    }

    this.size--
    return deleteNode
  }

🏢 提示

链表最重要的是分析清楚，每个节点的next指向

双向链表

循环链表

面试题

export class ListNode {
     val: number
     next: ListNode | null
     constructor(val?: number, next?: ListNode | null) {
         this.val = (val===undefined ? 0 : val)
         this.next = (next===undefined ? null : next)
     }
 }

1. 反转链表

LCR 024. 反转链表 - 力扣（LeetCode）

// 1. 循环迭代实现
function reverseList(head: ListNode | null): ListNode | null {
  if(head===null || head.next===null) return head
  let newLink:ListNode| null = null
  while(head){
    const current = head
    head = head?.next
    current.next = newLink
    newLink = current
  }
  return newLink
};
// 2. 递归实现

function reverseList(head: ListNode | null): ListNode | null {
  if(head=== null || head.next === null) return head
  const newNode = reverseList( head.next) // 先递归，然后返回链表的新的头，
  // 然后就不断在递归中传递返回
  head!.next.next = head //这里必须使用 原本的链的节点关系来修改next指向
  head.next = null
  return newNode //返回的始终是最后的节点，也就是新的head
};

1. 删除节点

面试题 02.03. 删除中间节点 - 力扣（LeetCode）

🏢 提示

实现思路： 理解链表的本质，删除节点必须知道要删除节点的前一个节点

1. 如果无法获取前一个节点，那么相当于把链表的后一个节点的值赋值给当前节点，并把当前节点的next指向后第2个节点
2. 也就是说实际上删除了后一个节点，但是把值前移了一位，实现了删除当前节点的功能

function deleteNode(node:ListNode|null){
  if(node?.next){
    node!.val = node.next!.val
    node.next = node.next!.next   
  }
}