介绍

圆形缓冲区（circular buffer），也称作圆形队列（circular queue），循环缓冲区（cyclic buffer），环形缓冲区（ring buffer），是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。

用法

圆形缓冲区的一个有用特性是：当一个数据元素被用掉后，其余数据元素不需要移动其存储位置。相反，一个非圆形缓冲区（例如一个普通的队列）在用掉一个数据元素后，其余数据元素需要向前搬移。换句话说，圆形缓冲区适合实现先进先出缓冲区，而非圆形缓冲区适合后进先出缓冲区。

圆形缓冲区适合于事先明确了缓冲区的最大容量的情形。扩展一个圆形缓冲区的容量，需要搬移其中的数据。因此一个缓冲区如果需要经常调整其容量，用链表实现更为合适。

写操作覆盖圆形缓冲区中未被处理的数据在某些情况下是允许的。特别是在多媒体处理时。例如，音频的生产者可以覆盖掉声卡尚未来得及处理的音频数据。

工作机制

由于计算机内存是线性地址空间，因此圆形缓冲区需要特别的设计才可以从逻辑上实现。

读指针与写指针：

一般的，圆形缓冲区需要 4 个指针：

• 在内存中实际开始位置；
• 在内存中实际结束位置，也可以用缓冲区长度代替；
• 存储在缓冲区中的有效数据的开始位置（读指针）；
• 存储在缓冲区中的有效数据的结尾位置（写指针）。

读指针、写指针可以用整型值来表示。

扩展：生产者消费者问题，参见：操作系统原理之进程同步 (opens new window)

实现

JavaScript

// Circular Queues offer a quick to store FIFO data with a maximum size.
// Conserves memory as we only store up to our capacity
// It is opposed to a queue which could continue to grow if input outpaces output
// Doesn’t use dynamic memory so No memory leaks

class CircularQueue {
  constructor (maxLength) {
    this.queue = []
    this.front = 0
    this.rear = 0
    this.maxLength = maxLength
  }

  // ADD ELEMENTS TO QUEUE
  enqueue (value) {
    if (this.checkOverflow()) return
    if (this.checkEmpty()) {
      this.front += 1
      this.rear += 1
    } else {
      if (this.rear === this.maxLength) {
        this.rear = 1
      } else this.rear += 1
    }
    this.queue[this.rear] = value
  }

  // REMOVES ELEMENTS
  dequeue () {
    if (this.checkEmpty()) {
      // UNDERFLOW
      return
    }
    const y = this.queue[this.front]
    this.queue[this.front] = '*'
    if (!this.checkSingleelement()) {
      if (this.front === this.maxLength) this.front = 1
      else {
        this.front += 1
      }
    }

    return y // Returns the removed element and replaces it with a star
  }

  // checks if the queue is empty or not
  checkEmpty () {
    if (this.front === 0 && this.rear === 0) {
      return true
    }
  }

  checkSingleelement () {
    if (this.front === this.rear && this.rear !== 0) {
      this.front = this.rear = 0
      return true
    }
  }

  // Checks if max capacity of queue has been reached or not
  checkOverflow () {
    if ((this.front === 1 && this.rear === this.maxLength) || (this.front === this.rear + 1)) {
      // CIRCULAR QUEUE OVERFLOW
      return true
    }
  }

  // Prints the entire array ('*' represents blank space)
  display (output = value => console.log(value)) {
    for (let index = 1; index < this.queue.length; index++) {
      output(this.queue[index])
    }
  }

  // Displays the length of queue
  length () {
    return this.queue.length - 1
  }

  // Display the top most value of queue
  peek () {
    return this.queue[this.front]
  }
}

export { CircularQueue }

应用

卡牌序列问题

// see https://gist.github.com/tinylamb/9228640
/*
 * =========================================================
 *       Filename:  throwcards.c
 *    Description:  google Throwing cards away I
 *    题目大意：给n张牌，放成一叠，从上到下编号从1到n，当至少还有两张牌时
 *    丢弃最上面的牌，然后把新的最上面的牌放到最下面，一直重复，直到只剩下一张牌
 *    输出丢弃牌的序列。
 * =========================================================
 */
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#define MAX 51 //预先知道数组最大值,留一个空来区别空/满

/*数据集定义*/
typedef struct Queue{
    int array[MAX];
    int head,tail;
}Queue;

/*queue上的基本操作*/
void InitQueue(Queue *q);
bool IsEmpty(Queue *q);
bool IsFull(Queue *q);
void InQueue(Queue *q,int e);
int DeQueue(Queue *q);

int main(){
    int n;
    int discards[MAX];
    Queue q;
    while(scanf("%d",&n)!=EOF && n){
        InitQueue(&q);
        int i;
        for(i=1;i<=n;i++)
            InQueue(&q,i);
        int k=0;
        while(!IsEmpty(&q)){
            discards[k++]=DeQueue(&q);
            int top=DeQueue(&q);
            InQueue(&q , top);
        }
        printf("Discarded cards:");
        for(i=0;i<n-1;i++)
            printf("%d%s",discards[i],(i==n-2)?"\n":",");
        printf("Remaining card:%d\n",discards[i]);
    }
    return 0;
}

void InitQueue(Queue *q){
    q->head=q->tail=0;
}
bool IsEmpty(Queue *q){
    return (q->head==q->tail)?true:false;
}

bool IsFull(Queue *q){
    return ((q->tail + 1) % MAX == q->head)?true:false;
}

void InQueue(Queue *q,int e){
    assert(!IsFull(q));
    q->array[q->tail]=e;
    q->tail = (q->tail+1) % MAX;
}
int DeQueue(Queue *q){
    assert(!IsEmpty(q));
    int e=q->array[q->head];
    q->head = (q->head + 1) % MAX;
    return e;
}

参考

• 环形缓冲区 - Wikiwand (opens new window)