/**

* A class to test the ListQueue.java program

* @author T. Andrew Yang

*

* Sample output:

Before dequeue()----------

qu.getFront(): 10

qu.dequeue(): 10

After dequeue()----------

qu.getFront(): Southern oaks

**/

import weiss.nonstandard.ListQueue;

public class ListQueueTest {

public static void main (String args[]){

ListQueue qu = new ListQueue();

qu.enqueue(10);

qu.enqueue("Southern oaks");

qu.enqueue("Eastern redbud");

qu.enqueue(20);

qu.enqueue("Knockout roses");

System.out.println("Before dequeue()----------");

System.out.println("qu.getFront(): " + qu.getFront());

System.out.println("qu.dequeue(): " + qu.dequeue());

System.out.println("After dequeue()----------");

System.out.println("qu.getFront(): " + qu.getFront());

} // main

}

//------------ Classes below are from the Weiss book: Data Structures & Problem Solving using Java.

package weiss.nonstandard;

// Basic node stored in a linked list

// Note that this class is not accessible outside

// of package weiss.nonstandard

class ListNode<AnyType>

{

// Constructors

public ListNode( AnyType theElement )

{

this( theElement, null );

}

public ListNode( AnyType theElement, ListNode<AnyType> n )

{

element = theElement;

next = n;

}

public AnyType element;

public ListNode<AnyType> next;

}

//------------

package weiss.nonstandard;

/**

* 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 );

}

}

//------------

package weiss.nonstandard;

// Queue interface

//

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

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

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

// AnyType 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<AnyType>

{

/**

* Insert a new item into the queue.

* @param x the item to insert.

*/

void enqueue( AnyType 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.

*/

AnyType 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.

*/

AnyType dequeue( );

/**

* Test if the queue is logically empty.

* @return true if empty, false otherwise.

*/

boolean isEmpty( );

/**

* Make the queue logically empty.

*/

void makeEmpty( );

}

//------------

package weiss.nonstandard;

// ListQueue class

//

// CONSTRUCTION: with no initializer

//

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

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

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

// AnyType 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<AnyType> implements Queue<AnyType>

{

/**

* 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( AnyType x )

{

if( isEmpty( ) ) // Make queue of one element

back = front = new ListNode<AnyType>( x );

else // Regular case

back = back.next = new ListNode<AnyType>( 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 AnyType dequeue( )

{

if( isEmpty( ) )

throw new UnderflowException( "ListQueue dequeue" );

AnyType 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 AnyType 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<AnyType> front;

private ListNode<AnyType> back;

}

//------------