如何创建一个简单的圆形数组？

Question

根据我的教科书，可以完成Queue ADT的实现：

• 使用圆形阵列
• 使用链接列表

你如何创建一个简单的圆形阵列？我不确定它是否被广泛使用。它只是一个链接列表，其中最后一个项目指向第一个项目？

Answer 1

在Wikipedia上有几个环缓冲器的例子和与它们相关的设计权衡。

TypeScript中最简单的例子是：

class RingBuffer<T> {
  private backing: Array<T>;
  private size: number;
  private start: number;
  get length(): number {
    return this.size;
  }
  constructor(private maxSize: number) {
    this.backing = [];
    this.start = 0;
    this.size = 0;
  }
  public push(...ts: Array<T>): number {
    if (this.size + ts.length > this.maxSize) {
      throw new Error('Ring overflow error.');
    }
    for (const t of ts) {
      this.backing[(this.start + this.size) % this.maxSize] = t;
      this.size++;
    }
    return this.size;
  }
  public shift() {
    if (this.size === 0) {
      throw new Error('No such element.');
    }
    this.size--;
    const val = this.backing[this.start];
    this.start = (this.start + 1) % this.maxSize;
    return val;
  }
  public pop() {
    if (this.size === 0) {
      throw new Error('No such element.');
    }
    this.size--;
    return this.backing[(this.start + this.size) % this.maxSize];
  }
}

基本的想法是它是一个固定大小的数组，它使用一点指针数学循环回到开头，因为你试图越来越多地填充它;它可能会或可能不会检查上述方式。

Answer 2

对于Java（以及许多其他语言中的类似），有两种选择：

• 固定大小，Object[]作为内部存储。 方法：size() / rotate() / get(index) / set(index, value)
• 灵活的尺寸，ArrayList<T>作为内部存储。 除了固定大小的版本可以做什么，它还可以add(value) / add(index, value) / remove(index) / remove(value) / indexOf(index) / lastIndexOf(index)。

提示：

• 由于通过索引缓慢访问元素，Linked list不是一个好的选择。
• 两种选择都使用int head指向循环索引。 需要维护它，并在各种操作中将它与内部结构的真实索引进行转换。