So I've created a DoubleQueue in Java.. It's for my Data Structures and Algorithms class and we're trying to show that DoubleQueue's can be used to implement Stacks and Queues. Here's how it works:
It uses an array to store the items with the head pointing to the front item in the array and the tail pointing to the back item of the array. The array is circular, and when capacity reaches 90% it expands. Now I think the expansion is putting up a fuss. When I add a bunch of Integers to the stack, then remove them all, they display fine, in reversed order. However, I'm trying to reverse a string by pushing String.charAt, then popping all the characters and printing them. This works fine for strings that are short enough that they require no expansion. However, once expansion is required, I start getting a weird output that involves messed up characters (not in the right order, characters missing), as well as null values.
I think it's got something to do with how I'm cast ing the array:
/**
* Expands the capacity of the storage array that holds the collection of items
* within the DoubleQueue *** only if expansion is needed ***
* @return True if the array was expanded; False otherwise
*/
@SuppressWarnings({"unchecked"})
public boolean expandArray() {
// First, see if need to expand
if( (double) size / storage.length >= CAPACITY_EXPAND ) {
// Create a temporary pointer to the storage array
E[] temp = storage;
// First out what type of expansion we're doing and create a new, larger array
if( expansionRule == EXPANSION_DOUBLE )
storage = ( E[] )new Object[ 2 * temp.length ];
else
storage = ( E[] )new Object[ temp.length + INCREASE_CONSTANT ];
int i = 0; // Counter for storage
int j = tail; // Counter for temp
// Copy temp to storage
while( j != head ) {
storage[ i ] = temp[ j ];
if( j == temp.length - 1 ) j = 0; // If we have to wrap around the array
else j++;
i++;
}
storage[ i ] = temp[ j ];
return true;
}
return false;
}
Here is the whole code:
public class DoubleQueue<E> {
/** CONSTANTS **/
private final int INCREASE_CONSTANT = 10; // The amount to increase by if expansion rule is increase by constant
private final double CAPACITY_EXPAND = 0.9; // The size:capacity ratio at which the storage should be expanded
public static final char EXPANSION_DOUBLE = 'd'; // Parameter for expansionRule()
public static final char EXPANSION_CONSTANT = 'c'; // Parameter for expansionRule()
/** VARIABLES **/
private char expansionRule; // Stores the current expansion rule
private int head; // Keeps track of the index of the first element
private int tail; // Keeps track of the index of the last element
private int size; // Keeps track of the number of items in storage
private E storage[]; // Holds the collection of items
/** CONSTRUCTORS **/
/**
* Creates an empty DoubleQueue with a given capacity. Initializes variables
* and sets the default expansion rule.
* @param capacity The initial capacity of the DoubleQueue
*/
@SuppressWarnings({ "unchecked" })
public DoubleQueue( int capacity ) {
size = 0;
head = -1;
tail = -1;
storage = ( E[] )new Object[ capacity ];
setExpansionRule( EXPANSION_DOUBLE );
}
/**
* Creates an empty DoubleQueue of initial capacity 10.
*/
public DoubleQueue() {
this( 10 );
}
/** METHODS **/
/**
* Checks to see if the DoubleQueue is currently empty
* @return True if the DoubleQueue is empty; False otherwise
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Adds an item at the beginning of the DoubleQueue
* @param item The item to be added to the DoubleQueue
* @return True if the item was successfully added
*/
public boolean addFirst( E item ) {
// First, perform expansion if neccessary
expandArray();
// Put the head and tail pointers in the right spots
if( isEmpty() ) {
head = 0;
tail = 0;
} else if( head == storage.length - 1 ) head = 0;
else head++;
// Add the item
storage[ head ] = item;
// Increment the size
size++;
return true;
}
/**
* Adds an item at the end of the DoubleQueue
* @param item The item to be added to the DoubleQueue
* @return True if the item was successfully added
*/
public boolean addLast( E item ) {
// First, perform expansion if neccessary
expandArray();
// Put the head and tail pointers in the right place
if( isEmpty() ) {
head = 0;
tail = 0;
} else if( tail == 0 ) tail = storage.length - 1;
else tail--;
// Add the item
storage[ tail ] = item;
// Increment the size
size++;
return true;
}
/**
* Expands the capacity of the storage array that holds the collection of items
* within the DoubleQueue *** only if expansion is needed ***
* @return True if the array was expanded; False otherwise
*/
@SuppressWarnings({"unchecked"})
public boolean expandArray() {
// First, see if need to expand
if( (double) size / storage.length >= CAPACITY_EXPAND ) {
// Create a temporary pointer to the storage array
E[] temp = storage;
// First out what type of expansion we're doing and create a new, larger array
if( expansionRule == EXPANSION_DOUBLE )
storage = ( E[] )new Object[ 2 * temp.length ];
else
storage = ( E[] )new Object[ temp.length + INCREASE_CONSTANT ];
int i = 0; // Counter for storage
int j = tail; // Counter for temp
// Copy temp to storage
while( j != head ) {
storage[ i ] = temp[ j ];
if( j == temp.length - 1 ) j = 0; // If we have to wrap around the array
else j++;
i++;
}
storage[ i ] = temp[ j ];
return true;
}
return false;
}
/**
* Gets the element at the front of the DoubleQueue & removes it
* @throws EmptyDoubleQueueException if the queue is empty and there is no item to remove
* @return The item at the front of the DoubleQueue
*/
public E removeFirst() throws EmptyDoubleQueueException {
// If the DoubleQueue is empty we obviously can't get an element from it..
if( size == 0 ) throw new EmptyDoubleQueueException();
// Create a temporary record of the item and remove it from storage
E temp = storage[ head ];
storage[ head ] = null;
size--; // Decrease the size of the DoubleQueue
if( size == 0 ) { // If we're taking the last element
head = -1;
tail = -1;
} else if ( head == 0 ) head = storage.length - 1; // Wrap around the array
else head--;
return temp;
}
/**
* Gets the item at the back of the DoubleQueue & removes it
* @throws EmptyDoubleQueueException if the queue is empty and there is no item to return
* @return The item at the back of the doubleQueue
*/
public E removeLast() throws EmptyDoubleQueueException {
// If the DoubleQueue is empty we obviously can't get an element from it..
if( size == 0 ) throw new EmptyDoubleQueueException();
// Create a temporary record of the item and remove it from storage
E temp = storage[ tail ];
storage[ tail ] = null;
size--; // Decrease the size of the DoubleQueue
if( size == 0 ) { // If we're taking the last element
head = -1;
tail = -1;
} else if ( tail == storage.length - 1 ) tail = 0; // Wrap around the array
else tail++;
return temp;
}
/**
* Gets the item at the front of the DoubleQueue
* @return The item at the front of the DoubleQueue; null if list is empty
*/
public E peekFirst() {
if( size == 0 ) return null; // Nothing to return
return storage[ head ];
}
/**
* Gets the item at the back of the DoubleQueue
* @return The item at the back of the DoubleQueue; null if list is empty
*/
public E peekLast() {
if( size == 0 ) return null; // Nothing to return
return storage[ tail ];
}
/**
* Trims the size of the underlying collection to the exact number of items within
* the collection
*/
@SuppressWarnings({"unchecked"})
public void truncate() {
E[] temp = storage; // Create a temporary pointer to storage
storage = ( E[] )new Object[ storage.length ]; // Create a new storage array that is the size of the # of elements in storage
int i = 0; // Pointer to iterate storage
int j = 0; // Pointer to iterate temp
// Copy values from temp to storage
while( j != head ) {
storage[ i ] = temp[ j ];
i++;
if( j == temp.length - 1 ) j = 0; // Wrap around array
else j++;
}
}
/**
* Sets the type of expansion to be used when the underlying array nears capacity
* @param rule The type of expansion to be used in the future
* @throws InvalidInputException when the input provided does not correspond to an expansion type
* @return True if the expansion rule was set successfully
*/
public boolean setExpansionRule( char rule ) {
// Check to make sure the rule provided was valid
if( rule != EXPANSION_CONSTANT && rule != EXPANSION_DOUBLE )
throw new InvalidInputException();
// Set the rule
expansionRule = rule;
return true;
}
/**
* Returns the current capacity of the array that holds the collection of
* items currently in the DoubleQueue. This method is used for testing
* purposes only and WOULD NOT BE INCLUDED in a public release of DoubleQueue.
* @return The capcity of the storage array
*/
public int getCapacity() {
return storage.length;
}
/**
* Gets the number of elements currently in the DoubleQueue
* @return The number of elements currently in the DoubleQueue
*/
public int getSize() {
return size;
}
}
and here is the driver:
public class Driver {
public static void main( String[] args ) {
// First, check the isEmpty() method
System.out.println( "Check isEmpty() method:" );
DoubleQueue<Integer> dq = new DoubleQueue<Integer>();
if( dq.isEmpty() ) System.out.println( "isEmpty() method returns true when DoubleQueue is empty." );
else System.out.println( "ERROR: isEmpty() method returns false when DoubleQueue is empty." );
// Add something and check the isEmpty() method again
dq.addFirst( 1 );
if( dq.isEmpty() ) System.out.println( "ERROR: isEmpty() method returns true when DoubleQueue is not empty." );
else System.out.println( "isEmpty() method returns false when DoubleQueue is not empty." );
System.out.println();
// Test expansion using default expansion ( double )
System.out.println( "Check expansion by doubling (should double in capacity when the 10th element is added and again when the 19th element is added):" );
dq = new DoubleQueue<Integer>();
System.out.println( "Capacity before adding elements: " + dq.getCapacity() );
for( int i = 1; i <= 20; i++ ) {
dq.addFirst( i );
System.out.println( "Added element #" + i + ". Capacity: " + dq.getCapacity() + "." );
}
// Test expansion using constant expansion
System.out.println();
System.out.println( "Check expansion by constant (should add ten to capacity when the 10th and 19th elements are added)." );
dq = new DoubleQueue<Integer>();
dq.setExpansionRule( DoubleQueue.EXPANSION_CONSTANT );
System.out.println( "Capacity before adding elements: " + dq.getCapacity() );
for( int i = 1; i <= 20; i++ ) {
dq.addFirst( i );
System.out.println( "Added element #" + i + ". Capacity: " + dq.getCapacity() + ". " );
}
// Test functionality as a STACK
DoubleQueue<Character> stack = new DoubleQueue<Character>();
String toBeReversed = "reht olleh";
System.out.println();
System.out.println( "String to be reversed: " + toBeReversed );
// Add string to be reversed letter by letter into strck
for( int i = 0; i < toBeReversed.length(); i++ ) {
char j = toBeReversed.charAt( i );
stack.addLast( j );
System.out.println( "Added letter " + j );
}
System.out.println( stack.getCapacity() );
System.out.println( stack.getSize() );
// Print stack
while( !stack.isEmpty() ) {
try {
System.out.print( stack.removeLast() );
} catch( EmptyDoubleQueueException e ) {
}
}
/**
// This first bit tests the DoubleQueue as a stack, to reverse a strign
DoubleQueue<Character> dq1 = new DoubleQueue<Character>();
String toBeReversed = "hello";
for( int i = 0; i < toBeReversed.length(); i++ ) {
dq1.addLast( toBeReversed.charAt( i ) );
}
while( !dq1.isEmpty() ) {
try {
System.out.print( dq1.removeFirst() );
} catch( EmptyDoubleQueueException e ) {
// Do nothing
}
}**/
}
}
hlo thernullnull?