具有完整 BUFFER 容量的循环队列

Question

#define BUFFER_SIZE 10
typedef {
...
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

当

时缓冲区为空

in == out

时缓冲区已满

((in+1)%BUFFER_SIZE) == out

此算法最多允许同时在缓冲区中 BUFFER_SIZE - 1 项。

是否有 BUFFER_SIZE 个项目可以同时在缓冲区中的解决方案？

Answer 1

使用整数变量计数器，初始化为 0。每次我们向缓冲区添加一个新项目时计数器都会递增，每次我们从缓冲区中删除一个项目时计数器都会递减。

制作人-

while (true) {
  /* produce an item in nextProduced */ 
  while (counter == BUFFER_SIZE)
  ; /* do nothing */ 
  buffer[in] = nextProduced; 
  in = (in + 1) %BUFFER_SIZE; 
  counter++;
}

消费者-

while (true) {
  while (counter == 0)
  ; /* do nothing */
  nextConsumed = buffer[out];
  out = (out + 1) % BUFFER_SIZE; 
  counter--;
  /* consume the item in nextConsumed */
}

具有完整 BUFFER 容量的循环队列

Cyclic queue with full BUFFER capacity

c

arrays

algorithm

queue