Реализация очереди с использованием кругового массива

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. В очереди есть 5 методов, включая enqueue, dequeue, isEmpty, clear, head.
2. В моем коде метод head возвращает элемент в передней позиции
3. isEmpty возвращает true, если item_num = 0
4. Метод очистки очищает очередь
5. Метод enqueue должен добавлять элементы после заднего и увеличивать задний на 1. Я думаю, у меня есть какая-то ошибказдесь
6. Метод dequeue возвращает первый элемент и удаляет его.Тем не менее, у меня ошибка.Можете ли вы сказать мне несколько советов?Заранее спасибо.

Answer 1

Есть много логических ошибок. Трудно найти правильную вещь, реализованную в вашем коде.

пытается ответить на вопрос

(1) вам действительно нужно сделать front = B.length - (rear - front) внутри grow(), когда вы уже знаете, что grow () вызывается при заполнении массива / очереди
(2) если условие if () имеет значение true, что вы делаете?
скажем сначала A = [1 2 3 4], front = 3, Rear = 2, тогда ваш новый массив будет [1 2 3 4 0 0 0 0] с одинаковыми значениями front и back. Это действительно?
(3) также проверьте логику enque и deque.
(4) рассмотрите сериализацию данных очереди, иначе они перейдут в противоречивое состояние.
(5) для простоты вы можете просто использовать заднюю длину = (задняя + 1)%, проверять не нужно, если нет необходимости.

Answer 2

Проще говоря, в кольцевом массиве всякий раз, когда указатель перемещается, вы должны проверить его и при необходимости исправить. Вы не делаете это в dequeue.

Логика внутри enqueue также неверна.

Наконец, у вас есть два указателя и счетчик. Вам не нужно три вещи, только две.

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]