Циклическая очередь с полной емкостью БУФЕРА

#arrays #c #algorithm #queue

Вопрос:

 #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 элементы могут находиться в буфере одновременно?

Ответ №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 */
}