java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips arrow java.lang arrow Array-based Queue Implementation in Java
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4092
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Array-based Queue Implementation in Java E-mail
User Rating: / 189
PoorBest 

In providing services in computer science, transport, and operations research a queue is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. The most well known operation of the queue is the First-In-First-Out (FIFO) queue process In a FIFO queue, the first element in the queue will be the first one out; this is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked.

There are two basic operations associated with a queue: enqueue and dequeue. Enqueue means adding a new item to the rear of the queue while dequeue refers to removing the front item from queue and returns it in item.

Following code shows how to implement a queue using arrays:

// 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 ObjectDEFAULT_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( )
    {
        ifisEmpty( ) )
            throw new UnderflowException"ArrayQueue dequeue" );
        currentSize--;

        Object returnValue = theArrayfront ];
        front = incrementfront );
        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( )
    {
        ifisEmpty( ) )
            throw new UnderflowException"ArrayQueue getFront" );
        return theArrayfront ];
    }

    /**
     * Insert a new item into the queue.
     @param x the item to insert.
     */
    public void enqueueObject x )
    {
        ifcurrentSize == theArray.length )
            doubleQueue( );
        back = incrementback );
        theArrayback = 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 incrementint )
    {
        if++x == theArray.length )
            x = 0;
        return x;
    }
    
    /**
     * Internal method to expand theArray.
     */
    private void doubleQueue( )
    {
        Object [ ] newArray;

        newArray = new ObjecttheArray.length * ];

            // Copy elements that are logically in the queue
        forint i = 0; i < currentSize; i++, front = incrementfront ) )
            newArray= theArrayfront ];

        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 UnderflowExceptionString message )
    {
        supermessage );
    }
}

// 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  enqueueObject 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( );
}

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.