队列(链表实现) Java 代码

队列(链表实现) Java 代码
// ListQueue 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
/**
* List-based implementation of the queue.
* @author Mark Allen Weiss
*/
public class ListQueue implements Queue {
    /**
     * Construct the queue.
     */
    public ListQueue( ) {
        front = back = null;
    }
    /**
     * Test if the queue is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty( ) {
        return front == null;
    }
    /**
     * Insert a new item into the queue.
     * @param x the item to insert.
     */
    public void enqueue( Object x ) {
        if( isEmpty( ) )    // Make queue of one element
            back = front = new ListNode( x );
        else                // Regular case
            back = back.next = new ListNode( x );
    }
    /**
     * 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( "ListQueue dequeue" );
        Object returnValue = front.element;
        front = front.next;
        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( "ListQueue getFront" );
        return front.element;
    }
    /**
     * Make the queue logically empty.
     */
    public void makeEmpty( ) {
        front = null;
        back = null;
    }
    private ListNode front;
    private ListNode back;
}
/**
* 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 );
    }
}
// Basic node stored in a linked list
// Note that this class is not accessible outside
// of package weiss.nonstandard
class ListNode {
    // Constructors
    public ListNode( Object theElement ) {
        this( theElement, null );
    }
    public ListNode( Object theElement, ListNode n ) {
        element = theElement;
        next    = n;
    }
    public Object   element;
    public ListNode next;
}
// 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( );
}