Skip to content

Instantly share code, notes, and snippets.

@JiaxiangZheng
Created April 18, 2017 03:35
Show Gist options
  • Save JiaxiangZheng/81df68d2db85f179d58e146df3995d4c to your computer and use it in GitHub Desktop.
Save JiaxiangZheng/81df68d2db85f179d58e146df3995d4c to your computer and use it in GitHub Desktop.
a ring queue with max capacity implements with plain array
/**
* RingQueue implements a cycle
*/
class RingQueue {
constructor(capacity) {
this.list = new Array(capacity + 1);
this.lower = 0;
this.upper = 0;
}
add(v) {
const size = this.list.length;
const index = this.upper;
const upper = (this.upper + 1) % size;
if (upper === this.lower) { // already full
this.list[this.lower] = null; // set the dummy node
this.lower = (this.lower + 1) % size;
}
this.upper = upper;
this.list[index] = v;
}
clear() {
this.lower = 0;
this.upper = 0;
}
full() {
const size = this.list.concat.length;
const upper = (this.upper + 1) % size;
return upper === this.lower;
}
size() {
return (this.list.length + this.upper - this.lower) % this.list.length;
}
}
// exports.RingQueue = RingQueue;
// TEST CODE
const assert = {
equal: (left, right) => { if (left !== right) throw new Error('not euqal') }
};
let queue = new RingQueue(4);
assert.equal(queue.size(), 0);
queue.add(0); assert.equal(queue.lower, 0); assert.equal(queue.upper, 1); assert.equal(queue.size(), 1);
queue.add(1); assert.equal(queue.lower, 0); assert.equal(queue.upper, 2); assert.equal(queue.size(), 2);
queue.add(2); assert.equal(queue.lower, 0); assert.equal(queue.upper, 3); assert.equal(queue.size(), 3);
queue.add(3); assert.equal(queue.lower, 0); assert.equal(queue.upper, 4); assert.equal(queue.size(), 4);
queue.add(4); assert.equal(queue.lower, 1); assert.equal(queue.upper, 0); assert.equal(queue.size(), 4);
for (let i = 5; i < 100; i++) {
queue.add(i);
assert.equal(queue.size(), 4);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment