调整圆形数组的大小,在双端队列实现中
Resizing circular array, in deque implementation
我正在尝试使用循环数组实现双端队列,这里是我的代码(对不起 post 整个 class)
public class Deque<Item> implements Iterable<Item> {
private int frontIndex;
private int backIndex;
private static final int defaulSize = 8;
private int size;
private Item holder[];
private int capacity;
public Deque() {
holder = (Item[]) new Object[defaulSize];
this.size = 0;
this.frontIndex = 0;
this.backIndex = 0;
this.capacity = defaulSize;
}
public boolean isEmpty() {
return this.size == 0;
}
public int size() {
return this.size;
}
public void addFirst(Item item) throws Exception {
if (item == null) {
throw new NoSuchElementException();
}
if (size == capacity) {
doubleCapacity();
}
holder[this.frontIndex] = item;
this.frontIndex = Math.floorMod((this.frontIndex + 1), capacity);
size++;
}
public void addLast(Item item) throws Exception {
if (item == null) {
throw new NoSuchElementException();
}
if (size == capacity) {
doubleCapacity();
}
holder[this.backIndex] = item;
this.backIndex = Math.floorMod((this.backIndex - 1), capacity);
size++;
}
public Item removeFirst() throws Exception {
if (isEmpty()) {
throw new Exception("Deque is empty.");
}
this.frontIndex = Math.floorMod((this.frontIndex - 1), capacity);
this.size--;
Item e = holder[this.frontIndex];
holder[this.frontIndex] = null;
return e;
}
public Item removeLast() throws Exception {
if (isEmpty()) {
throw new Exception("Deque is empty.");
}
this.backIndex = Math.floorMod((this.backIndex + 1), capacity);
this.size--;
Item e = holder[this.backIndex];
holder[this.backIndex] = null;
return e;
}
private void doubleCapacity() {
int p = this.backIndex;
int n = holder.length;
int r = n - p; // number of elements to the right of p
capacity = (n) * 2;
Object[] a = new Object[capacity];
System.arraycopy(holder, p, a, 0, r);
System.arraycopy(holder, 0, a, r, p);
holder = (Item[]) a;
this.backIndex = n;
this.frontIndex = 0;
}
private class DequeIterator<E> implements Iterator<E> {
private int pos = 0;
public boolean hasNext() {
return holder.length > pos;
}
public E next() {
return (E) holder[pos++];
}
public void remove() {
throw new UnsupportedOperationException("Cannot remove an element of an array.");
}
}
@Override
public Iterator<Item> iterator() {
return this.new DequeIterator<Item>();
}
}
当我尝试使用 deque 调整循环数组大小时出现问题,似乎所有索引都被弄乱了
我使用了类似于 java 实现中的方法来进行实验
private void doubleCapacity() {
int p = this.backIndex;
int n = holder.length;
int r = n - p; // number of elements to the right of p
capacity = (n) * 2;
Object[] a = new Object[capacity];
System.arraycopy(holder, p, a, 0, r);
System.arraycopy(holder, 0, a, r, p);
holder = (Item[]) a;
this.backIndex = n;
this.frontIndex = 0;
}
如果循环数组用作双端队列,是否有特定的方法来调整其大小,或者我如何调整此双端队列的大小
(这不是家庭作业,只是个人学习)
这个问题基本上是因为
1- 向双端队列添加项目时没有正确更新 frontIndex 和 backIndex
2- 将容量加倍时没有使用正确的索引。
问题 1
当 frontIndex 和 backIndex 相等并且您要在双端队列的任何入口点添加元素时,您需要同时更新它们,否则您将失去对双端队列的控制。示例:开始时 frontIndex 和 backIndex 都是 ==0。如果你添加一个项目让我们说在前面,之后你将有 frontIndex=1 (正确)和 backIndex=0 (不正确,因为位置 0 被新项目占据)。这有很多副作用
1
的解
public void addFirst(Item item) throws Exception {
... unchanged handling of capacity...
holder[this.frontIndex] = item;
//CHECK OF THE 2 INDEXES
if(this.frontIndex==this.backIndex){
this.backIndex= floorMod((this.backIndex - 1), capacity);
}
this.frontIndex = floorMod((this.frontIndex + 1), capacity);
size++;
}
public void addLast(Item item) throws Exception {
... unchanged handling of capacity...
holder[this.backIndex] = item;
if(this.frontIndex==this.backIndex){
this.frontIndex= floorMod((this.frontIndex + 1), capacity);
}
this.backIndex = floorMod((this.backIndex - 1), capacity);
size++;
}
注意问题也存在于删除函数中,您应该正确处理它。我没有时间处理它,但解决方案很简单
问题2
您总是使用 backIndex(概念上没问题)来处理新数组中项目的副本,但理想情况下 backIndex 指向 Deque 中第一个元素之前的位置因此使用该值会使 Deque 本身更加混乱。
此外,您将完全错误的索引分配给 new backIndex(它应该等于新创建数组的最后一个元素的索引,而不是 n,它指的是 old数组)和frontIndex(应该等于位置n,即最后一个填充项之后的一个元素)。
2 的解决方案
private void doubleCapacity() {
int p = floorMod((this.backIndex+1 ), capacity);
int n = holder.length;
int r = n - p; // number of elements to the right of p
capacity = (n) * 2;
Object[] a = new Object[capacity];
System.arraycopy(holder, p, a, 0, r);
System.arraycopy(holder, 0, a, r, p);
holder = (Item[]) a;
//backIndex should be the last element of the whole array
this.backIndex = capacity-1;
//frontIndex must be 1 after the last element of the portio of array populated by items
this.frontIndex = n;
}
作为设计,我会将 frontIndex 和 backIndex 处理为双端队列中第一个和最后一个元素的(循环)索引,而不是它们之前和之后的索引。但这只是我的方式。
我正在尝试使用循环数组实现双端队列,这里是我的代码(对不起 post 整个 class)
public class Deque<Item> implements Iterable<Item> {
private int frontIndex;
private int backIndex;
private static final int defaulSize = 8;
private int size;
private Item holder[];
private int capacity;
public Deque() {
holder = (Item[]) new Object[defaulSize];
this.size = 0;
this.frontIndex = 0;
this.backIndex = 0;
this.capacity = defaulSize;
}
public boolean isEmpty() {
return this.size == 0;
}
public int size() {
return this.size;
}
public void addFirst(Item item) throws Exception {
if (item == null) {
throw new NoSuchElementException();
}
if (size == capacity) {
doubleCapacity();
}
holder[this.frontIndex] = item;
this.frontIndex = Math.floorMod((this.frontIndex + 1), capacity);
size++;
}
public void addLast(Item item) throws Exception {
if (item == null) {
throw new NoSuchElementException();
}
if (size == capacity) {
doubleCapacity();
}
holder[this.backIndex] = item;
this.backIndex = Math.floorMod((this.backIndex - 1), capacity);
size++;
}
public Item removeFirst() throws Exception {
if (isEmpty()) {
throw new Exception("Deque is empty.");
}
this.frontIndex = Math.floorMod((this.frontIndex - 1), capacity);
this.size--;
Item e = holder[this.frontIndex];
holder[this.frontIndex] = null;
return e;
}
public Item removeLast() throws Exception {
if (isEmpty()) {
throw new Exception("Deque is empty.");
}
this.backIndex = Math.floorMod((this.backIndex + 1), capacity);
this.size--;
Item e = holder[this.backIndex];
holder[this.backIndex] = null;
return e;
}
private void doubleCapacity() {
int p = this.backIndex;
int n = holder.length;
int r = n - p; // number of elements to the right of p
capacity = (n) * 2;
Object[] a = new Object[capacity];
System.arraycopy(holder, p, a, 0, r);
System.arraycopy(holder, 0, a, r, p);
holder = (Item[]) a;
this.backIndex = n;
this.frontIndex = 0;
}
private class DequeIterator<E> implements Iterator<E> {
private int pos = 0;
public boolean hasNext() {
return holder.length > pos;
}
public E next() {
return (E) holder[pos++];
}
public void remove() {
throw new UnsupportedOperationException("Cannot remove an element of an array.");
}
}
@Override
public Iterator<Item> iterator() {
return this.new DequeIterator<Item>();
}
}
当我尝试使用 deque 调整循环数组大小时出现问题,似乎所有索引都被弄乱了
我使用了类似于 java 实现中的方法来进行实验
private void doubleCapacity() {
int p = this.backIndex;
int n = holder.length;
int r = n - p; // number of elements to the right of p
capacity = (n) * 2;
Object[] a = new Object[capacity];
System.arraycopy(holder, p, a, 0, r);
System.arraycopy(holder, 0, a, r, p);
holder = (Item[]) a;
this.backIndex = n;
this.frontIndex = 0;
}
如果循环数组用作双端队列,是否有特定的方法来调整其大小,或者我如何调整此双端队列的大小
(这不是家庭作业,只是个人学习)
这个问题基本上是因为
1- 向双端队列添加项目时没有正确更新 frontIndex 和 backIndex
2- 将容量加倍时没有使用正确的索引。
问题 1
当 frontIndex 和 backIndex 相等并且您要在双端队列的任何入口点添加元素时,您需要同时更新它们,否则您将失去对双端队列的控制。示例:开始时 frontIndex 和 backIndex 都是 ==0。如果你添加一个项目让我们说在前面,之后你将有 frontIndex=1 (正确)和 backIndex=0 (不正确,因为位置 0 被新项目占据)。这有很多副作用
1
的解 public void addFirst(Item item) throws Exception {
... unchanged handling of capacity...
holder[this.frontIndex] = item;
//CHECK OF THE 2 INDEXES
if(this.frontIndex==this.backIndex){
this.backIndex= floorMod((this.backIndex - 1), capacity);
}
this.frontIndex = floorMod((this.frontIndex + 1), capacity);
size++;
}
public void addLast(Item item) throws Exception {
... unchanged handling of capacity...
holder[this.backIndex] = item;
if(this.frontIndex==this.backIndex){
this.frontIndex= floorMod((this.frontIndex + 1), capacity);
}
this.backIndex = floorMod((this.backIndex - 1), capacity);
size++;
}
注意问题也存在于删除函数中,您应该正确处理它。我没有时间处理它,但解决方案很简单
问题2
您总是使用 backIndex(概念上没问题)来处理新数组中项目的副本,但理想情况下 backIndex 指向 Deque 中第一个元素之前的位置因此使用该值会使 Deque 本身更加混乱。 此外,您将完全错误的索引分配给 new backIndex(它应该等于新创建数组的最后一个元素的索引,而不是 n,它指的是 old数组)和frontIndex(应该等于位置n,即最后一个填充项之后的一个元素)。
2 的解决方案
private void doubleCapacity() {
int p = floorMod((this.backIndex+1 ), capacity);
int n = holder.length;
int r = n - p; // number of elements to the right of p
capacity = (n) * 2;
Object[] a = new Object[capacity];
System.arraycopy(holder, p, a, 0, r);
System.arraycopy(holder, 0, a, r, p);
holder = (Item[]) a;
//backIndex should be the last element of the whole array
this.backIndex = capacity-1;
//frontIndex must be 1 after the last element of the portio of array populated by items
this.frontIndex = n;
}
作为设计,我会将 frontIndex 和 backIndex 处理为双端队列中第一个和最后一个元素的(循环)索引,而不是它们之前和之后的索引。但这只是我的方式。