java - 不理解队列实现的代码

Question

我很难理解 java 中队列实现的某些部分。我需要帮助理解代码。我对编程比较陌生。这不是我的代码。如果有人用一个小例子来解释，将会很有帮助。

在enqueue方法中，rear ==capacity - 1条件做了什么？

在dequeue方法中，front ==capacity - 1条件做了什么？

public class QueueImpl {

    private int capacity;
    int queueArr[];
    int front = 0;
    int rear = -1;
    int currentSize = 0;

    public QueueImpl(int queueSize){
        this.capacity = queueSize;
        queueArr = new int[this.capacity];
    }

    /**
     * this method adds element at the end of the queue.
     * @param item
     */
    public void enqueue(int item) {
        if (isQueueFull()) {
            System.out.println("Overflow ! Unable to add element: "+item);
        } else {
            rear++;
            if(rear == capacity-1){
                rear = 0;
            }
            queueArr[rear] = item;
            currentSize++;
            System.out.println("Element " + item+ " is pushed to Queue !");
        }
    }

    /**
     * this method removes an element from the top of the queue
     */
    public void dequeue() {
        if (isQueueEmpty()) {
            System.out.println("Underflow ! Unable to remove element from Queue");
        } else {
            front++;
            if(front == capacity-1){
                System.out.println("Pop operation done ! removed: "+queueArr[front-1]);
                front = 0;
            } else {
                System.out.println("Pop operation done ! removed: "+queueArr[front-1]);
            }
            currentSize--;
        }
    }

    /**
     * This method checks whether the queue is full or not
     * @return boolean
     */
    public boolean isQueueFull(){
        boolean status = false;
        if (currentSize == capacity){
            status = true;
        }
        return status;
    }

    /**
     * This method checks whether the queue is empty or not
     * @return
     */
    public boolean isQueueEmpty(){
        boolean status = false;
        if (currentSize == 0){
            status = true;
        }
        return status;
    }
}

Answer 1

尝试可视化项目如何存储在内部 queueArr[] 数组中。这不是您天真的做法，但是让我们首先看一下这个概念。

<小时/>

在天真的概念中，您将队列的第一个元素存储在queueArr[0]中，第二个元素存储在queueArr[0]中> 在 queueArr[1] 处，在 queueArr[queueArr.length - 1] 处的最后一个元素，依此类推。

但是，如果出现新元素或者应该删除一个元素，您会怎么做？然后，您要么需要创建一个容量更大的新阵列并将所有内容复制到新阵列，要么之间存在间隙。

<小时/>

您的队列实现有一个更好的概念，它将元素循环存储在数组中。

假设您有一个完整的数组。然后删除第一个元素，第一个槽 queueArr[0] 现在为空。现在您想在末尾插入一个新元素。现在，您将其插入 queueArr[0] 并重用该空白空间。

由于数据结构开始和结束位置的含义现在是可变的，因此您需要使用 rear 和 front 变量来记住它。

下面是一张 Google 搜索结果的小图片，演示了这种技术:

<小时/>

条件 rear ==capacity - 1 和 front ==capacity - 1 现在可以准确处理我上面描述的情况。如果数组已满，但开始索引中有间隙，则您将在其中插入新元素，因此数组的后部位于开始索引处。在上面的示例中，rear 首先位于 queueArr.length - 1，之后位于 0。

详细:
一旦 rear 指针位于数组的右端(请注意，capacity 与 queueArr.length 相同)。
如果它解析为true，那么您的代码将执行rear = 0;，将指针设置回数组的开头。因此，它在数组中从左到右徘徊，然后又回到左。

与front指针类似。

<小时/>

请注意，这个概念之所以有效，只是因为队列不允许在其间删除或插入，您只能在开头或结尾更改某些内容。否则内部数据将无法再连接。