Circular buffer in JavaScript

Question

Has anyone already implemented a circular buffer in JavaScript? How would you do that without having pointers?

Glaydsglaze

You probably should clarify "circular buffer". What sort of API interests you? What goes in the buffer? etc etc – Cursor

Ideally the API would consist of: push ( key, value ) get ( key ) and when the buffer has reached its maximum size the first saved item is overwritten. – Glaydsglaze

Shameless self plug: If you are looking for a rotating node.js buffer, I wrote one that can be found here: npmjs.org/packages/pivot-buffer Documentation is currently lacking, but RotatingBuffer#push allows you to append a buffer to the current buffer, rotating the previous data if new length is greater than the length specified in the constructor. – Periostitis

Answer 1

Strange co-incidence, I just wrote one earlier today! I don't know what exactly your requirements are but this might be of use.

It presents an interface like an Array of unlimited length, but ‘forgets’ old items:

// Circular buffer storage. Externally-apparent 'length' increases indefinitely
// while any items with indexes below length-n will be forgotten (undefined
// will be returned if you try to get them, trying to set is an exception).
// n represents the initial length of the array, not a maximum
function CircularBuffer(n) {
    this._array= new Array(n);
    this.length= 0;
}
CircularBuffer.prototype.toString= function() {
    return '[object CircularBuffer('+this._array.length+') length '+this.length+']';
};
CircularBuffer.prototype.get= function(i) {
    if (i<0 || i<this.length-this._array.length)
        return undefined;
    return this._array[i%this._array.length];
};
CircularBuffer.prototype.set= function(i, v) {
    if (i<0 || i<this.length-this._array.length)
        throw CircularBuffer.IndexError;
    while (i>this.length) {
        this._array[this.length%this._array.length]= undefined;
        this.length++;
    }
    this._array[i%this._array.length]= v;
    if (i==this.length)
        this.length++;
};
CircularBuffer.IndexError= {};

Ecklund

Nice. I added push: CircularBuffer.prototype.push = function(v) { this._array[this.length%this._array.length] = v; this.length++; }; – Amnesia

"Indefinetely" as in 1.7976931348623157e+308, which in turn exceeding means somewhen Infinity. +1 – Moise

It will only work up to Number_MAX_SAFE_INTEGER, or 2^53 - 1. This is because Number_MAX_SAFE_INTEGER + 1 is equal to Number_MAX_SAFE_INTEGER + 2. Still a really big number, almost 10 quintillion! Source: MDN – Waggon

Answer 2

var createRingBuffer = function(length){

  var pointer = 0, buffer = []; 

  return {
    get  : function(key){return buffer[key];},
    push : function(item){
      buffer[pointer] = item;
      pointer = (length + pointer +1) % length;
    }
  };
};

Update: in case you fill the buffer with numbers only, here are some one liner plugins:

min  : function(){return Math.min.apply(Math, buffer);},
sum  : function(){return buffer.reduce(function(a, b){ return a + b; }, 0);},

Spelunker

why do you have pointer = (length + pointer +1) % length instead of just pointer = (pointer + 1) % length? – Soult

Change get function to get : function(key){ if (key < 0){ return buffer[pointer+key]; } else if (key === false){ return buffer[pointer - 1]; } else{ return buffer[key]; } }, to support negative indexing (from right) and default to last thing pushed if no key is given. – Archer

Actually I ended up adding a couple other niceties to this so I submitted a variant answer. – Archer

Answer 3

Like many others, I liked noiv's solution, but I wanted a somewhat nicer API:

var createRingBuffer = function(length){
  /* https://stackoverflow.com/a/4774081 */
  var pointer = 0, buffer = []; 

  return {
    get  : function(key){
        if (key < 0){
            return buffer[pointer+key];
        } else if (key === false){
            return buffer[pointer - 1];
        } else{
            return buffer[key];
        }
    },
    push : function(item){
      buffer[pointer] = item;
      pointer = (pointer + 1) % length;
      return item;
    },
    prev : function(){
        var tmp_pointer = (pointer - 1) % length;
        if (buffer[tmp_pointer]){
            pointer = tmp_pointer;
            return buffer[pointer];
        }
    },
    next : function(){
        if (buffer[pointer]){
            pointer = (pointer + 1) % length;
            return buffer[pointer];
        }
    }
  };
};

Improvements over original:

• get supports default argument (returns last item pushed onto buffer)
• get supports negative indexing (counts from right)
• prev moves buffer back one and returns what's there (like popping without delete)
• next undoes prev (moves buffer forward and returns it)

I used this to store a command history which I could then flip through in an app using its prev and next methods, which nicely return undefined when they have nowhere to go.

Archer

.get() will always fail unless you replace === false with === undefined. .get() will return undefined when buffer is full. .get(-n) will return undefined when buffer is full. e.g. r = createRingBuffer(2); r.push(1); r.push(2); r.get(-1) – Pylle

Answer 4

Almost 10 years later, an answer using JavaScript ES6:

    class CircularBuffer {
      constructor(bufferLength) {
        this.buffer = [];
        this.pointer = 0;
        this.bufferLength = bufferLength;
      }
      
      push(element) {
        if(this.buffer.length === this.bufferLength) {
           this.buffer[this.pointer] = element;
        } else {
           this.buffer.push(element);
        }
        this.pointer = (this.pointer + 1) % this.bufferLength;
      }
    
      get(i) {
        return this.buffer[i];
      }
      
      //Gets the ith element before last one 
      getLast(i) {
        return this.buffer[this.pointer+this.bufferLength-1-i];
      }
    
    }

//To use it:

let circularBuffer = new CircularBuffer(3);
circularBuffer.push('a');
circularBuffer.push('b');
circularBuffer.push('c');
// should print a,b,c
console.log(`0 element: ${circularBuffer.get(0)}; 1 element: ${circularBuffer.get(1)}; 2 element: ${circularBuffer.get(2)};`);

console.log('Last element: '+circularBuffer.getLast(0)); // should print 'c'

circularBuffer.push('d');

// should print d,b,c
console.log(`0 element: ${circularBuffer.get(0)}; 1 element: ${circularBuffer.get(1)}; 2 element: ${circularBuffer.get(2)};`);

Bujumbura

I think there is a modulo missing for the index of getLast: (this.pointer+this.bufferLength-1-i)%this.bufferLength – Summation

Answer 5

This is a quick mockup of the code you could use (it probably isn't working and has bugs in it, but it shows the way it could be done):

var CircularQueueItem = function(value, next, back) {
    this.next = next;
    this.value = value;
    this.back = back;
    return this;
};

var CircularQueue = function(queueLength){
    /// <summary>Creates a circular queue of specified length</summary>
    /// <param name="queueLength" type="int">Length of the circular queue</type>
    this._current = new CircularQueueItem(undefined, undefined, undefined);
    var item = this._current;
    for(var i = 0; i < queueLength - 1; i++)
    {
        item.next = new CircularQueueItem(undefined, undefined, item);
        item = item.next;
    }
    item.next = this._current;
    this._current.back = item;
}

CircularQueue.prototype.push = function(value){
    /// <summary>Pushes a value/object into the circular queue</summary>
    /// <param name="value">Any value/object that should be stored into the queue</param>
    this._current.value = value;
    this._current = this._current.next;
};

CircularQueue.prototype.pop = function(){
    /// <summary>Gets the last pushed value/object from the circular queue</summary>
    /// <returns>Returns the last pushed value/object from the circular queue</returns>
    this._current = this._current.back;
    return this._current.value;
};

using this object would be like:

var queue = new CircularQueue(10); // a circular queue with 10 items
queue.push(10);
queue.push(20);
alert(queue.pop());
alert(queue.pop());

You could of course implement it using array as well with a class that would internally use an array and keep a value of the current item index and moving that one.

Ola

What's with all those .NET-style doc comments? – Pyromania

@Ionut: They're Javascript intellisense for Visual Studio 2008+ just in case he's on .net otherwise they'll simply be ignored by other editors. – Ola

I had no idea there's support for them in Visual Studio. Thanks for the info. – Pyromania

@Ionut: Make sure to write the AFTER function declaration and not BEFORE as normal in C#. That's the main difference. Otherwise it works quite similar. – Ola

Unnecessary XML style markup makes me sad but a big thumbs up for structured documentation – Bespoke

Answer 6

I use personally the implementation of Trevor Norris that you can find here: https://github.com/trevnorris/cbuffer

and I'm quite happy with it :-)

Monolingual

Answer 7

Short and sweet:

// IMPLEMENTATION
function CircularArray(maxLength) {
  this.maxLength = maxLength;
}

CircularArray.prototype = Object.create(Array.prototype);

CircularArray.prototype.push = function(element) {
  Array.prototype.push.call(this, element);
  while (this.length > this.maxLength) {
    this.shift();
  }
}

// USAGE
var ca = new CircularArray(2);
var i;

for (i = 0; i < 100; i++) {
  ca.push(i);
}

console.log(ca[0]);
console.log(ca[1]);
console.log("Length: " + ca.length);

Output:

98
99
Length: 2

Pancratium

Answer 8

Here's my take. Specifically this is a very simple object implementation of a circular/ring sliding buffer.

A little side note. Despite the fact that people call it similar names, "circular", "ring", "queue", it should be worth clarifying, because they can mean different things.

1. A ring/circular queue. You can add elements to the head, and crop them from the end. Min size is 0, max size is the size of underlying array. The queue wraps around the underlying array.

2. The same thing, a queue, FIFO, first-in-first-out, but with variable (indefinite) max size, and implemented using standard push() and unshift() array methods. To add element, you simply push() it onto an array, and to consume element you unshift() it, that's it, pretty standard functions, no need to invent anything.

3. A sliding buffer of constant size, where new elements are added to the head (right), the buffer slides back (left), and left-most excessive elements are automatically lost. Conceptually it is a sliding buffer, it just happens to get implemented most efficiently as a circular/ring one.

This is the implementation of a (3) kind. This can be used, and is primarily intended, as a back-end of a data visualization widget, e.g. a sliding line graph for real-time monitoring.

The object:

function make_CRS_Buffer(size) {
    return {
        A:  [],
        Ai: 0,
        Asz:    size,
        add:    function(value) {
            this.A[ this.Ai ] = value;
            this.Ai = (this.Ai + 1) % this.Asz;
        },
        forall: function(callback) {
            var mAi = this.A.length < this.Asz ? 0 : this.Ai;
            for (var i = 0; i < this.A.length; i++) {
                callback(this.A[ (mAi + i) % this.Asz ]);
            }

        }
    };
}

Usage:

var buff1 = make_CRS_Buffer(5);

buff1.add(cnt);

buff1.forall(value => {
    b1.innerHTML += value + " ";
});

And, a complete functional example, with two buffers running in parallel:

var b1 = document.getElementById("b1");
var b2 = document.getElementById("b2");

var cnt = 0;

var buff1 = make_CRS_Buffer(5);
var buff2 = make_CRS_Buffer(12);


function add() {
	buff1.add(cnt);
	buff2.add(cnt);
	cnt ++;
	
	b1.innerHTML = "";
	buff1.forall(value => {
		b1.innerHTML += value + " ";
	});
	
	b2.innerHTML = "";
	buff2.forall(value => {
		b2.innerHTML += value + " ";
	});
}

function make_CRS_Buffer(size) {
	return {
		A:	[],
		Ai:	0,
		Asz:	size,
		add:	function(value) {
			this.A[ this.Ai ] = value;
			this.Ai = (this.Ai + 1) % this.Asz;
		},
		forall:	function(callback) {
			var mAi = this.A.length < this.Asz ? 0 : this.Ai;
			for (var i = 0; i < this.A.length; i++) {
				callback(this.A[ (mAi + i) % this.Asz ]);
			}
		
		}
	};
}

<!DOCTYPE html>
<html>
<body>

<h1>Circular/Ring Sliding Buffer</h1>

<p><i>(c) 2020, Leonid Titov</i>

<div id="b1" style="
	background-color: hsl(0,0%,80%);
	padding: 5px;
">empty</div>

<div id="b2" style="
	background-color: hsl(0,0%,80%);
	padding: 5px;
">empty</div>

<br>
<button onclick="add()">Add one more</button>

</body>
</html>

Hope it'll be useful.

Indistinctive

Answer 9

Instead of implementing circular queue with JavaScript, we can use some inbuilt functions of array to achieve circular queue implementation.

example: Suppose we need to implement the circular queue for length 4.

var circular = new Array();
var maxLength = 4;
var addElementToQueue = function(element){
    if(circular.length == maxLength){
        circular.pop();
    }
    circular.unshift(element);
};
addElementToQueue(1);
addElementToQueue(2);
addElementToQueue(3);
addElementToQueue(4);

Output:

circular [4, 3, 2, 1]

If you try to add another element to this array eg:

addElementToQueue(5);

Output:

circular [5, 4, 3, 2]

Aceto

Isn't unshift O(n) in the size of the array? Seems like a really bad way to implement a circular buffer – Ammonic

Answer 10

A lot of answers, but didn't see something like the following functional simple approach... Something like (ES6):

const circularAdd = maxSize => (queue, newItem) =>
  queue.concat([newItem]).slice(Math.max(0, queue.length + 1 - maxSize));

This can be used as a reducer. E.g. in observable streams in scan.

// Suppose newItem$ is a simple new value emitter
const itemBuffer$ = newItem$.pipe(scan(circularAdd(100), []));
// itemBuffer$ will now emit arrays with max 100 items, where the new item is last

edit

Not really an answer to this particular question I see now, cause it doesn't provide a read position... :)

Sender

Answer 11

I couldn't get Robert Koritnik's code to work, so I edited it to the following which seems to work:

    var CircularQueueItem = function (value, next, back) {
        this.next = next;
        this.value = value;
        this.back = back;
        return this;
    };

    var CircularQueue = function (queueLength) {
        /// <summary>Creates a circular queue of specified length</summary>
        /// <param name="queueLength" type="int">Length of the circular queue</type>
        this._current = new CircularQueueItem(undefined, undefined, undefined);
        var item = this._current;
        for (var i = 0; i < queueLength - 1; i++) {
            item.next = new CircularQueueItem(undefined, undefined, item);
            item = item.next;
        }
        item.next = this._current;
        this._current.back = item;

        this.push = function (value) {
            /// <summary>Pushes a value/object into the circular queue</summary>
            /// <param name="value">Any value/object that should be stored into the queue</param>
            this._current.value = value;
            this._current = this._current.next;
        };
        this.pop = function () {
            /// <summary>Gets the last pushed value/object from the circular queue</summary>
            /// <returns>Returns the last pushed value/object from the circular queue</returns>
            this._current = this._current.back;
            return this._current.value;
        };
        return this;
    }

To use:

    var queue = new CircularQueue(3); // a circular queue with 3 items
    queue.push("a");
    queue.push("b");
    queue.push("c");
    queue.push("d");
    alert(queue.pop()); // d
    alert(queue.pop()); // c
    alert(queue.pop()); // b
    alert(queue.pop()); // d
    alert(queue.pop()); // c

Tarpaulin

Because it's a queue and not a stack, should pop() return the first added element instead of the last one? Am I missing something here? For example imagine we have Mike, Lauren and a ticketing booth queue. Mike joins to the end of the queue. After Mike Lauren joins in. Because the queue, Mike will be served first. – Higdon

Answer 12

I recommend using that TypeScript circular array implementation: https://gist.github.com/jerome-benoit/c251bdf872473d1f86ea3a8b90063c90. It is lean and the API is the same as the standard array object.

Collaborate

Answer 13

I think you should be able to do this by just using objects. Something like this:

var link = function(next, value) {
    this.next = next;
    this.value = value;
};

var last = new link();
var second = link(last);
var first = link(second);
last.next = first;

Now you'd just store the value in each link's value property.

Mayence

I believe you forgot to use the new operator. – Pyromania

Yep, been coding too much Python as of late =) – Mayence

Answer 14

One approach would be to use a linked list as others have suggested. Another technique would be to use a simple array as the buffer and to keep track of the read and write positions via indices into that array.

Henninger

Answer 15

I really like how noiv11 solved this and for my need I added an extra property 'buffer' which returns the buffer:

var createRingBuffer = function(length){

  var pointer = 0, buffer = []; 

  return {
    get  : function(key){return buffer[key];},
    push : function(item){
      buffer[pointer] = item;
      pointer = (length + pointer +1) % length;
    },
    buffer : buffer
  };
};

// sample use
var rbuffer = createRingBuffer(3);
rbuffer.push('a');
rbuffer.push('b');
rbuffer.push('c');
alert(rbuffer.buffer.toString());
rbuffer.push('d');
alert(rbuffer.buffer.toString());
var el = rbuffer.get(0);
alert(el);

Bandoline

What a horrible thing to do! The buffer was nicely hidden in the original. – Laddie

Agree, no idea why I did it (2 years ago) – Bandoline

Answer 16

Thanks noiv for your simple and efficient solution. I also needed to be able to access the buffer like PerS did, but i wanted to get the items in the order they were added. So here's what i ended up with:

function buffer(capacity) {
    if (!(capacity > 0)) {
        throw new Error();
    }

    var pointer = 0, buffer = [];

    var publicObj = {
        get: function (key) {
            if (key === undefined) {
                // return all items in the order they were added
                if (pointer == 0 || buffer.length < capacity) {
                    // the buffer as it is now is in order
                    return buffer;
                }
                // split and join the two parts so the result is in order
                return buffer.slice(pointer).concat(buffer.slice(0, pointer));
            }
            return buffer[key];
        },
        push: function (item) {
            buffer[pointer] = item;
            pointer = (capacity + pointer + 1) % capacity;
            // update public length field
            publicObj.length = buffer.length;
        },
        capacity: capacity,
        length: 0
    };

    return publicObj;
}

Here is the test suite:

QUnit.module("buffer");

QUnit.test("constructor", function () {
    QUnit.expect(4);

    QUnit.equal(buffer(1).capacity, 1, "minimum length of 1 is allowed");
    QUnit.equal(buffer(10).capacity, 10);

    QUnit.throws(
        function () {
            buffer(-1);
        },
        Error,
        "must throuw exception on negative length"
    );

    QUnit.throws(
        function () {
            buffer(0);
        },
        Error,
        "must throw exception on zero length"
    );
});

QUnit.test("push", function () {
    QUnit.expect(5);

    var b = buffer(5);
    QUnit.equal(b.length, 0);
    b.push("1");
    QUnit.equal(b.length, 1);
    b.push("2");
    b.push("3");
    b.push("4");
    b.push("5");
    QUnit.equal(b.length, 5);
    b.push("6");
    QUnit.equal(b.length, 5);
    b.push("7");
    b.push("8");
    QUnit.equal(b.length, 5);
});

QUnit.test("get(key)", function () {
    QUnit.expect(8);

    var b = buffer(3);
    QUnit.equal(b.get(0), undefined);
    b.push("a");
    QUnit.equal(b.get(0), "a");
    b.push("b");
    QUnit.equal(b.get(1), "b");
    b.push("c");
    QUnit.equal(b.get(2), "c");
    b.push("d");
    QUnit.equal(b.get(0), "d");

    b = buffer(1);
    b.push("1");
    QUnit.equal(b.get(0), "1");
    b.push("2");
    QUnit.equal(b.get(0), "2");
    QUnit.equal(b.length, 1);
});

QUnit.test("get()", function () {
    QUnit.expect(7);

    var b = buffer(3);
    QUnit.deepEqual(b.get(), []);
    b.push("a");
    QUnit.deepEqual(b.get(), ["a"]);
    b.push("b");
    QUnit.deepEqual(b.get(), ["a", "b"]);
    b.push("c");
    QUnit.deepEqual(b.get(), ["a", "b", "c"]);
    b.push("d");
    QUnit.deepEqual(b.get(), ["b", "c", "d"]);
    b.push("e");
    QUnit.deepEqual(b.get(), ["c", "d", "e"]);
    b.push("f");
    QUnit.deepEqual(b.get(), ["d", "e", "f"]);
});

Soult

Answer 17

Its very easy if you now what Array.prototype.length is:

function CircularBuffer(size) {
  Array.call(this,size); //superclass
  this.length = 0; //current index
  this.size = size; //buffer size
};

CircularBuffer.prototype = Object.create(Array.prototype);
CircularBuffer.prototype.constructor = CircularBuffer;
CircularBuffer.prototype.constructor.name = "CircularBuffer";

CircularBuffer.prototype.push = function push(elem){
  Array.prototype.push.call(this,elem);
  if (this.length >= this.size) this.length = 0;
  return this.length;
}

CircularBuffer.prototype.pop = function pop(){
  var r = this[this.length];
  if (this.length <= 0) this.length = this.size;  
  this.length--;
  return r;
}

Antonina

Answer 18

I prefer simpler approaches. This should be a three-liner, IMO.

Something like

const makeRing = sz                   => ({ sz, buf: new Array(size) }),
      at       = ({sz, buf}, pos)     => buf[pos % sz],
      set      = ({sz, buf}, pos, to) => buf[pos % sz] = to;

Then you can just

const ring = makeRing(10);

ring.buf.fill(1);
set(ring, 35, 'TWO!');

console.log(ring.buf);
console.log(at(ring, 65));

Pucida

Answer 19

I wasn't doing any perf checks, but as per my understanding sequential array access should be faster than linked list. Also I've noticed that multiple implementations suffer from obsolete prototype based ES3 (at least) style which makes my eyeballs pop. Also none of them support dynamic size increase i.e. "growing". So here's how I see this implementation. Feel free to expand as per your needs:

export class Dequeue<T> {
    private buffer: T[];
    private head: number;
    private tail: number;
    private size: number;

    constructor(initialCapacity: number) {
        this.buffer = [];
        this.buffer.length = initialCapacity;
        this.head = this.tail = this.size = 0;
    }

    public enqueue(value: T): T {
        let next = this.head + 1;
        let buffer = this.buffer;
        let length = buffer.length;

        if (length <= next) {
            next -= length;
        }

        if (buffer.length <= this.size) {
            buffer.length += length;

            for (let index = next; index < length; index++) {
                buffer[index + length] = buffer[index];
            }
        }

        this.size++;
        buffer[this.head] = value;
        this.head = next;

        return value;
    }

    public dequeue(): T | undefined {
        if (this.size > 0) {
            this.size--;

            let buffer = this.buffer;
            let length = buffer.length;
            let value = buffer[this.tail];

            let next = this.tail + 1;

            if (length <= next) {
                next -= length;
            }

            this.tail = next;

            return value;
        } else {
            return undefined;
        }
    }

    public get length() {
        return this.size;
    }
}

To prevent propagation of undefined in the interface I can suggest the following version:

export function Throw(message: string): never {
    throw new Error(message);
}

export class Dequeue<T> {
    private buffer: T[];
    private head: number;
    private tail: number;
    private size: number;

    constructor(initialCapacity: number) {
        this.buffer = [];
        this.buffer.length = initialCapacity;
        this.head = this.tail = this.size = 0;
    }

    public enqueue(value: T): T {
        let next = this.head + 1;
        let buffer = this.buffer;
        let length = buffer.length;

        if (length <= next) {
            next -= length;
        }

        if (buffer.length <= this.size) {
            buffer.length += length;

            for (let index = next; index < length; index++) {
                buffer[index + length] = buffer[index];
            }
        }

        this.size++;
        buffer[this.head] = value;
        this.head = next;

        return value;
    }

    public dequeue(defaultValueFactory: () => T = () => Throw('No elements to dequeue')): T {
        if (this.size > 0) {
            this.size--;

            let buffer = this.buffer;
            let length = buffer.length;
            let value = buffer[this.tail];

            let next = this.tail + 1;

            if (length <= next) {
                next -= length;
            }

            this.tail = next;

            return value;
        } else {
            return defaultValueFactory();
        }
    }

    public get length() {
        return this.size;
    }
}

Mercury

Answer 20

  /**
    example: [1,2,3].bPush(-1,'a')   //[1,2,3,'a']
                    .bPush(0,'b')    //[1,2,3,'a']
                    .bPush(-1,'c')   //[1,2,3,'a','c']
                    .bPush(3,'e')    //['a','c','e']
    bufferSize zero or undefined does nothing; returns array as is
    bufferSize negative is same as push
    bufferSize > 0 creates a circular buffer appending newest & overwriting oldest
  */
  Array.prototype.bPush = function (bufferSize, newItem) {
    if (!bufferSize) return this;
    if (bufferSize > 0 && this.length >= bufferSize) {
      while( this.length >= bufferSize) this.shift();
    }
    this.push(newItem);
    return this;
  }

Dermatogen

Answer 21

I have ported my python library to JavaScript via OpenAI, it's somewhat python-esque, but is highly functional (supports .slice, .extend, a genuine .pop, as well as python style .remove(value). Use .append instead of .push)

class CircularList {
    /** https://mcmap.net/q/156180/-efficient-circular-buffer/40784706#40784706 */
    constructor(size, data = []) {
        if (Array.isArray(size)) {
            this.size = size.length;
            this._data = [...size];
        } else {
            this.size = size;
            this._data = [...data].slice(-size);
        }
        this.end = this._data.length % this.size;
    }

    extend(data) {
        this._data.push(...data);
        this._data = this._data.slice(-this.size);
        this.end = this._data.length % this.size;
    }

    pop(index = -1) {
        /**
         * Remove and return item at index (default last).
         */
        if (this._data.length === 0) {
            throw new Error("pop from empty list");
        }

        const idx = (index + this.end) % this.size;
        const result = this._data.splice(idx, 1)[0];
        this.end = (this.end - 1 + this.size) % this.size;
        return result;
    }

    index(value) {
        try {
            let idx = this._data.indexOf(value);
            idx = (idx - this.end + this.size) % this.size;
            return idx;
        } catch {
            return -1;
        }
    }

    remove(value) {
        const idx = this.index(value);
        if (idx !== -1) {
            this.pop(idx);
        }
    }

    append(value) {
        /** Append an element */
        if (this._data.length === this.size) {
            this._data[this.end] = value;
        } else {
            this._data.splice(this.end, 0, value);
        }
        this.end = (this.end + 1) % this.size;
    }

    asArray() {
        return [...this._data.slice(this.end), ...this._data.slice(0, this.end)];
    }

    get(key = -1) {
        /** Get element by end, relative to the current end */
        let idx;
        key = key >>> 0;
        if (this._data.length === this.size) {
            idx = (key + this.end) % this.size;
        } else {
            idx = key % this._data.length;
        }
        return this._data[idx];
    }

    slice(...args) {
        const result = [];
        for (let i = 0; i < this._data.length; ++i) {
            result.push(this.get(i));
        }
        return Array.prototype.slice.apply(result, args);
    }

    toString() {
        /** Return string representation */
        return `Circular List: ${this.asArray().toString()} (${this._data.length} out of ${this.size} items)`;
    }
}

Pylle

Answer 22

Using ES6 classes you can do a structure like this:

class CircularBuffer {
  constructor(size) {
    this.size = size;
    this.buffer = new Array(size);
    this.head = 0;
    this.tail = 0;
    this.length = 0;
  }

  isEmpty() {
    return this.length === 0;
  }

  isFull() {
    return this.length === this.size;
  }

  push(item) {
    if (this.isFull()) {
      this.head = (this.head + 1) % this.size; // Overwrite the oldest item
    }

    this.buffer[this.tail] = item;
    this.tail = (this.tail + 1) % this.size;
    this.length = Math.min(this.length + 1, this.size);
  }

  pop() {
    if (this.isEmpty()) {
      throw new Error("Buffer is empty");
    }

    const item = this.buffer[this.head];
    this.head = (this.head + 1) % this.size;
    this.length--;

    return item;
  }

  toArray() {
    const result = [];
    for (let i = 0; i < this.length; i++) {
      result.push(this.buffer[(this.head + i) % this.size]);
    }
    return result;
  }
}


// Example usage:
const buffer = new CircularBuffer(5);

buffer.push(1);
buffer.push(2);
buffer.push(3);

console.log(buffer.toArray()); // [1, 2, 3]

console.log(buffer.pop()); // 1
console.log(buffer.toArray()); // [2, 3]

buffer.push(4);
buffer.push(5);
buffer.push(6);

console.log(buffer.toArray()); // [2, 3, 4, 5, 6]

buffer.push(7);
buffer.push(8);
buffer.push(9);

console.log(buffer.toArray()); // [5, 6, 7, 8, 9]

Vedis