Как создать простой круглый массив?

Question

По моему учебнику, реализации очереди ADT можно сделать:

• Использование круговых массивов
• Использование связанных списков

Как создать простой круговой массив? Я не уверен, что он широко используется. Это только связанный список, где последний элемент указывает на первый элемент?

Answer 1

Существует несколько примеров кольцевых буферов и связанных с ними компромиссов на Wikipedia.

Простейшим примером может в JS быть:

function RingBuffer(size) { 
    this.backing = new Array(size); 
    this.start = 0; 
    this.length = 0; 
    this.max_size = size; 
} 
RingBuffer.prototype = { 
    add: function (x) { 
     if (this.length === this.max_size) { 
      throw new Exception("Ring overflow error."); 
     } else { 
      this.backing[(this.start + this.length) % this.max_size] = x; 
      this.length += 1; 
     } 
    }, 
    popFirst: function (x) { 
     if (this.length == 0) { 
      throw new Exception("No such element."); 
     } else { 
      this.length -= 1; 
      return this.backing[this.start++]; 
     } 
    } 
}; 

Основная идея заключается в том, что это массив фиксированного размера, который использует немного указателя математике для цикла обратно к началу, как вы пытаетесь наполнять его все больше и больше; он может или не может делать оценки, проверяя, как это сделано выше.