首页 > 其他分享 >[Typescript] Queue

[Typescript] Queue

时间:2023-07-19 14:44:40浏览次数:39  
标签:head Typescript toEqual list Queue tail expect

Using Linked list to implement a Queue.

In javascript, if you want to push a item in front of an Array, it need to shift the rest of items, not good for performance. Using Linked List is O(1) oepration for enque and deque,  which is better.

Usecase: Let's say you want to keep at most 20 items, can use a Queue

type Node<T> = {
    value: T;
    next?: Node<T>;
};

// use a linked list to implement a queue
export default class Queue<T> {
    public length: number;
    private head?: Node<T>;
    private tail?: Node<T>;

    constructor() {
        this.length = 0;
        this.head = this.tail = undefined;
    }

    enqueue(item: T): void {
        const node = { value: item };
        this.length++;
        if (!this.tail) {
            this.head = this.tail = node;
            return;
        }

        this.tail.next = node;
        this.tail = node;
    }

    deque(): T | undefined {
        if (!this.head) {
            return undefined;
        }

        this.length--;
        const head = this.head;
        this.head = this.head.next;

        // free up memory
        head.next = undefined;

        // clean up tail
        if (this.length === 0) {
            this.tail = undefined;
        }

        return head.value;
    }

    peek(): T | undefined {
        return this.head?.value;
    }
}

 

Test:

import Queue from "@code/Queue";

test("queue", function () {
    const list = new Queue<number>();

    list.enqueue(5);
    list.enqueue(7);
    list.enqueue(9);

    expect(list.deque()).toEqual(5);
    expect(list.length).toEqual(2);

    // this must be wrong..?
    debugger;

    // i hate using debuggers
    list.enqueue(11);
    debugger;
    expect(list.deque()).toEqual(7);
    expect(list.deque()).toEqual(9);
    expect(list.peek()).toEqual(11);
    expect(list.deque()).toEqual(11);
    expect(list.deque()).toEqual(undefined);
    expect(list.length).toEqual(0);

    // just wanted to make sure that I could not blow up myself when i remove
    // everything
    list.enqueue(69);
    expect(list.peek()).toEqual(69);
    expect(list.length).toEqual(1);
});

 

标签:head,Typescript,toEqual,list,Queue,tail,expect
From: https://www.cnblogs.com/Answer1215/p/17565515.html

相关文章

  • 54.使用VUE3+VITE+TYPESCRIPT+element-plus的setup语法糖,实现导出excel功能
    要实现导出Excel功能,你可以使用以下步骤:1.安装相关依赖:```bashnpminstallxlsxfile-saver```2.在你的组件中引入相关依赖:```javascriptimport{ref}from'vue';import{saveAs}from'file-saver';import{useTable}from'element-plus';importXLSX......
  • [Typescript] 150 Hard - OptionalUndefined
    Implementtheutiltype OptionalUndefined<T,Props> thatturnsallthepropertiesof T thatcanbe undefined,intooptionalproperties.Inaddition,asecond-optional-generic Props canbepassedtorestrictthepropertiesthatcanbealtered.Opti......
  • [Typescript] 149 Medium - Triangular number
    GivenanumberN,findtheNthtriangularnumber,i.e. 1+2+3+...+N/*_____________YourCodeHere_____________*/exporttypeNumberToArray<Textendsnumber,Rextends1[]=[]>=R["length"]extendsT?R:NumberToArray&......
  • [Typescript Challenge] 148 Medium - CartesianProduct
    Given2sets(unions),returnitsCartesianproductinasetoftuples,e.g.CartesianProduct<1|2,'a'|'b'>//[1,'a']|[2,'a']|[1,'b']|[2,'b'] Solution:/*____________......
  • 记录--盘点 TypeScript 那些奇怪的符号
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助TypeScript是一种由微软开发的自由和开源的编程语言。它是JavaScript的一个超集,而且本质上向这个语言添加了可选的静态类型和基于类的面向对象编程。一、!非空断言操作符在上下文中当类型检查器无法断定类型时,一......
  • 2023.7.16 linux 软中断Softirqs 队列 Workqueues 并发管理队列cmwq
    Implementingwork-deferringmechanisms 延期任务Softirqs:Executedinanatomiccontext # kernel/softirq.c ;<linux/interrupt.h>.Tasklets:Executedinanatomiccontext Workqueues:Executedinaprocesscontext structsoftirq......
  • Typescript学习笔记总结
    Typescript是一种由微软开发的开源编程语言,它是JavaScript的超集,意味着它包含了JavaScript的所有特性,同时还提供了一些额外的功能和类型检查。Typescript的目标是提高JavaScript代码的可读性、可维护性和可扩展性,同时还能够在编译时检测出一些常见的错误。在本文中,我们将详细介绍Ty......
  • 揭秘 .NET 中的 TimerQueue(上)
    前言TimerQueue是.NET中实现定时任务的核心组件,它是一个定时任务的管理器,负责存储和调度定时任务。它被用于实现很多.NET中的定时任务,比如System.Threading.Timer、Task.Delay、CancellationTokenSource等。笔者将用两篇文章为大家介绍TimerQueue的实现原理,本篇文章将以......
  • typescript 中严格字面量类型检查的理解
    个人关于TS中Strictobjectliteralassignmentchecking的理解StrictobjectliteralassignmentcheckingStrictobjectliteralassignmentcheckingbyahejlsberg·PullRequest#3823·microsoft/TypeScript案例interfaceIStudent{name:stringid:strin......
  • 安装CentOS出现dracut-initqueue timeout
    报错信息如图: 解决方法:cddevls|grepsd在这里找到你U盘系统挂载点,看sd后面带数字的PS:或者先插着U盘执行下ls,再拔掉U盘执行ls,看上下两个显示对比缺少哪个,也是看带数字的,记下这个U盘名字,填写到下方【你U盘名字】>dracut:/#reboot执行重启命令重启之后,在ins......