TS实现队列

接口IList.ts

interface IList<T> {
    isEmpty(): boolean
    size(): number
    peek(): T | undefined
}

export default IList

接口IQueue.ts

import IList from "../types/IList"

interface IQueue<T> extends IList<T> {
    enqueue(item: T): void
    dequeue(): T | undefined
}

export default IQueue

数组实现队列

import IQueue from "./IQueue";

class ArrayQueue<T> implements IQueue<T> {
    private arr: T[] = [];

    enqueue(item: T): void {
        this.arr.push(item)
    }
    dequeue(): T | undefined {
        return this.arr.shift()
    }
    peek(): T | undefined {
        return this.arr[0]
    }
    isEmpty(): boolean {
        return this.arr.length === 0
    }
    size(): number {
        return this.arr.length
    }
   
}

export default ArrayQueue

实例

击鼓传花

import ArrayQueue from "./01_实现队列结构Queue";

function hotPotato(names: string[], num: number): string {
    // 1.创建队列结构
    const queue = new ArrayQueue<string>();

    // 2.循环添加元素
    for (const name of names) {
        queue.enqueue(name);
    }

    // 3.遍历队列
    while (queue.size() > 1) {
        for (let i = 1; i < num; i++) {
            queue.enqueue((queue.dequeue() as string));
        }
        queue.dequeue();
    }
    return queue.dequeue() as string;
}


const names = ["zhangsan","lisi","wangwu","zhaoliu"];
console.log(hotPotato(names, 3));

输出

zhangsan

约瑟夫环

剑指 Offer 62. 圆圈中最后剩下的数字 - 力扣（LeetCode）

动态规划实现

function lastRemaining(n: number, m: number): number {
    let position = 0;

    for(let i = 2; i <= n; i++) {
        position = (position + m) % i;
    }
    return position;
};


console.log(lastRemaining(5, 3));

输出

3