Circular buffer

Circular buffer



circular buffercyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams.


The useful property of a circular buffer is that it does not need to have its elements shuffled around [又一次排列]when one is consumed. (If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.) In other words, the circular buffer is well-suited[很合适] as a FIFO [先进先出]buffer while a standard, non-circular buffer is well suited as a LIFO [后进后出]buffer.

Circular buffering makes a good implementation strategy for a queue that has fixed maximum size. Should a maximum size be adopted [被採用]for a queue, then a circular buffer is a completely ideal implementation; all queue operations are constant time. However, expanding a circular buffer requires shifting memory, which is comparatively[相对来说] costly. For arbitrarily expanding queues[可任意扩展的], a linked list approach[链表] may be preferred instead.

[本文作者franklin注解]环形buffer 应用于固定的块场合,一旦固定,这块内存就是专用,所以,不具备扩展性.

In some situations, overwriting [可覆盖性]circular buffer can be used, e.g. in multimedia. If the buffer is used as the bounded [有界性,有限制] buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up. Also, the LZ77 family of lossless data compression algorithms operates on the assumption that strings seen more recently in a data stream are more likely to occur soon in the stream. Implementations store the most recent data in a circular buffer.

How it works

A circular buffer first starts empty and of some predefined length. For example, this is a 7-element buffer:

Circular buffer - empty.svg

Assume that a 1 is written into the middle of the buffer (exact starting location does not matter in a circular buffer):

Circular buffer - XX1XXXX.svg

Then assume that two more elements are added — 2 & 3 — which get appended after the 1:

Circular buffer - XX123XX.svg

If two elements are then removed from the buffer, the oldest values inside the buffer are removed. The two elements removed, in this case, are 1 & 2, leaving the buffer with just a 3:

Circular buffer - XXXX3XX.svg

If the buffer has 7 elements then it is completely full:

Circular buffer - 6789345.svg

A consequence of the circular buffer is that when it is full and a subsequent write is performed, then it starts overwriting the oldest data. In this case, two more elements — A & B — are added and they overwrite the 3 & 4:


Circular buffer - 6789AB5.svg

Alternatively[或者], the routines that manage the buffer could prevent overwriting the data and return an error or raise[根本就是设计成不能写入] an exception. Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer.

Finally, if two elements are now removed then what would be returned is not 3 & 4 but 5 & 6 because A & B overwrote the 3 & the 4 yielding the buffer with:

Circular buffer - X789ABX.svg

Circular buffer mechanics

What is not shown in the example above is the mechanics of how the circular buffer is managed.

Start/end pointers (head/tail)[edit]

Generally, a circular buffer requires four pointers:

  • one to the actual buffer in memory
  • one to the buffer end in memory (or alternately[取代]: the size of the buffer)
  • one to point to the start of valid data (or alternately: amount of data written to the buffer)
  • one to point to the end of valid data (or alternately: amount of data read from the buffer)

Alternatively[或者], a fixed-length buffer with two integers to keep track of indices can be used in languages that do not have pointers.


Taking a couple of examples from above. (While there are numerous[庞大的] ways to label the pointers and exact semantics[精确到语意]can vary, this is one way to do it.)

This image shows a partially[部分] full buffer:

Circular buffer - XX123XX with pointers.svg

This image shows a full buffer with two elements having been overwritten:

Circular buffer - 6789AB5 with pointers.svg

What to note about the second one is that after each element is overwritten then the start pointer is incremented as well.


Full / Empty Buffer Distinction

A small disadvantage of relying on pointers or relative indices of the start and end of data is, that in the case the buffer is entirely full, both pointers point to the same element:

Circular buffer - 6789AB5 full.svg

This is exactly the same situation as when the buffer is empty:

Circular buffer - 6789AB5 empty.svg


To solve this confusion there are a number of solutions:

Always Keep One Slot Open [最简单有效的解决的方法就是保持最后一个单元不写]

This design always keeps one slot unallocated. A full buffer has at most (\text{size}-1) slots. If both pointers refer to the same slot, the buffer is empty. If the end (write) pointer refers to the slot preceding the one referred to by the start (read) pointer, the buffer is full.

The advantage is:

  • The solution is simple and robust.

The disadvantages are:

  • One slot is lost, so it is a bad compromise when the buffer size is small or the slot is big or is implemented in hardware.
  • The full test requires a modulo operation


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。


【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...



  • 敏捷过程模型有哪几种_能力模型的第四层能力

    敏捷过程模型有哪几种_能力模型的第四层能力目录 一、模型简介和思想 二、模型结构 第一部分encoder层 第二部分Convolution Layer卷积层 第三部分Co-Predictor Layer联合

  • c语言浮点数输出格式的控制,c语言输出格式控制「建议收藏」


  • Web自动化测试-Protractor基础(二)


  • 【javaScript】cssText兼容及好处(相对于


  • SIFT–尺度空间、高斯金字塔


  • 解决网页上不能直接复制文字的问题「建议收藏」