java - 为什么基于数组的队列不能正常工作?
问题描述
我已经为基于数组的队列编写了代码。它的行为非常奇怪,就像我使用 for 循环将 0,1,2,3,4 排入队列,但插入队列的是 0,0,1,2,3。
dequeue 也在抛出ArrayOutOfBoundsException
,我不知道为什么。
我使用的入队逻辑是将元素放在一个简单的数组中。额外的一件事是,如果大小接近容量的一半,我会增加阵列的容量。
对于出队,如果大小小于容量的三分之一,我将减少容量。我还保留了一个弹出计数器,它从数组的开头弹出元素。
以下是我使用的代码:
class ArrayQueue {
private int[] arr;
private int size;
private int capacity;
private int popped = 0;
public ArrayQueue(int capacity) {
this.capacity = capacity;
size = 0;
arr = new int[capacity];
}
public int size() {
return size;
}
public int capacity() {
return capacity;
}
public void enqueue(int ele) {
size++;
if(size >= capacity/2) {
capacity = capacity*2;
int[] nArr = new int[capacity];
for(int i=0;i<size;i++)
nArr[i] = arr[i];
arr = nArr;
}
arr[size] = ele;
}
public void dequeue() {
size--;
System.out.println(arr[popped]+" removed");
if(size <= capacity/3) {
capacity = capacity/2;
int[] nArr = new int[capacity];
for(int i=0;i<size;i++)
nArr[i] = arr[i];
arr = nArr;
}
int[] nArr = new int[capacity];
for(int i=0;i<popped;i++)
nArr[i] = arr[i];
for(int i=popped+1;i<size;i++)
nArr[i-1] = arr[i];
arr = nArr;
popped++;
}
public boolean isEmpty() {
return (size == 0);
}
public void showQueue() {
for(int i=0;i<size;i++)
System.out.println("| "+arr[i]+" |");
}
}
public static void main(String[] args) {
ArrayQueue a = new ArrayQueue(10);
System.out.println("Starting size "+a.size());
for(int i=0;i<5;i++) {
a.enqueue(i);
System.out.println("Current size is "+a.size());
System.out.println("Current capacity is "+a.capacity());
}
System.out.println();
a.showQueue();
System.out.println();
a.dequeue();
System.out.println("Size: "+a.size());
System.out.println("Current capacity is "+a.capacity());
a.dequeue();
System.out.println("Size: "+a.size());
System.out.println("Current capacity is "+a.capacity());
a.dequeue();
System.out.println("Size: "+a.size());
System.out.println("Current capacity is "+a.capacity());
a.dequeue();
System.out.println("Size: "+a.size());
System.out.println("Current capacity is "+a.capacity());
}
我得到的输出是:
Starting size 0
Current size is 1
Current capacity is 10
Current size is 2
Current capacity is 10
Current size is 3
Current capacity is 10
Current size is 4
Current capacity is 10
Current size is 5
Current capacity is 20
| 0 |
| 0 |
| 1 |
| 2 |
| 3 |
0 removed
Size: 4
Current capacity is 10
1 removed
Size: 3
Current capacity is 5
0 removed
Size: 2
Current capacity is 5
0 removed
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
at ArrayQueue.dequeue(Code.java:228)
at Code.main(Code.java:76)
解决方案
进行deQueue()
操作时,应始终remove an element at index 0
. 所以你no need increment popped
。It should be always 0 (index 0)
public void dequeue() {
size--;
System.out.println(arr[popped] + " removed");
if (size <= capacity / 3) {
capacity = capacity / 2;
int[] nArr = new int[capacity];
for (int i = 0; i < size; i++)
nArr[i] = arr[i];
arr = nArr;
}
int[] nArr = new int[capacity];
/* for (int i = 0; i < popped; i++)
nArr[i] = arr[i]; //Not required as popped is always 0
*/
for (int i = popped + 1; i < size; i++)
nArr[i - 1] = arr[i];
arr = nArr;
//popped++; // not required as we remove first element
}
推荐阅读
- c# - 没有 ObjectID 的 MongoDb C# 类
- javascript - 不使用 allErrors 的带有 ajv 的自定义错误消息:true
- slack - Slack API - 仅对公共频道中的一组用户可见的持久消息
- vim - 交换行中的 1 和 0
- python - 在 Python 中使用基于 SOAP 的 Web 服务
- postgresql - 在每次迁移时更改 uuid 列的学说
- selenium - 如何检索 Selenium 中的会话存储(使用 Python)?
- windows - 什么是 RPC 控制 Windows 对象管理器命名空间?
- crosstab - 如何创建一个包含多个变量的交叉表,包括加权 p 值
- java - 如何使 Stream `max` 提前终止?