尋找一個圓形的固定尺寸的基於陣列的雙端隊列

Question

我正在尋找一個Deque，其具有以下特徵：

• 它固定大小
• 如果我在頭/尾元件的添加元素相對端降
• 它是基於陣列的，所以我可以在恆定的時間訪問隨機元素
• 我可以在前面或在末端（雙端隊列）

0123添加元素

我檢查了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)); 
     } 

    } 

}