//class to represent one node in a list class ListNode { //package access members; List can access these directly T data; ListNode nextNode; //constructor creates a ListNode that refers to object ListNode( T object ) { this( object, null ); } // end ListNode one-argument constructor //constructor creates ListNode that refers to //Object and to next ListNode ListNode( T object, ListNode node ) { data = object; nextNode = node; } // end ListNode two-argument constructor //return reference to data in node T getObject() { return data; // return Object in this node } // end method getObject //return reference to next node in list ListNode getNext() { return nextNode; // get next node } // end method getNext } // end class ListNode //class List definition public class List { private static final String Integer = null; private ListNode firstNode; private ListNode lastNode; private String name; // string like "list" used in printing //constructor creates empty List with "list" as the name public List() { this( "list" ); } // end List no-argument constructor //constructor creates an empty List with a name public List( String listName ) { name = listName; firstNode = lastNode = null; } // end List one-argument constructor //insert Object at front of List public void insertAtFront( T insertItem ) { if ( isEmpty() ) // firstNode and lastNode refer to same object firstNode = lastNode = new ListNode( insertItem ); else // firstNode refers to new node firstNode = new ListNode( insertItem, firstNode ); } // end method insertAtFront //insert Object at end of List public void insertAtBack( T insertItem ) { if ( isEmpty() ) // firstNode and lastNode refer to same Object firstNode = lastNode = new ListNode( insertItem ); else // lastNode's nextNode refers to new node lastNode = lastNode.nextNode = new ListNode( insertItem ); } // end method insertAtBack //remove first node from List public T removeFromFront() throws RuntimeException { if ( isEmpty() ) // throw exception if List is empty throw new RuntimeException( name+" is Empty !!" ); T removedItem = firstNode.data; // retrieve data being removed //update references firstNode and lastNode if ( firstNode == lastNode ) firstNode = lastNode = null; else firstNode = firstNode.nextNode; return removedItem; // return removed node data } // end method removeFromFront //remove last node from List public T removeFromBack() throws RuntimeException { if ( isEmpty() ) // throw exception if List is empty throw new RuntimeException( name+" is Empty !!" ); T removedItem = lastNode.data; // retrieve data being removed // update references firstNode and lastNode if ( firstNode == lastNode ) firstNode = lastNode = null; else // locate new last node { ListNode current = firstNode; //loop while current node does not refer to lastNode while ( current.nextNode != lastNode ) current = current.nextNode; lastNode = current; // current is new lastNode current.nextNode = null; } // end else return removedItem; // return removed node data } // end method removeFromBack //determine whether list is empty public boolean isEmpty() { return firstNode == null; // return true if List is empty } // end method isEmpty //output List contents public void print() { if ( isEmpty() ) { System.out.printf( "Empty %s ", name ); return; } // end if System.out.printf( "The %s is: ", name ); ListNode current = firstNode; //while not at end of list, output current node's data while ( current != null ) { System.out.printf( "%s ", current.data ); current = current.nextNode; } // end while System.out.println( " " ); } // end method print } // end class List
//=============
//class to represent Stack public class Stack { List stackList; // constructor Stack() { this("My Stack"); } // constructor Stack(String name) { stackList=new List(name); } public void push( T item ) { stackList.insertAtFront( item ); } public T pop() throws RuntimeException { return stackList.removeFromFront(); } public boolean isEmpty() { return stackList.isEmpty(); } public void print() { stackList.print(); } } // end class Stack //=============== //class to represent Queue public class Queue { List queueList; // constructor Queue() { this("My Queue"); } // constructor Queue(String name) { queueList=new List(name); } public void enqueue( T item ) { queueList.insertAtBack( item ); } public T dequeue() throws RuntimeException { return queueList.removeFromFront(); } public boolean isEmpty() { return queueList.isEmpty(); } public void print() { queueList.print(); } } // end class Queue
========
(in java program language)
Us sing only the given Queue
or Stack. Print the content of Stack/Queue before and after changes
