寻找一个圆形固定大小的基于arrays的双端队列

我正在寻找具有以下特征的Deque ：

• 它有固定的大小
• 如果我在相反端的头/尾元素处添加元素就会丢失
• 它是基于数组的，所以我可以在恒定的时间内访问随机元素
• 我可以在前面或末尾添加元素（双端）

我检查了JCF中的Deque实现，但是我找不到合适的东西。

Answer 1

因为我喜欢编写自己的数据类型，

 import static org.junit.Assert.assertEquals; import org.junit.Test; public class Ring { private String[] data; int n = 0; public Ring(int size) { data = new String[size]; } public void push(String s) { data[n] = s; n = (n + 1) % data.length; } public void shift(String s) { data[n = (n - 1) % data.length] = s; } public String get(int index) { return data[(n + index) % data.length]; } public static class Examples { @Test public void shouldDropElementsWhenPushingTooFar() { Ring ring = new Ring(3); ring.push("A"); ring.push("B"); ring.push("C"); ring.push("D"); ring.push("E"); assertEquals("C", ring.get(0)); assertEquals("D", ring.get(1)); assertEquals("E", ring.get(2)); } @Test public void shouldAddElementsAtTheFront() { Ring ring = new Ring(3); ring.push("A"); ring.push("B"); ring.push("C"); ring.push("D"); ring.push("E"); // rewind ring.shift("B"); assertEquals("B", ring.get(0)); assertEquals("C", ring.get(1)); assertEquals("D", ring.get(2)); } } }