New Topic/Question
Reply
public interface JFQueue
{
/**
@param s is a string to be added to the queue
@return true if new element is successfully added, false otherwise
*/
public boolean queue(String s);
/**
deletes the element in the head of first position of the queue
@ return the value of the deleted element
*/
public String deQueue();
}
import java.util.*;
/*
public interface JFQueue
{
//@param s is a string to be added to the queue
//@return true if new element is successfully added, false otherwise
public boolean queue(String s);
//deletes the element in the head of first position of the queue
//@ return the value of the deleted element
public String deQueue();
}
*/
public class ArrayQueue implements JFQueue
{
public static void main (String[] args)
{
int maxSize = 8;
ArrayQueue myQueue = new ArrayQueue (maxSize);
myQueue.getSize();
}
private int maxSize; //maximum queue size
int head; //Location of the head or first element
int tail; //Location of the last element
int size; //number of elements in the queue
String[] data; //Array to hold the data
/** Constructor
@param maxSize sets up the maximum queue size
*/
public ArrayQueue(int maxSize)
{
this.maxSize = maxSize;
head= 0;
tail= maxSize - 1;
size = 0;
data = new String[maxSize];
}
// Add an element to the end of the queue
public boolean queue(String s)
{
if(size==0)
{
size++;
head= 0;
tail= (tail + 1) % size;
return true;
}
if(size == maxSize)
{
expand();
}
size ++;
int n = (tail+1) % maxSize;
data[n]= s;
tail=n;
return true;
}
// Remove the element at the front of the queue
public String deQueue()
{
String temp = data[head];
if(temp==null) //Queue is empty!!
{
return null;
}
head = (head + 1) % maxSize;
size --;
if (size <= (0.1 * maxSize))
{
compact();
}
return temp;
}
// Return the size of the queue
public int getSize()
{
return size;
}
// The traverse method verify that we correctly implemented the queue
public void traverse()
{
for(int i= 0; i< size; i++)
{
System.out.println ("Array Location " +(head + i)% maxSize +" Value "+
data[(head + i)% maxSize]);
}
}
// Expand the array to double its current size if the queue is full and reallocate the array
private void expand()
{
int newSize = 2 * size;
String [] newData = new String [newSize];
int j = head;
for (int i = 0; i < size; i ++)
{
newData[i] = data[i];
j = (j + 1) % maxSize;
}
head = 0;
tail = size - 1;
size = newSize;
data = newData;
}
// Reduce the size of the array to half if it is only 10% full and reallocate the array
private void compact()
{
double newSize = 0.5 * size;
String [] newData = new String [newSize];
int j = head;
for (int i = 0; i < size; i ++)
{
newData[i] = data[i];
j = (j+1) % maxSize;
}
head = 0;
tail = size - 1;
size = newSize;
data = newData;
}
}
This post has been edited by HardToHandle: 20 September 2012 - 03:54 PM
MultiQuote
| 