1

我正在尝试使用数组实现队列。（不使用内置的 Java Queue 函数）。但是，在测试时，数组只会在 size ==maxSize 时打印出来（因为数组的大小达到了 maxSize/容量）。除了在大小小于 maxSize 时不打印之外，测试用例通过。（它是一个双端队列，因此可以在前后添加元素）。有什么建议吗？

package vipQueueArray;

import java.util.NoSuchElementException;


 public class vipQueue {

private Object[] array;
private int size = 0;
private int head = 0; // index of the current front item, if one exists
private int tail = 0; // index of next item to be added
private int maxSize;

public vipQueue(int capacity) {
    array = new Object[capacity];
    maxSize = capacity;
    size = 0;
    tail = maxSize - 1;

}

public Object Dequeue() {
    if (size == 0) {
        throw new NoSuchElementException("Cant remove: Empty");
    }
    Object item = array[head];
    array[head] = null;
    head = (head + 1) % array.length;
    size--;

    return item;

}

public void EnqueueVip(Object x) {
    if (size == maxSize) {
        throw new IllegalStateException("Cant add: Full");
    }

    array[tail] = x;
    tail = (tail - 1) % array.length;
    size++;

}

public void Enqueue(Object y) {
    if (size == maxSize) {
        throw new IllegalStateException("Cant add: Full");
    }
    array[head] = y;
    head = (head + 1) % array.length;
    size++;

}

public boolean isFull() {
    return (size == maxSize);
}

public boolean isEmpty() {
    return (size == 0);
}

}

public class Test{
         public static void main(String[] args){

             vipQueue Q = new vipQueue(2);
             Q.Enqueue(4);






        System.out.printf("->%d", Q.Dequeue());
         }  }
4

2 回答 2

4

在出队中你正在做：

head = (head + 1) % array.length;

您应该（根据您的 impl.）将其更改为：

head = (head - 1) % array.length;

加法：

这不是队列的实现：队列在 FIFO 中工作，而您实现的工作后进先出，实际上更像是一个......堆栈。

为了实现队列，您应该从指向数组 [0] 的头部和尾部开始。然后每个插入都addAtTail()意味着该项目将在 array[tail] 输入：

array[tail] = item;
tail++;
size++;

当 tail == array.length （抛出异常）时停止插入。

出队意味着删除项目array[tail-1]然后执行：

tail--;
size--;
于 2013-09-23T04:16:42.173 回答
1

当你入队时，你设置 head = head + 1。当你出队时，你返回 array[head]

因此，在 Enqueue 之后，head = 1，但您添加的项目在插槽 0 中。

此外，tail = capacity-1，当队列中没有任何内容时，必然会造成麻烦。恩

于 2013-09-23T04:16:36.140 回答