Массив основанные очереди реализации в Java

В предоставлении услуг в области компьютерной науки, транспорта и исследование операций очереди буфера, где хранятся различные организации, такие как данные, объекты, лица, или события, и ждет, чтобы быть обработаны. Наиболее известные эксплуатацию очереди First-In-First-Out (FIFO) очереди процесс в очереди FIFO, первый элемент в очереди будет одним из первых, это равносильно тому, что всякий раз, когда элемент добавлены, все элементы, которые были добавлены до, должны быть устранены до начала нового элемента может быть вызван.

Существуют два основных операций, связанных с очередью: епдиеие и йедиеие. Добавляет означает добавление нового элемента в задней части а Dequeue очередь ссылается на удаление переднего элемента из очереди и возвращает его в пункт.

Следующий код показывает, как реализовать очередь с помощью массивов:



// ArrayQueue class


//


// CONSTRUCTION: with no initializer


//


// ******************PUBLIC OPERATIONS*********************


// void enqueue( x )      --> Insert x


// Object getFront( )     --> Return least recently inserted item


// Object dequeue( )      --> Return and remove least recent item


// boolean isEmpty( )     --> Return true if empty; else false


// void makeEmpty( )      --> Remove all items


// ******************ERRORS********************************


// getFront or dequeue on empty queue





/**


 * Array-based implementation of the queue.


 * @author Mark Allen Weiss


 */


public class ArrayQueue implements Queue


{


    /**


     * Construct the queue.


     */


    public ArrayQueue( )


    {


        theArray = new Object[ DEFAULT_CAPACITY ];


        makeEmpty( );


    }





    /**


     * Test if the queue is logically empty.


     * @return true if empty, false otherwise.


     */


    public boolean isEmpty( )


    {


        return currentSize == 0;


    }





    /**


     * Make the queue logically empty.


     */


    public void makeEmpty( )


    {


        currentSize = 0;


        front = 0;


        back = -1;


    }





    /**


     * Return and remove the least recently inserted item


     * from the queue.


     * @return the least recently inserted item in the queue.


     * @throws UnderflowException if the queue is empty.


     */


    public Object dequeue( )


    {


        if( isEmpty( ) )


            throw new UnderflowException( "ArrayQueue dequeue" );


        currentSize--;





        Object returnValue = theArray[ front ];


        front = increment( front );


        return returnValue;


    }


    


    /**


     * Get the least recently inserted item in the queue.


     * Does not alter the queue.


     * @return the least recently inserted item in the queue.


     * @throws UnderflowException if the queue is empty.


     */


    public Object getFront( )


    {


        if( isEmpty( ) )


            throw new UnderflowException( "ArrayQueue getFront" );


        return theArray[ front ];


    }





    /**


     * Insert a new item into the queue.


     * @param x the item to insert.


     */


    public void enqueue( Object x )


    {


        if( currentSize == theArray.length )


            doubleQueue( );


        back = increment( back );


        theArray[ back ] = x;


        currentSize++;


    }





    /**


     * Internal method to increment with wraparound.


     * @param x any index in theArray's range.


     * @return x+1, or 0 if x is at the end of theArray.


     */


    private int increment( int x )


    {


        if( ++x == theArray.length )


            x = 0;


        return x;


    }


    


    /**


     * Internal method to expand theArray.


     */


    private void doubleQueue( )


    {


        Object [ ] newArray;





        newArray = new Object[ theArray.length * 2 ];





            // Copy elements that are logically in the queue


        for( int i = 0; i < currentSize; i++, front = increment( front ) )


            newArray[ i ] = theArray[ front ];





        theArray = newArray;


        front = 0;


        back = currentSize - 1;


    }





    private Object [ ] theArray;


    private int        currentSize;


    private int        front;


    private int        back;





    private static final int DEFAULT_CAPACITY = 10;


    


    


}





/**


 * Exception class for access in empty containers


 * such as stacks, queues, and priority queues.


 * @author Mark Allen Weiss


 */


public class UnderflowException extends RuntimeException


{


    /**


     * Construct this exception object.


     * @param message the error message.


     */


    public UnderflowException( String message )


    {


        super( message );


    }


}





// Queue interface


//


// ******************PUBLIC OPERATIONS*********************


// void enqueue( x )      --> Insert x


// Object getFront( )     --> Return least recently inserted item


// Object dequeue( )      --> Return and remove least recent item


// boolean isEmpty( )     --> Return true if empty; else false


// void makeEmpty( )      --> Remove all items


// ******************ERRORS********************************


// getFront or dequeue on empty queue





/**


 * Protocol for queues.


 * @author Mark Allen Weiss


 */


public interface Queue


{


    /**


     * Insert a new item into the queue.


     * @param x the item to insert.


     */


    void  enqueue( Object x );


    


    /**


     * Get the least recently inserted item in the queue.


     * Does not alter the queue.


     * @return the least recently inserted item in the queue.


     * @exception UnderflowException if the queue is empty.


     */


    Object getFront( );





    /**


     * Return and remove the least recently inserted item


     * from the queue.


     * @return the least recently inserted item in the queue.


     * @exception UnderflowException if the queue is empty.


     */


    Object dequeue( );





    /**


     * Test if the queue is logically empty.


     * @return true if empty, false otherwise.


     */


    boolean isEmpty( );





    /**


     * Make the queue logically empty.


     */


    void makeEmpty( );


}

Javist

Массив основанные очереди реализации в Java

Добавить комментарий Отменить ответ