Subject: Sorted Queue using array of ListNodes [Question] · Posted: 2004-12-06, 01:30am
Rank: ? (1)
Member #: 22787
So I need to make this queue. The enqueue method finds the right place to add the node and the dequeue method just takes the node off of the front. I'm having problems setting it up, though. This is my code at the moment:
Code:
public class RPQueue implements RPQueueInterface
{
private Memory queue; // Array that holds queue elements
private int capacity; // size of the array (capacity of the queue)
private int numItems = 0; // number of items on the queue
private int front = 0; // location of the front of the queue
final byte DECREASING = 0; // used to determine current order of queue
final byte INCREASING = 1; // used to determine current order of queue
/**
* ListNode creates variables for use in storing information in nodes.
*
* @author Dale, Joyce, Weems & Christopher Yount
* @version 11/9/04
*/
protected class ListNode
// Used to hold references to list nodes for the linked list implementation
{
protected Comparable info; // used to store the info in a list node
protected int next; // used as a reference to the next node in the array
}
/**
* Creates an array data structure of ListNodes.
*
* @author Christopher Yount
* @version 11/22/04
*/
protected class Memory
{
ListNode array[];
protected ListNode list; // reference to first node in list
protected ListNode free; // reference to first node in free list
protected int currentPos = 0; // Current position for iteration
// Constructors
public Memory()
{
array = new ListNode[100];
capacity = 100;
for (int i = 0; i < capacity - 2; i++)
{
array[i] = null;
array[i].next = i + 1;
}
array[capacity - 1] = null;
array[capacity - 1].next = -1;
list = null;
free = array[0];
}
public Memory(int maxSize)
{
array = new ListNode[maxSize];
capacity = maxSize;
for (int i = 0; i < capacity - 2; i++)
{
array[i] = null;
array[i].next = i + 1;
}
array[capacity - 1] = null;
array[capacity - 1].next = -1;
list = null;
free = array[0];
}
/**
* This method returns the address of the next linked-list node or -1 if the array
* is full
*
* @return an int holding the value of the next linked-list node or -1
*/
public int allocate()
// Effect: Returns the address of the next linked-list node
// or -1 if there is no space left.
// Postconditions: if (isFull), -1 is returned, otherwise, return the address
// of the next linked-list node
{
int allocated = 0;
if (numItems != 0)
{
if (currentPos == capacity - 1)
allocated = -1;
else if (numItems > 1)
allocated = array[currentPos].next;
}
return allocated;
}
/**
* This method reinserts the node with address "cell" back into the free list or
* raises an assert exception if "cell" is outside the proper range.
*
* @param y an int referencing an address
*/
public void deallocate (int cell)
{
assert (cell > capacity - 1):
"Cell is outside of the proper range.";
array[cell].next = free.next;
free = array[cell];
}
}
// Constructors
public RPQueue()
{
queue = new Memory();
}
public RPQueue(int maxSize)
{
queue = new Memory(maxSize);
}
/**
* This method determines whether or not the queue is empty.
*
* @return a boolean value containing the result of isEmpty == true
*/
public boolean isEmpty()
// Effect: Determines whether this priority queue is empty.
// Postcondition: Return value = (this priority queue is empty)
{
boolean emptyQueue = false;
if (numItems == 0)
{
emptyQueue = true;
}
return emptyQueue;
}
/**
* This method determines whether or not the queue is full.
*
* @return a boolean value containing the result of isFull == true
*/
public boolean isFull()
// Effect: Determines whether this priority queue is full.
// Postcondition: Return value = (priority queue is full)
{
boolean fullQueue = false;
if (queue.allocate() == -1)
fullQueue = true;
return fullQueue;
}
/**
* This method adds an item onto the queue, in its sorted place.
*
* @param y an object of type Comparable
*/
public void enqueue(Comparable item)
// Effect: Adds item to this priority queue.
// Postcondition: If (this priority queue is full)
// an unchecked exception that communicates ‘enqueue
// on priority queue full’ is thrown
// Else
// item is in this priority queue.
{
assert (!isFull()):
"Queue is full. Please dequeue before attempting to enqueue.";
ListNode newNode = new ListNode(); // reference to node being inserted
ListNode prevLoc = new ListNode(); // trailing reference
ListNode location = new ListNode(); // traveling reference
int spaceHolder = 0;
boolean moreToSearch;
location = queue.list;
prevLoc = null;
moreToSearch = (location != null);
// Find insertion point.
while (moreToSearch)
{
if (item.compareTo(location.info) > 0) // list element is larger than item
moreToSearch = false;
else
{
prevLoc = location;
queue.currentPos = location.next;
location = queue.array[queue.currentPos];
moreToSearch = (location.info != null);
}
}
// Prepare node for insertion.
newNode.info = item;
// Insert node into list.
if (prevLoc == null) // Insert as first
{
newNode.next = queue.currentPos;
queue.list = newNode;
}
else
{
newNode.next = prevLoc.next;
queue.array[prevLoc.next] = newNode;
}
numItems++;
}
/**
* This method removes an element from front of the queue and returns a reference
* to it.
*
* @return a reference to the removed element
*/
public Comparable dequeue()
// Effect: Removes element with highest priority from this
// priority queue and returns a reference to it
// Postconditions: If (this priority queue is empty)
// an error message is produced
// Else
// Highest priority element has been removed.
// Return value = (reference to the removed element)
{
Comparable reference;
int newFront;
assert (numItems != 0):
"You cannot dequeue from an empty queue.";
reference = queue.array[front].info;
newFront = queue.array[front].next;
queue.deallocate(front);
front = newFront;
numItems--;
return reference;
}
/**
* This method reverses the order of the list, resulting in a list sorted in an
* increasing or decreasing manner.
*
*/
public void Reverse()
// Effect: Reverses the order of the sorted list
// Postconditions: The list is now sorted in either ascending or descending order
{
byte order = 0;
if (queue.array[0].info.compareTo(queue.array[queue.array[0].next].info) > 0)
I'm getting null pointer exceptions where I define the Memory arrays. What am I doing wrong? Also, I need to be able to reverse the order of the queue. I feel like I should be able to do this recursively. Am I correct? How would I go about doing this? Thank you.
