取消排队方法未正确删除队列中的元素

Question

我的取消排队方法目前也不会删除我想要的项，而是从集合中删除最后一个元素。例如

如果我添加元素：1，2，3我的toString方法将按预期返回1，2，3。

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

尽管该方法表示“已从队列中删除元素1”，提示＜code＞T result

然后，当我再次调用enqueue方法时，在同一个队列上，如果我将字符串3入队，它将把它打印为新的队列:3，2，3

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

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

添加到@Arun Subramanian的答案中。

您的 resize（） 方法只是将所有元素从项目按顺序复制到 newItems，然后将前 = 0 和后 = 数字项。如果您按顺序实现队列，那会很好。但是，队列的实现不是顺序的，而是循环/环形实现。因此，您必须以循环方式复制元素。

@ArunSubramanian的回答中提到了一种方法，“如果< code>front

@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;
}

类似地，您的＜code＞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;
}

Answer 2

你的toString（）和调整大小（）方法是错误的。

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

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

回来最初是2。现在它的计算公式为：

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

所以此时你的背部是0。

现在，当您调用dequeue()时，前面会弹出1。所以现在你的数组看起来像这样:< br>items[0] -

现在，在您的toString（）方法中，不考虑前面和后面的值，您从0开始到结束：

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

你需要做的是从i = front开始。如果前面

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复制到数字项目，你需要在“前面”开始复制，然后像我为toString（）写的那样前进。这样做将确保在多次调整大小时保持队列的顺序。