A simple double ended queue datastructure
Want to see pretty graphs? Log in now!
npm install dequeue
|81||downloads in the last day|
|1 623||downloads in the last week|
|6 925||downloads in the last month|
|Last Published By|
|Version||1.0.5 last updated 8 months ago|
|Keywords||datastructure, queue, double ended queue, fifo, FIFO, linked list|
|Dependents||frap, log4js-andyliao, log4js-node-andyliao, streamy-data|
A Simple Double Ended Queue Datastructure
Dequeue is implemented as a doubly linked circular list with a titular head
node. By "titular head node", I mean an empty node to designate the beginning
and end of the circularly linked list. I first saw this construction in the
linux kernel source and it seem simple and elegant. I added the
property to use it like I was using an Array.
Example: Dequeue as a replacement for an Array as a FIFO
var Dequeue = require('dequeue') //var fifo =  var fifo = new Dequeue() fifo.length === 0 //=> true fifo.push(d1) fifo.length === 1 //=> true fifo.unshift(d2) fifo.pop() === d1 //=> true fifo.push(d3) fifo.shift() === d2 //=> true fifo.length === 1 //=> true; only d3 is in the dequeue
deque = new Dequeue()
Push a value on the end.
value = deque.pop()
Remove a value off the end.
Push a value on the beginning.
value = deque.shift()
Remove a value off the beginning.
value = deque.last()
Examine the value of the end without removing it.
value = deque.first()
Examine the value of the beginning without removing it.
Remove all entries. This is NOT a test for an empty dequeue; use
Something this simple does not really need a roadmap. However, I am thinking of adding APIs to facilitate walking the Linked List via an iterator. It will be simple and fully backward compatible.