JS-Circular-Deque

A Preload-Based Circular Deque Class in JavaScript.

Github Repo | npm package
Language: en | zh-cn
License: MIT license

Principle

The queue is stored in a circular fashion, maintaining both front and back pointers.

When the queue runs out of space, it resizes to $1.75$ times its original size and copies the queue.

Usage

Installing and Importing the Module

npm install circular-deque

const deque = require('circular-deque');

Creating an Object | constructor()

const t = new deque();   // #1
const t = new deque(10); // #2

Method #1: Does not pre-allocate length.
Method #2: Pre-allocates a length of length as needed by the program.

Getting Front/Back Elements | front() & back()

let x = t.front();
let x = t.back();

Time Complexity: $O(1)$.

Inserting Elements at the Front/Back | push_front() & push_back()

t.push_front(x);
t.push_back(x);

Time Complexity: Most of the time $O(1)$, worst case $O(\text{length})$ (when resizing is needed).

Popping Elements from the Front/Back | pop_front() & pop_back()

t.pop_front();
t.pop_back();

Time Complexity: $O(1)$.

Function Aliases

push_back  <= enqueue | push | pushBack
pop_front  <= dequeue | pop | popFront
pop_back   <= popBack
push_front <= pushFront

Previous Versions

v0.9.0

1. [x] Added README documentation.
2. [x] Optimized pop operation to reduce space overhead.

Development Plan

1. [ ] Optimize parameters based on data structure performance.
2. [ ] Check for memory leaks.