思路

  1. 先進先出
  2. 紀錄開始與結尾元素

實作

測試方法

public class Queue_Array3 {
    Integer[] ary;
    Integer[] queue;
    Integer i_front = null;
    Integer i_end = null;

    public Queue_Array3(Integer[] ary){
        this.ary = ary;
    }

    public void build_queue(){
        this.queue = new Integer[this.ary.length];
        for (int i = 0 ; i < ary.length; i++) {
            offer(ary[i]);
        }
    }

    public static void main(String[] args) {
        Integer[] nums = new Integer[]{1,2,3,4,5};
        Queue_Array3 queue_array = new Queue_Array3(nums);
        queue_array.build_queue();

        // full - extend the storage size
        queue_array.offer(6); //expand_space

        Integer val = queue_array.poll();
        val = queue_array.poll();
        val = queue_array.poll();
        val = queue_array.poll();
        val = queue_array.poll();
        val = queue_array.poll();

        // empty
        val = queue_array.poll();

        // circular queue - i_end test
        queue_array.offer(11);
        queue_array.offer(12);
        queue_array.offer(13);
        queue_array.offer(14);
        queue_array.offer(15);
        val = queue_array.poll();
        val = queue_array.poll();
        val = queue_array.poll();
        val = queue_array.poll();

        for (int i = 0; i < 80; i++) {
            queue_array.offer(30 + i);
        }

        System.out.println();
    }

具體

offer

private void offer(Integer val) {
    // 空間不夠需要拓展空間
    if (size() == queue.length) {
        // warning
        expand_space();
    }

    if (size() == 0) { // 空的
        i_front = 0;
        i_end = 0;
        queue[i_end] = val; // 把參數放到 end
    }else { //非空
        i_end++; // circular array -> 先添加最後位數 for 環狀結構
        i_end %= queue.length; //如果餘數= 6%=5,1
        queue[i_end] = val; //queue[1]=999
    }

}

private void expand_space() {
    Integer[] queue_new = new Integer[this.queue.length * 2]; //拓展
    int i = 0;
    while (true) {
        if (size() == 0) break; //如果全部轉進去,break

        Integer val = poll(); //不停從原有內容 poll 出來準備放到新的 queue_new
        queue_new[i] = val;
        i++;

    }

    this.i_front = 0; // 初始化 i_front
    this.i_end = i - 1; // 初始化 i_end

    this.queue = queue_new;

}

private int size() {
    if (i_front == null && i_end == null) { //為第一個
        return 0;
    }else if (i_end >= i_front) { // 最後 >= 最前
        return (i_end - i_front) + 1; // 4-0+1=5, 尚未出現環狀陣列
    }else if (i_end < i_front) { //出現環狀陣列
        return (queue.length - i_front) //前半段大小 + (i_end) + 1; // 後半段大小
        // 5 - 1 = 4, 4+1=5 -> 9
    }
    return -1;
}

poll

public Integer poll() {
    if (size() == 0) { // 空的
        return null;
    }

    Integer val = queue[i_front];
    queue[i_front] = null;

    if (size() == 1) { // 取出後就是最後一個 -> queue=null
        i_front = null;
        i_end = null;
    }else {
        i_front++; // circual array
        i_front %= queue.length; //1%4=1,3%4=3,5%4=1 環狀陣列
    }
    return val;
}