使用循环数组实现队列

Question

我正在尝试使用数组来实现队列。但我的实施不起作用。我找不到错误。我的实现如下：

class ArrayQueue[T: ClassManifest] extends Queue[T] {
private var A = new Array[T](2) // array for storing the queue elements
private var front = 0           // index of the front element in the array
private var rear = 0            // index of the rear element in the array
private var item_num = 0        // number of elements that are in the array


// when an array overflows we double the size of the array
private def grow() {            
    val B = A
    A = new Array[T](2 * B.length)
    if (front < rear) {
        for ( i <- 0 until B.length)
            A(i) = B(i)
            }
    else {
        System.arraycopy(B, rear, A, 0, B.length - rear)
        System.arraycopy(B, 0, A, B.length-rear, front)
        front = B.length - (rear - front)
        rear = 0
        }
}



def clear(): Unit = {     
    A = new Array[T](22)
    front = 0
    rear = 0
    item_num = 0 
    }


def isEmpty: Boolean = (item_num == 0) 


def head = { 
    if (isEmpty)
        throw new NoSuchElementException
    A(front)
    }


def dequeue(): T = {    
    if (isEmpty)
        throw new NoSuchElementException    
    front += 1  
    item_num = item_num - 1
    A(front - 1)


}

def enqueue(elem: T): Unit = {  

    A(rear) = elem
    rear += 1
    item_num += 1 
    if (rear == A.length - 1 && item_num != A.length)
        rear = 0
    if (item_num == A.length || rear == front - 1) {
        grow()
        }
    if (item_num == 0) {
        front = 0 
        rear = 0 }


    } 

1. Queue 有 5 个方法，包括 enqueue、dequeue、isEmpty、clear、head。
2. 在我的代码中，head方法返回前面位置的元素，
3. 如果item_num = 0，则isEmpty返回true。Clear
4. 方法清除队列
5. ，方法enqueue必须在rear后面添加元素，并将rear增加1。我想我在这里有一些错误，
6. 方法dequeue返回第一个元素并将其删除。 但是，我有一个错误。你能告诉我一些提示吗？先感谢您。

Answer 1

简单来说，在循环数组中，每当指针移动时，你就必须检查它，并在必要时修复它。您不会在出队中执行此操作。

enqueue 内部的逻辑也不正确。

最后，您有两个指针和一个计数器。你不应该需要三样东西，只需要两样。

Answer 2

有很多逻辑错误。很难找到代码中实现的任何正确的东西。

尝试回答以下问题

（1）当您已经知道grow()是时，您真的需要在grow()内执行front = B.length - (rear - front)吗当数组/队列已满时调用
(2) 如果 if() 条件评估为 true，你在做什么？
假设最初 A=[1 2 3 4]，front =3，rear =2，那么你的新数组将是 [1 2 3 4 0 0 0 0]，具有相同的前后值。有效吗？
(3) 还检查 enque 和 deque 逻辑。
(4) 考虑队列数据的序列化，否则会处于不一致的状态。
(5)为了缓解，你可以简单地使用rear = (rear+1)%length，不需要检查，不需要if。

Answer 3

我在这里发布了在java中使用数组实现循环队列的完整代码。
Trim()：修剪数组的大小。

package com.java.util.collection.advance.datastructure.queue;

public interface Queue<E>{


    boolean addR(E e);


    E removeL();


    E element();


    boolean isFull();


    boolean isEmpty();

    void trim();
}



package com.java.util.collection.advance.datastructure.queue;

public interface CircularQueue<E> extends Queue<E>{

}


package com.java.util.collection.advance.datastructure.queue;

import java.util.Arrays;

public class MyCircularQueue<E> implements CircularQueue<E>{

    private int front = 0;
    private int rear =-1;
    private E[] elements =null;
    private static final int DEFAULT_INTIAL_CAPACITY =100; 
    private int size =0;

    public MyCircularQueue(){
        this(DEFAULT_INTIAL_CAPACITY);
    }
    @SuppressWarnings("unchecked")
    public MyCircularQueue(int intialCapacity){
        if(intialCapacity < 0){
            throw new IllegalArgumentException("intial capacity can't be null");
        }
        elements =(E[]) new Object[intialCapacity];
    }
    @Override
    public boolean addR(E e) {
        if(! isFull()) {
            rear = (rear+1)%elements.length;
            elements[rear] = e;
            size++;
            return true;
        }
        return false;
    }



    @Override
    public E removeL() {
        E element =null;
        if(!isEmpty()){
            if(front == elements.length-1)
            {
                front =(front+1)%elements.length;
            } 
            element=elements[front];
            // Nullify the reference
            elements[front] =null;
            front++;
            --size;
        }
        return element;
    }

    @Override
    public E element() {
        E element =null;
        if(!isEmpty()){
            element=elements[front];
        }
        return element;
    }

    @Override
    public boolean isFull() {
        return size == elements.length;
    }

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

    @Override
    // Do Nothing
    public void trim() {
        @SuppressWarnings("unchecked")
        E[]dest =(E[]) new Object[size];
        if(front < rear) {
            System.arraycopy(elements, front, dest, front-1,rear);
        } else {
            System.arraycopy(elements, front, dest, 0, size-front+1);
            System.arraycopy(elements, 0, dest, size-front+1, front-rear);
            front =0;
            rear = size;
        }
        elements =dest;
    }
    @Override
    public String toString() {
        return "MyCircularQueue [front=" + front + ", rear=" + rear
                + ", elements=" + Arrays.toString(elements) + ", size=" + size
                + "]";
    }



}

测试类：

package com.java.util.collection.advance.datastructure.queue;

import java.util.Random;

public class MyCircularQueueApp<E> {

    public static void main(String[] args) {

        CircularQueue<Integer> cirQueue =new MyCircularQueue<Integer>(11);
        Random random =new Random();
        for(int i=0;i<10;i++){
            cirQueue.addR(random.nextInt(3));
        }

        System.out.println(cirQueue);
        cirQueue.removeL();
        System.out.println("Before triming: "+cirQueue);
        cirQueue.trim();
        System.out.println("After triming: "+cirQueue);
        cirQueue.removeL();

        System.out.println(cirQueue);
        cirQueue.addR(1000);
        System.out.println(cirQueue);
        cirQueue.addR(10000);
        cirQueue.addR(100000);
        System.out.println(cirQueue);
        System.out.println(cirQueue.element());
    }
}

输出：

MyCircularQueue [front=0, rear=9, elements=[1, 2, 2, 2, 1, 2, 2, 1, 2, 1, null], size=10]
Before triming: MyCircularQueue [front=1, rear=9, elements=[null, 2, 2, 2, 1, 2, 2, 1, 2, 1, null], size=9]
After triming: MyCircularQueue [front=1, rear=9, elements=[2, 2, 2, 1, 2, 2, 1, 2, 1], size=9]
MyCircularQueue [front=2, rear=9, elements=[2, null, 2, 1, 2, 2, 1, 2, 1], size=8]
MyCircularQueue [front=2, rear=1, elements=[2, 1000, 2, 1, 2, 2, 1, 2, 1], size=9]
MyCircularQueue [front=2, rear=1, elements=[2, 1000, 2, 1, 2, 2, 1, 2, 1], size=9]