tiny-linked-queue

tiny-linked-queue

Introduction

A tiny queue(first-in, first-out) implemented by linked-list.

Movitation

enqueue and dequeue operation implemented by linked-list has O(1) time-complex, faster than Array.prototype.shift which costs O(n).

Usage

npm install -D tiny-linked-queue

const Qeueue = require('tiny-linked-queue')
const q = new Qeueue()

q.enqueue('foo')
q.enqueue('bar')
q.enqueue('baz')

q.dequeue() // => 'foo'
q.dequeue() // => 'bar'
q.dequeue() // => 'baz'

API

declare class Queue<ValueType> {
    /**
     * size of the queue.
     */
    readonly size: number;
    /**
     * check the queue is empty.
     */
    readonly isEmpty: boolean;
    /**
     * return the first element of the queue.
     */
    readonly head: ValueType | undefined;
    /**
     * return the last element of the queue.
     */
    readonly tail: ValueType | undefined;
    /**
     * constructor.
     */
    constructor();
    /**
     * enqueue.
     */
    enqueue(value: ValueType): void;
    /**
     * dequeue.
     */
    dequeue(): ValueType | undefined;
    /**
     * clear the queue.
     */
    clear(): void;
}

export = Queue;

Performace

node performance.js

sample output:

testing performance between linked-queue and native-array, 
by execute one hundred thousand enqueue and dequeue operation
    
...
    
native-array costs:
11388 ms
linked-queue costs:
19 ms

Tests

yarn test