50

有人已经在 J​​avaScript 中实现了循环缓冲区吗？如果没有指针，您将如何做到这一点？

4

20 回答 20

36

奇怪的巧合，我今天早些时候才写了一篇！我不知道您的具体要求是什么，但这可能有用。

它提供了一个类似无限长度数组的界面，但会“忘记”旧项目：

// 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= {};
于 2009-10-17T21:31:45.990 回答
28 
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;
    }
  };
};

更新：如果你只用数字填充缓冲区，这里有一些衬垫插件：

min  : function(){return Math.min.apply(Math, buffer);},
sum  : function(){return buffer.reduce(function(a, b){ return a + b; }, 0);},
于 2011-01-23T13:30:37.877 回答
11

像许多其他人一样，我喜欢noiv 的解决方案，但我想要一个更好的 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];
        }
    }
  };
};

对原版的改进：

  • get支持默认参数（返回推送到缓冲区的最后一项）
  • get支持负索引（从右数）
  • prev将缓冲区移回一个并返回那里的内容（例如弹出而不删除）
  • nextundoes prev（向前移动缓冲区并返回它）

prev我用它来存储命令历史记录，然后我可以使用它的和方法在应用程序中翻阅next，当它们无处可去时很好地返回 undefined。

于 2015-01-20T05:45:34.547 回答
4

这是您可以使用的代码的快速模型（它可能无法正常工作并且其中有错误，但它显示了可以完成的方式）：

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());

您当然可以使用数组来实现它，也可以使用一个在内部使用数组并保留当前项索引的值并移动该值的类来实现它。

于 2009-10-17T20:51:36.097 回答
4

这是我的看法。具体来说，这是一个非常简单的循环/环形滑动缓冲区的对象实现。

一点旁注。尽管人们称它为相似的名称，“圆形”、“环形”、“队列”，但应该值得澄清一下，因为它们可能意味着不同的东西。

  1. 环形/循环队列。您可以将元素添加到头部，然后从末端裁剪它们。最小大小为 0，最大大小是底层数组的大小。队列环绕底层数组。

  2. 同样的东西，队列，FIFO，先进先出，但具有可变（无限）最大大小，并使用标准 push() 和 unshift() 数组方法实现。要添加元素，您只需将其 push() 到一个数组中，然后使用 unshift() 即可使用元素，就是这样，非常标准的函数，无需发明任何东西。

  3. 一个恒定大小的滑动缓冲区，其中新元素被添加到头部（右），缓冲区向后滑动（左），最左边的多余元素自动丢失。从概念上讲，它是一个滑动缓冲区，它恰好被最有效地实现为循环/环形缓冲区。

这是（3）种的实现。这可以用作并且主要用于作为数据可视化小部件的后端，例如用于实时监控的滑动线图。

物体：

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 ]);
            }

        }
    };
}

用法：

var buff1 = make_CRS_Buffer(5);

buff1.add(cnt);

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

并且，一个完整的功能示例，两个缓冲区并行运行：

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>

希望它会有用。

于 2020-02-18T16:17:23.137 回答
3

我个人使用 Trevor Norris 的实现，你可以在这里找到： https ://github.com/trevnorris/cbuffer

我对此很满意:-)

于 2014-05-18T09:45:40.067 回答
3

简短而甜蜜：

// 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);

输出：

98
99
Length: 2
于 2015-04-02T15:29:19.340 回答
3

我们可以使用数组的一些内置函数来实现循环队列，而不是用 JavaScript 实现循环队列。

示例：假设我们需要实现长度为 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);

输出：

圆形 [4, 3, 2, 1]

如果您尝试向此数组添加另一个元素，例如：

addElementToQueue(5);

输出：

圆形 [5, 4, 3, 2]

于 2015-11-09T11:44:43.693 回答
2

差不多 10 年后，一个使用 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)};`);

于 2019-09-29T18:57:58.210 回答
2

很多答案，但没有看到类似以下功能简单的方法......类似（ES6）的东西：

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

这可以用作减速器。例如，在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

编辑

不是我现在看到的这个特定问题的答案，因为它没有提供阅读位置...... :)

于 2020-02-04T09:13:10.563 回答
1

我无法让 Robert Koritnik 的代码工作，所以我将其编辑为以下似乎工作的代码：

    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
于 2010-05-28T17:19:00.197 回答
1

我建议使用 TypeScript 循环数组实现：https ://gist.github.com/jerome-benoit/c251bdf872473d1f86ea3a8b90063c90 。它很精简，API 与标准数组对象相同。

于 2021-05-27T23:24:14.817 回答
0

我认为你应该能够通过使用对象来做到这一点。像这样的东西：

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 属性中。

于 2009-10-17T20:38:55.910 回答
0

一种方法是使用其他人建议的链表。另一种技术是使用一个简单的数组作为缓冲区，并通过该数组的索引来跟踪读取和写入位置。

于 2009-10-17T21:23:33.130 回答
0

我真的很喜欢noiv11 如何解决这个问题，并且出于我的需要，我添加了一个额外的属性“缓冲区”，它返回缓冲区：

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);
于 2012-06-12T12:12:57.400 回答
0

感谢 noiv 提供简单有效的解决方案。我还需要能够像PerS 那样访问缓冲区，但我想按添加的顺序获取项目。所以这就是我的结果：

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;
}

这是测试套件：

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"]);
});
于 2013-05-14T04:07:55.963 回答
0

如果你现在Array.prototype.length是什么，这很容易：

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;
}
于 2018-11-14T19:45:59.513 回答
0

我更喜欢更简单的方法。这应该是三班轮，IMO。

就像是

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

然后你可以

const ring = makeRing(10);

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

console.log(ring.buf);
console.log(at(ring, 65));
于 2019-10-04T00:39:08.853 回答
0

我没有做任何性能检查，但据我了解，顺序数组访问应该比链表更快。此外，我注意到多个实现受到过时的基于原型的 ES3（至少）风格的影响，这让我的眼球流行起来。他们也不支持动态大小增加，即“增长”。所以这就是我如何看待这个实现。根据您的需要随意扩展：

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;
    }
}

为了防止undefined在界面中传播，我可以建议以下版本：

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;
    }
}
于 2020-02-16T15:06:59.450 回答
0 
  /**
    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;
  }
于 2022-02-10T01:21:11.823 回答