Link-List Based Queue
Machine Problem #1

William Kallander
CSSAP443
05 April 2001

Purpose:

The purpose of this program is to review the Queue and Linked-List data structures, as well as Input/Output in Java.  In addition, a mechanism for custom memory management in java is introduced that avoids the dreaded garbage collection performance problem.

Class Descriptions:

ListNode:

This is a fixed-length consecutive memory location to house the data needed in the nodes of a LinkedList.

• getID() / setID() - Obtain and Store the key to the associated data stored in the Node.
• getPrevious() / setPrevious() - Obtain and Store the SystemMemory address of the previous node in the list.
• getNext() / setNext() - Obtain and Store the SystemMemory address of the next node in the list.
• getDataSize() / setDataSize() - Obtain and Store the number of data elements embedded in the node.
• getData() / setData() - Obtain and Store data elements in the node by offsets into the array of elements.

SystemMemory:

A class to emulate system memory (similar to computer RAM).  An internal static array is used to simulate a global pool of memory, and another field of this class maintains the chunk size for the memory as specified by the user.

• isValid() - Ensure that a pointer to a memory location is within the bounds of the SystemMemory internal array.

MemoryManager:

Manages memory by free-ing or allocating memory.

• malloc() - Allocate a pre-defined chunk of SystemMemory to the caller.
• free() - Accept a chunk of SystemMemory back after a caller releases it, and store it for possible future use by other callers.
• printFreeMemory() - Print out the available (unused) SystemMemory locations.

DoubleLinkList:

A Doubly-LinkedList data structure implementation using custom memory management.  This allows traversal in both directions (via next and previous fields in the ListNode class).  This class depends heavily on the ListNode class.

• insertLast() - Insert a node onto the end of the LinkedList.
• removeFirst() - Remove a node off the front of the LinkedList.
• remove() - Remove a node based on a key for the data.
• isEmpty() - Determine if the list has contains any nodes.
• print() - Traverse the entire list and print out the values.

IQueue:

This is an interface for our queue.  This abstraction allows the substitution of another queue painlessly.  Since this is an interface, it only contains method definitions.

The following are therefore described in the interface implementation class LookupQueue.

• public void enqueue( int element );
• public int dequeue();
• public int dequeue( int id );
• public void print();

LookupQueue:

This is an implementation for the IQueue interface.  It defines the exact behaviour of the IQueue methods.  As an example, this class implementation defines the behaviour of the IQueue to be First-In-First-Out , and dependant upon the custom memory model as described above.  In particular, the LookupQueue simply translates methods calls into their appropriate DoubleLinkList counterpart and executes these method calls against an internally stored DoubleLinkList.

• enqueue() - Add a new element to the end of the queue.
• dequeue() - Remove an element from the front of the queue.
• dequeue( int id ) - Remove an element based on a matching key from the queue.  This action is independent of the position in which this element is stored.
• print() - Print all elements in the queue to standard output.

Tmp1:

This class provides the command-line user interface and drives the program based on user inputs.

• main() - Drives the program and allows the following user interactions:
  • Set the SystemMemory size.
  • Set the SystemMemory block size.
  • Enqueue an arbitrary number of data records.
  • Dequeue an arbitrary number of data records.
  • Remove an element from the queue based on it's numeric id.
  • Print the contents of the queue to standard output.
  • Print the free (unused) memory in the system.
  • Quit the program

Pseudocode:

Queue Implementation:

1. public LookupQueue();  // Constructor

   Pseudocode:
   LookupQueue()
      // create a new DoubleLinkList and store a
       // reference to it internally in this class
       m_list <-- new DoubleLinkList()
   

    

2. public void enqueue( int element );

   Pseudocode:
   enqueue( element )
       // Pass the parameter to the insertLast() method
       // of the DoubleLinkList class
       call DoubleLinkList's insertLast( element )
       // This places the element at the end of the
       // linked-list data structure
   

3. public int dequeue();

   Pseudocode:
   dequeue()
       // Invoke the removeFirst() method of the
       // DoubleLinkList class.
       // This removes the element at the front position
       // of the linked list data structure
       pointer <-- call DoubleLinkList's removeFirst()
       // Return it's memory address
       return pointer
   

4. public int dequeue( int id );

   Pseudocode:
   dequeue( id )
       // Invoke the remove() method of the DoubleLinkList class.
       // This removes the element with the specified key from
       // any position of the linked list data structure
       pointer <-- call DoubleLinkList's remove( id )
       // Return it's memory address
       return pointer
   

    

5. public void print();

   Pseudocode:
   print()
       // Invoke the print() method of the DoubleLinkList class.
       // This traverses the entire linked list data structure
       // and prints the data element found to standard output.
       pointer <-- call DoubleLinkList's print()
       // Return it's memory address
       return pointer