Dequeue 方法未正确删除队列中的元素

Question

我的出队方法目前也没有删除我想要的项目，而是删除了集合中的最后一个元素。例如，

如果我加入元素：1, 2, 3 我的 toString 方法将按预期 return 1、2、3。

然后当我使用我的驱动程序调用 dequeue 时，它应该使第 0 个元素出列，在本例中为 1。

尽管该方法显示“已从队列中删除元素 1”，提示 T result 变量包含正确的值，但该方法并未按预期工作，因为在 to 之后调用 toString 方法时打印内容，会打印：1, 2

然后当我再次调用 enqueue 方法时，在同一个队列上，如果我将 String 3 入队，它将打印为新队列：3, 2, 3

我对我的逻辑错误在哪里感到困惑，因为我假设它是在集合被填充的极端情况下，但我仍然运行在集合未填充时使用我的 dequeue 方法出错在最大值我在下面附上了我的代码。

public class QueueRA<T> implements QueueInterface<T> {

    protected T[] items;
    protected int front, back, numItems; 
    
    @SuppressWarnings("unchecked")
    public QueueRA() {
        front = 0;
        numItems = 0;
        back = 0;
        items = (T[]) new Object[3];    
    }
    
    @Override
    public boolean isEmpty() {
        return numItems == 0;
    }

    @Override
    public void enqueue(T newItem) throws QueueException {
        if(numItems == items.length) {
            resize();
            enqueue(newItem);
        }
        else {
            items[back] = newItem;
            back = (back + 1) % items.length;
            numItems++;
        }
    }

    @Override
    public T dequeue() throws QueueException {
        T result;
        if(numItems != 0) {
            result = items[front];
            items[front] = null;
            front = (front + 1) % items.length;
            numItems--;
        }
        else {
            throw new QueueException("The queue does not contain any elements.");
        }
        return result;
    }

    @SuppressWarnings("unchecked")
    @Override
    public void dequeueAll() {
        back = 0;
        front = 0;
        numItems = 0;
        items = (T[]) new Object[3];
    }

    @Override
    public T peek() throws QueueException {
        T result;
        if(numItems != 0) {
            result = items[front];
        }
        else {
            throw new QueueException("The queue does not contain any elements.");
        }
        
        return result;
    }
    
    /**
     * 
     */
    @SuppressWarnings("unchecked")
    protected void resize() {
        T[] newItems = (T[]) new Object[numItems+4];
        
        for(int i = 0; i < numItems; i++) {
            newItems[i] = items[i];
        }
        
        this.front = 0;
        this.back = numItems;
        this.items = newItems;
    }

    /**
     * 
     */
    public String toString() {
        String toReturn = "";
        for(int i = 0; i < numItems; i++) {
            if( (i+1) == numItems) {
                toReturn = toReturn.concat(items[i] + " ");
            }
            else {
                toReturn = toReturn.concat(items[i] + ", ");
            }
        }
        return toReturn;
    }
    
}

Answer 1

你的 toString() 和 resize() 方法是错误的。

在你的示例代码中，你最初创建了一个arraySize为3，然后添加了1、2、3。这占据了数组中的所有3个槽位，你的numItems设置为3。前面设置为0和 back 也设置为 0 因为加 3 后，你的算法是：

back = (back+1)%items.length;

back 最初为 2。现在计算为：

-> (2+1)%3
-> 3%3
-> 0

所以此时你的背是0。

现在，调用dequeue()时，前端弹出1。所以现在你的数组看起来像这样：
项目[0] -> 空
项目[1] -> 2
项目[2] -> 3
返回 = 0
正面=1

因此，当您对 next 进行排队并添加 3 时，您的 enqueue() 方法会检查系统中的项目数是否小于数组的大小 (2 < 3) 并将 3 添加到后面指向的位置（现在为 0）并将其递增为 1。因此，您的数组现在看起来像这样：
项目[0] -> 3
项目[1] -> 2
项目[2] -> 3
返回 = 1
前=1

现在，在你的 toString() 方法中，不考虑 front 和 back 的值，你从 0 开始到结束：

for(int i = 0; i < numItems; i++) {
.
.
.
}

你需要做的是从 i = front 开始。如果前面 < 后面，这意味着您从“前面”到“后面”线性移动并打印所有内容。如果 front > back 那么你做两个循环：

for(int i=front; i < arr.length; i++) {
// Code to print arr[i]
}

for(int i=0; i < back; i++) {
// Code to print arr[i]
}

这样就从前到尾打印，再从0到后打印。

同样，您的调整大小方法也是错误的。您不能从 0 复制到 numItems，您需要从“前面”开始复制，然后像我为 toString() 编写的那样进行。这样做将确保您的队列顺序在多次调整大小后得以保留。

Answer 2

正在添加到。

您的 resize() 方法只是将所有元素按顺序从 items 复制到 newItems，然后设置 front = 0 和 back = numItems。如果您按顺序实现队列，那会很好。但是，您对队列的实现不是顺序的，它是循环/环形实现。因此，你必须以循环方式复制元素。

@ArunSubramanian 的回答中提到了一种方法，“如果 front < back，这意味着您从 front 线性移动到 back 并打印一切。如果 front > back 那么你做两个循环。“ 另一种方法是使用具有模块化算法的 do-while 循环，如下所示：

@SuppressWarnings("unchecked")
protected void resize() {
    T[] newItems = (T[]) new Object[numItems + 4];
    
    int i = 0; // index used to copy items to newItems
    // do-while used in case the queue is full (i.e. front == back)
    do {
        newItems[i] = items[front];

        // modular arithmetic used to circle back on items
        front = (front + 1) % items.length;
        i += 1;
    } while(front != back);
    
    this.front = 0;
    this.back = numItems;
    this.items = newItems;
}

同样，您的 toString() 方法可以通过以下方式实现：

@Override
public String toString() {
    String toReturn = "";
    
    // need this check, otherwise do-while will illegally access items[0]
    if(!isEmpty()) {
        int len = items.length;
        int i = front;
        
        // do-while used in case front == back
        do {
            String delim = ((i+1) % len == back) ? " " : ", ";

            toReturn += items[i] + delim;
            
            i = (i+1) % len; // modular arithmetic used to circle back
        } while(i != back);
    }
    return toReturn;
}

Dequeue 方法未正确删除队列中的元素

Dequeue method not correctly deleting elements within queue

java

queue