Java 中的循环缓冲区？

Question

我需要一个类似双端队列的数据结构，我认为它被称为循环缓冲区。

这就是我所做的。

public class MyStack {


    byte[][] orders = {  {0, 1, 2, 3}, {1, 2, 3, 0}, {2, 3, 0, 1}, {3, 0, 1, 2}  };

    byte state      = 0;

    int[] data      = {1, 2, 3, 4};


    void swap(int value){           
        data[state] = value;

        if(state == 3){
            state = 0;

        }else{
            state ++;

        }       
    }

    int[] dump(){

        int[] output = {  
                          data[  orders[state][0]  ],
                          data[  orders[state][1]  ],
                          data[  orders[state][2]  ],
                          data[  orders[state][3]  ],
                       };

        return output;
    }

}

此处的输出正是我需要的功能类型。它基本上是一个长度为 4 的 window，穿过一个无限的、离散的 space，或者沿着一条数轴。

我的问题是：这个解决方案是否有效？是否有为此功能设计的内置库？如果是这样，是否值得改用？

Answer 1

一个circular buffer的典型实现使用两个索引来标记队列的第一个和最后一个元素。不需要显式存储状态，因为 enqueue 和 dequeue 可以通过索引计算来完成。 swap 方法更好的名称是 rotate.

您可以删除 orders 数组并将 dump 实现更改为：

    int[] output = {  
                      data[  (state+0)%4  ],
                      data[  (state+1)%4  ],
                      data[  (state+2)%4  ],
                      data[  (state+3)%4  ],
                   };

Answer 2

对此的一个改进是，删除大小为 n 的二维数组订单。

byte[][] orders = {  {0, 1, 2, 3}, {1, 2, 3, 0}, {2, 3, 0, 1}, {3, 0, 1, 2}  };

因为如果你知道状态，那么订单数组也可以通过公式动态确定

for(int i =0; i<data.length; i++){
  output[i] = data[(state+i)%data.length];
}

这可以用于return输出。

Java 中的循环缓冲区？

Circular Buffer in Java?

java

optimization

data-structures

stack

deque