/*File List02.java
Copyright 1997, R.G.Baldwin
This program develops a general-purpose linked-list that
supports the addition and removal of new nodes at either
the front or the back.
This general-purpose linked-list is then subclassed to
provide two more-specialized data structures:
Queue
Stack
In all cases, the data structures so produced operate
with objects of the generic type Object.
The output from running this program is shown below:
//------------------------------------------
Test the unordered list
Put some data objects in the unordered list
The unordered list contains:
One
Two
Three
Four
Remove data objects from the unordered list
Removed One
Removed Four
Removed Two
The unordered list now contains:
Three
Removed Three
The unordered list now contains:
Empty
Remove another object from the unordered list
Exception: Empty list in fetchFromFront
Test the queue
Put some data objects in the queue
The queue contains:
One
Two
Three
Four
Try to remove 5 data objects from the queue
Dequeued One
Dequeued Two
Dequeued Three
Dequeued Four
Exception: Empty list in fetchFromFront
Test the stack
Push some data objects on the Stack
The stack contains:
Four
Three
Two
One
Try to pop 5 data objects from the Stack
popped Four
popped Three
popped Two
popped One
Exception: Empty list in fetchFromFront
End of test
//------------------------------------------
This program was tested using JDK 1.1.3 under Win95.
**********************************************************/
import java.awt.*;
import java.awt.event.*;
import java.util.*;
//=======================================================//
class TestClass{
//This class is used to test the data structures.
//An object of this class contains a single instance
// variable which is an object of type String.
String data;
//-----------------------------------------------------//
TestClass(String data){//constructor
this.data = data;
}//end constructor
//-----------------------------------------------------//
public String toString(){//overridden toString() method
return (data);
}//end toString()
//-----------------------------------------------------//
}//end TestClass
//=======================================================//
/*This class is the controlling class which is used to test
the data structures developed in this lesson. This
class contains a method named test() which designed to
exercise the capabilities of the unordered linked-list,
stack, queue, and ordered list.
---------------------------------------------------------*/
class List02{//controlling class
public static void main(String[] args){//main
List02 obj = new List02();//instantiate this object
obj.test();//invoke the method named test()
}//end main
//-----------------------------------------------------//
void test(){
System.out.println("Test the unordered list");
RawList theList = new RawList();//instantiate list obj
System.out.println(
"Put some data objects in the unordered list");
theList.toFront(new TestClass("Two"));
theList.toBack(new TestClass("Three"));
theList.toFront(new TestClass("One"));
theList.toBack(new TestClass("Four"));
System.out.println("The unordered list contains:");
theList.printRawList();
System.out.println(
"\nRemove data objects from the unordered list");
try{//because an exception of type Excep can be thrown
System.out.println("Removed "
+ theList.fetchFromFront());
System.out.println("Removed "
+ theList.fetchFromBack());
System.out.println("Removed "
+ theList.fetchFromFront());
System.out.println(
"The unordered list now contains:");
theList.printRawList();
System.out.println("Removed "
+ theList.fetchFromBack());
System.out.println(
"The unordered list now contains:");
theList.printRawList();
System.out.println(
"Remove another object from the unordered list");
System.out.println("Removed "
+ theList.fetchFromFront());
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("\nTest the queue");
//instantiate a MyQueue object
MyQueue theQueue = new MyQueue();
System.out.println(
"Put some data objects in the queue");
theQueue.enqueue(new TestClass("One"));
theQueue.enqueue(new TestClass("Two"));
theQueue.enqueue(new TestClass("Three"));
theQueue.enqueue(new TestClass("Four"));
System.out.println("The queue contains:");
theQueue.printQueue();
System.out.println(
"\nTry to remove 5 data objects from the queue");
try{
for(int cnt = 0; cnt < 5; cnt++)
System.out.println("Dequeued "
+ theQueue.dequeue());
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("\nTest the stack");
//instantiate a MyStack object
MyStack theStack = new MyStack();
System.out.println(
"Push some data objects on the Stack");
theStack.push(new TestClass("One"));
theStack.push(new TestClass("Two"));
theStack.push(new TestClass("Three"));
theStack.push(new TestClass("Four"));
System.out.println("The stack contains:");
theStack.printStack();
System.out.println(
"\nTry to pop 5 data objects from the Stack");
try{
for(int cnt = 0; cnt < 5; cnt++)
System.out.println("popped " + theStack.pop());
}catch(Excep e){System.out.println("Exception: " + e);}
System.out.println("End of test");
}//end test()
}//end controlling class named class02
//=======================================================//
//=======================================================//
//This is the beginning of the classes that are used to
// instantiate several different kinds of data structures.
//=======================================================//
//=======================================================//
//This is a new exception class that is used to instantiate
// exception objects for a variety of different exceptional
// conditions within the data structure methods.
class Excep extends Exception{
private String diagnosticData;//put diagnostic data here
Excep(){//NoArg constructor
diagnosticData = "No diagnostic data provided";
}//end NoArg constructor
Excep(String diagnosticData){//parameterized constructor
this.diagnosticData = diagnosticData;
}//end NoArg constructor
public String toString(){//override toString()
return diagnosticData;
}//end overridden toString()
}//end class Excep
//=======================================================//
//This class is used to instantiate a node in the data
// structure. It contains an embedded object of whatever
// type is passed in as a parameter. The test class
// provide with this program uses objects of the class
// namedTestClass.
class Node{
Object dataObj; //data object is stored here
Node nextNode;//reference to the next node in the RawList
//-----------------------------------------------------//
public Node(Object dataObj){//constructor
this.dataObj = dataObj;//store incoming dataObj
}//end constructor
}//end class Node
//=======================================================//
//Begin definition of the class used to create
//and maintain a raw list
class RawList{
private Node firstNode; //reference to first node
private Node lastNode; //reference to last node
//-----------------------------------------------------//
//Function to allocate memory and return a reference
// variable for a new node.
private Node getNode( Object dataObj) {
//get reference variable to new memory
Node newNode = new Node(dataObj);
return newNode;
}//end getNode()
//-----------------------------------------------------//
//Method to determine if The structure is empty
boolean isEmpty(){
return firstNode == null;//return true if empty
}//end isEmpty()
//-----------------------------------------------------//
//Attach a new node to the front of the RawList
void toFront(Object dataObj){
//Encapsulate the incoming object in an object of type
// node and assign it to a local reference variable.
Node newNode = this.getNode(dataObj);
//Now attach the new node to the front of the list
if(this.isEmpty()) //RawList is empty
firstNode = lastNode = newNode;
else{ //RawList is not empty
newNode.nextNode = firstNode;
firstNode = newNode;
}//end if
}//end toFront()
//-----------------------------------------------------//
//Attach a new node to the back of the RawList
void toBack(Object dataObj){
//Encapsulate the incoming object in an object of type
// node and assign it to a local reference variable.
Node newNode = this.getNode(dataObj);
//Now attach the new node to the back of the list
if(this.isEmpty()) //RawList is empty
firstNode = lastNode = newNode;
else { //RawList is not empty
lastNode.nextNode = newNode;
lastNode = newNode;
}//end if
}//end toBack()
//-----------------------------------------------------//
//This method is used to fetch and delete a node from
// the front of the RawList. Note that all objects are
// treated as objects of the generic type Object.
Object fetchFromFront() throws Excep{
if(this.isEmpty()) //RawList is empty
throw new Excep("Empty list in fetchFromFront");
else { //RawList is not empty
//declare and initialize a local reference variable
Node tempRefToNode = firstNode;
if(firstNode == lastNode)//only one node in the list
firstNode = lastNode = null; //set both to null
else//more than one node in the list
//Wire around the first node and return it
firstNode = firstNode.nextNode;
return tempRefToNode.dataObj; //fetch successful
}//end else
}//end fetchFromFront()
//-----------------------------------------------------//
//This method is used to fetch and delete a node from the
// back of the RawList
Object fetchFromBack() throws Excep{
if(this.isEmpty()) //RawList is empty
throw new Excep("Empty list in fetchFromBack");
else { //RawList is not empty
//declare and initialize a local reference variable
Node tempRefToNode = lastNode;
if(firstNode == lastNode)//only one node in the list
firstNode = lastNode = null; //set both to null
else {//more than one node in the list
//Declare and initialize another local
// reference variable
Node currentRefToNode = firstNode;
//The list is a one-way street. The last node can
// only be removed by starting at the front and
// walking to the end touching each node along the
// way. Use a while loop to traverse the list,
// stopping at the node immediately before the
// last one.
while(currentRefToNode.nextNode != lastNode)
currentRefToNode = currentRefToNode.nextNode;
//Cut the last node loose and set the reference
// to the next node in the new last node to null
// to indicate the new end of the list.
lastNode = currentRefToNode;
currentRefToNode.nextNode = null;
}//end else
//Return the data object from the saved last node.
return tempRefToNode.dataObj; //fetch successful
}//end else
}//end fetchFromBack()
//-----------------------------------------------------//
//This method is used to display the contents of the
// RawList object.
void printRawList(){
if(this.isEmpty()){
System.out.println("Empty");
return;
}//end if
//Not empty. Declare and initialize a local
// reference variable to the first node in the list
Node currentRefToNode = firstNode;
//Use a while loop to traverse the list displaying
// the data object in each node along the way.
while(currentRefToNode != null){
System.out.println("" + currentRefToNode.dataObj);
currentRefToNode = currentRefToNode.nextNode;
}//end while
}//end printRawList()
}//end class RawList
//=======================================================//
//The above class was used to provide the raw list which
// serves as a superclass for the following specialized
// subclasses.
//=======================================================//
//This class subclasses the class named RawList in such
// a way as to provide queue behavior. A queue is a
// first-in/first-out structure. This can be accomplished
// by entering data into the back of a RawList object and
// removing it from the front of the object.
//As you can see, this is a very simple class. It simply
// invokes the methods of the RawList class on a selective
// basis.
class MyQueue extends RawList{
public void enqueue(Object obj){
this.toBack(obj);//enqueue data to the back of the list
}//end enqueue()
public Object dequeue() throws Excep{
//dequeue data from the front of the list
return this.fetchFromFront();
}//end dequeue()
public void printQueue(){
this.printRawList();//use the existing print capability
}//end printQueue()
public boolean isQueueEmpty(){
return this.isEmpty();//use the existing empty test
}//end isQueueEmpty
}//end class MyQueue
//=======================================================//
//This class is used to subclass the RawList class in
// such a way as to provide stack behavior. A stack is a
// last-in/first-out structure. This can be accomplished
// by attaching data to the front of the list and
// removing it from the front of the list.
class MyStack extends RawList{
public void push(Object obj){
this.toFront(obj);//attach new data to front of list
}//end push
public Object pop() throws Excep{
//remove new data from the front of the list
return this.fetchFromFront();
}//end pop()
public void printStack(){
this.printRawList();//use existing print capability
}//end printStack()
public boolean isStackEmpty(){
return this.isEmpty();//use the existing empty test
}//end isStackEmpty
}//end class MyStack
//=======================================================// |
גולשים מקוונים: 4