java資料結構——環形隊列

ArrayQueue存在一個問題，假設當尾部插入元素滿了，頭部又删掉了一些元素，這種情況下，就誤認為空間滿了，造成了假溢出，實際上頭部删除了元素留出了空間。這時候環形隊列就解決了這樣的一個問題，環形隊列的front指針始終指向目前隊列的最後位置；end指針始終指向第一個元素的前一個位置為-1，存儲元素的時候頭部和尾部都可以互相移動，而不必造成假溢出現象，節省了記憶體空間。如下：

1、構造方法

class CircleQueue {

    //隊頭
    private int front;
    //隊尾
    private int end;
    //隊列有效長度
    private int elements;
    //隊列
    private long[] queue;

    public CircleQueue() {
        queue = new long[5];
        front = -1;
        end = -1;
    }

    public CircleQueue(int length) {
        queue = new long[length];
        front = -1;
        end = -1;
    }
}
           

2、添加隊列

/**
     * 插入元素
     */
    public void add(int value) {
        if (isFull()) {
            System.out.println("隊列已滿，請删除");
            throw new IndexOutOfBoundsException();
        }
        if (isEmpty()) {
            front = 0;
        }
        if ((end == queue.length - 1)) {
            end = -1;
        }
        queue[++end] = value;
        elements++;
    }
           

3、删除隊列

/**
     * 删除元素
     */
    public void delete() {
        if ((front == queue.length)) {
            front = -1;
        }
        queue[front] = -1;
        front++;
        elements--;
    }
           

4、檢視隊列元素

/**
     * 檢視隊列
     */
    public void display() {
        if (isEmpty()) {
            System.out.println("元素為空，請先插入元素");
        }
        for (int i = 0; i < queue.length; i++) {
            if (queue[i] == -1) {
                //X為占位符，表示該節點元素沒有元素
                System.out.print("X" + " ");
            } else {
                System.out.print(queue[i] + " ");
            }
        }
        System.out.println();
    }
           

5、檢視隊頭

/**
     * 檢視隊頭
     */
    public long getFront() {
        if (isEmpty()) {
            System.out.println("隊尾為空");
            return 0;
        }
        return queue[front];
    }
           

6、檢視隊尾

/**
     * 檢視隊尾
     */
    public long getEnd() {
        if (isEmpty()) {
            return -1;
        }
        return queue[end];
    }
           

7、檢視隊列元素個數

/**
     * 檢視隊列裡面幾個元素
     */
    public int size() {
        return elements;
    }
           

8、隊列是否為空

/**
     * 隊列是否為空
     */
    public boolean isEmpty() {
        return elements == 0;
    }
           

9、隊列是否滿了

/**
     * 隊列是否滿了
     */
    public boolean isFull() {
        return elements == queue.length;
    }
           

下一篇将介紹優先隊列。