实现一个循环队列

循环队列 - 实现

在循环队列中，我们使用一个数组和两个指针（head 和 tail）来实现。 head 表示队列的起始位置，tail 表示队列的结束位置。首，尾循环充分利用存储资源。

class MyCircularQueue {
    int[] data;
    int head_index = -1;
    int tail_index = -1;
    int tail_next_index = 0;
    int length = 0;

    /**
     * Initialize your data structure here. Set the size of the queue to be k.
     */
    public MyCircularQueue(int k) {
        data = new int[k];
        length = data.length;
    }

    /**
     * Insert an element into the circular queue. Return true if the operation is successful.
     */
    public boolean enQueue(int value) {
        if (tail_index == -1 && head_index == -1) {
            tail_index = 0;
            head_index = 0;
            data[tail_index] = value;
            return true;
        }
        tail_next_index = tail_index + 1;
        if (tail_index == length - 1) {
            tail_next_index = 0;
        }
        if (tail_next_index == head_index) {
            return false;
        }
        tail_index = tail_next_index;
        data[tail_index] = value;
        return true;
    }

    /**
     * Delete an element from the circular queue. Return true if the operation is successful.
     */
    public boolean deQueue() {
        if (head_index == -1 && tail_index == -1) {
            return false;
        }
        if (head_index == tail_index) {
            head_index = -1;
            tail_index = -1;
            return true;
        }
        head_index++;
        return true;
    }

    /**
     * Get the front item from the queue.
     */
    public int Front() {
        if (head_index == -1) {
            return -1;
        }
        return data[head_index];
    }

    /**
     * Get the last item from the queue.
     */
    public int Rear() {
        if (tail_index == -1) {
            return -1;
        }
        return data[tail_index];
    }

    /**
     * Checks whether the circular queue is empty or not.
     */
    public boolean isEmpty() {
        if (head_index == -1 && tail_index == -1) {
            return true;
        }
        return false;
    }

    /**
     * Checks whether the circular queue is full or not.
     */
    public boolean isFull() {
        tail_next_index = tail_index + 1;
        if (tail_index == length - 1) {
            tail_next_index = 0;
        }
        if (tail_next_index == head_index) {
            return true;
        }
        return false;
    }
}

用例

        MyCircularQueue obj = new MyCircularQueue(3);
        System.out.println(obj.enQueue(1));
        System.out.println(obj.enQueue(2));
        System.out.println(obj.enQueue(3));
        System.out.println(obj.enQueue(4));
        System.out.println(obj.Rear());
        System.out.println(obj.isFull());
        System.out.println(obj.deQueue());
        System.out.println(obj.enQueue(4));
        System.out.println(obj.Rear());

true
true
true
false
3
true
true
true
4

总结

队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。删除（delete）操作也被称为出队（dequeue)，只能移除第一个元素。使用固定大小的数组和两个指针来指示起始位置和结束位置。目的是重用删除的存储空间。
实现的过程中，最重要的就是理解整个插入数据和消费数据的指针变化，才能准确的实现！！