Кольцевой буфер в JavaScript
Используйте десятичное число и используйте больше десятичных разрядов, чем Вы думаете, что Вам будет нужно так, чтобы caclulations был корректен. Деньги не делают возврата alwys корректные результаты в вычислениях. Ни при каких обстоятельствах не используйте плавание или реальный, поскольку они - неточные типы данных и могут заставить вычисления быть неправильными (тем более, что они становятся более сложными).
5 ответов
Странное совпадение, я только что написал одно сегодня! Я не знаю, каковы ваши требования, но это может быть полезно.
Он представляет интерфейс, подобный массиву неограниченной длины, но «забывает» старые элементы:
// 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= {};
Я думаю, вы должны уметь делать это, просто используя объекты. Примерно так:
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;
Теперь вы просто сохраняете значение в свойстве value каждой ссылки.
Это быстрый макет кода, который вы могли бы использовать (вероятно, он не работает и содержит ошибки, но показывает, как это можно сделать):
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;
};
с использованием этого объект будет иметь вид:
var queue = new CircularQueue(10); // a circular queue with 10 items
queue.push(10);
queue.push(20);
alert(queue.pop());
alert(queue.pop());
Конечно, вы могли бы реализовать его, используя массив, а также с классом, который бы внутренне использовал массив и сохранял значение текущего индекса элемента и перемещал его.
Один из подходов - использовать связанный список, как предлагали другие. Другой способ - использовать простой массив в качестве буфера и отслеживать позиции чтения и записи через индексы в этом массиве.
Я не смог заставить код Роберта Коритника работать, поэтому я отредактировал его следующим образом, который, кажется, работает:
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;
}
Для использования:
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