Implementing a Linked List into a Queue class?
I've written a Queue class for an assignment and a Linked List for a seperate assignment. However, now the teacher wants us to implement the LinkedList class into our Queue class. I don't understand what he means by that? Why would you need linked lists if the queue is an array which already has everything in order?
This is my queue class:
Code :
public class Queue{
private int maxQueueSize;
private int count;
private int queueFront;
private int queueRear;
//array of references to the objects that store queue elements
private DataElement[] list;
public Queue(){
maxQueueSize = 100;
}
public Queue(int queueSize){
maxQueueSize = queueSize;
}
public void intializeQueue(){
for(int i = queueFront; i <= queueRear;
i = (i + 1) % maxQueueSize)
list[i] = null;
queueFront = 0;
queueRear = maxQueueSize - 1;
count = 0;
}
public boolean isEmptyQueue(){
return (count == 0);
}
public boolean isFullQueue(){
return count == maxQueueSize;
}
public DataElement front(){
if(isEmptyQueue())
return null;
DataElement temp = list[queueFront].getCopy();
return temp;
}
public DataElement back(){
if(isEmptyQueue())
return null;
DataElement temp = list[queueRear].getCopy();
return temp;
}
public boolean addQueue(DataElement queueElement){
if(isFullQueue())
return false;
queueRear = (queueRear + 1) % maxQueueSize;
//use the mod
//operator to advance queueRear
//because the array is circular
count++;
list[queueRear] = queueElement.getCopy();
return true;
}
public boolean deleteQueue(){
if(isEmptyQueue())
return false;
count--;
list[queueFront] = null;
queueFront = (queueFront + 1) % maxQueueSize;
//use the mod
//operator to advance queueFront
//because the array is circular
return true;
}
}
And here is my Linked List class:
Code :
public abstract class LinkedList{
protected class LinkedListNode{ // inner class node definition
protected DataElement info;
protected LinkedListNode link;
}
protected LinkedListNode first; //variable to store the address of the first node of the list
protected LinkedListNode last; // variable to store the address of the last node of the list
protected int count; //variable to store the number of nodes in the list
//default constructor
//initializes the list to an empty state.
//postcondition: first = null, last = null, count = 0
public LinkedList(){
first = null; //
last = null; //empty list
count = 0; //
}
public LinkedList(LinkedList list)
{
copy(list);
}
private void copy(LinkedList list)
{
LinkedListNode pointer;
LinkedListNode newNode;
if(list.first == null)
{
first = null;
last = null;
count = 0;
}
else
{
count = list.count;
pointer = list.first;
first = new LinkedListNode();
first.info = pointer.info.getCopy();
first.link = null;
last = first;
pointer = pointer.link;
while(pointer != null)
{
newNode = new LinkedListNode();
newNode.info = pointer.info.getCopy();
newNode.link = null;
last.link = newNode;
last = newNode;
pointer = pointer.link;
}
}
}
//method to determine whether the list is empty
//postcondition: returns true if the list is empty; false otherwise
public boolean isEmptyList(){
return (count == 0);
}
//method to initialize the list to an empty state
//postcondition: first = null, last = null, count = 0
public void initializeList(){
first = null;
last = null;
count = 0;
}
//method to output the data contained in each node
public void print(){
if(count == 0){
System.out.println("Cannot print an empty list.");
}
else{
LinkedListNode pointer = new LinkedListNode();
pointer = first;
while(pointer != null){
System.out.println(pointer.info.toString());
pointer=pointer.link;
}
}
}
//method to return the number of nodes in the list.
//postcondition: the value of count is returned
public int length(){
return count;
}
//method to return a reference of the object
//containing the data of the first node of the list
//precondition: the list must exist and must not be empty.
//postcondition: the reference of the object that contains
//the info of the first node is returned
public DataElement front(){
return first.info.getCopy();
}
//Method to return a reference of object containing
//the data of the last node of the list.
//Precondition: The list must exist and must not be empty.
//Postcondition: The reference of the object that
//contains the info of the last node
//is returned.
public DataElement back(){
return last.info.getCopy();
}
//Method to insert newItem in the list.
//Postcondition: first points to the new list
// and newItem is inserted at the
// beginning of the list. Also,
// last points to the last node and
// count is incremented by 1.
public void insertFirst(DataElement newItem){
LinkedListNode newNode = new LinkedListNode();
newNode.info = newItem.getCopy();
newNode.link = first;
first = newNode;
if(last == null){
last = newNode;
count++;
}
}
//Method to insert newItem at the end of the list.
//Postcondition: first points to the new list and
//newItem is inserted at the end
//of the list. Also, last points to
//the last node and
//count is incremented by 1.
public void insertLast(DataElement newItem){
LinkedListNode newNode = new LinkedListNode();
newNode.info = newItem.getCopy();
newNode.link = null;
if(first == null){
first = newNode;
last = newNode;
}
else{
last.link = newNode;
last = newNode;
count++;
}
}
public void deleteFront()
{
if(first.link != null)
{
first = first.link;
count--;
}
else
{
first = null;
last = null;
count = 0;
}
}
public void deleteLast()
{
LinkedListNode pointer = first;
if(pointer.link == null)
{
first = null;
last = null;
count = 0;
}
else
{
while(pointer.link.link != null) pointer = pointer.link;
pointer.link = null;
last = pointer;
count--;
}
}
public void splitMid(LinkedList list)
{
int stopPoint = list.count / 2;
LinkedListNode pointer = null;
pointer = list.first.link;
for(int i = 0; i < stopPoint; i++)
{
pointer = pointer.link;
}
LinkedListNode secondFirst = pointer.link;
pointer.link.link = null;
}
public double average(){
double sum=0;
LinkedListNode pointer = new LinkedListNode();
pointer = first;
while(first != null){
pointer = first;
IntElement temp = (IntElement)pointer.info.getCopy();
sum = sum + temp.getNum();
first = pointer.link;
}
double average = (sum/59.0);
return average;
}
public double stdDev(double avg){
double stdAvg = avg;
double variance = 0;
LinkedListNode pointer = new LinkedListNode();
while(first!= null){
pointer = first;
IntElement temp = (IntElement)pointer.info.getCopy();
variance = (variance + ((temp.getNum() - stdAvg)*(temp.getNum() - stdAvg)));
first = pointer.link;
}
return (Math.sqrt(variance/59));
}
//Method to determine whether searchItem is in the list.
//Postcondition: Returns true if searchItem is found
//in the list; false otherwise.
public abstract boolean search(DataElement searchItem);
//Method to delete deleteItem from the list.
//Postcondition: If found, the node containing
//deleteItem is deleted from the
//list. Also first points to the first
//node, last points to the last
//node of the updated list, and count
//is decremented by 1.
public abstract void deleteNode(DataElement deleteItem);
}
I was checking out a few sites for examples such as
Simple Queue (FIFO) based on LinkedList : QueueCollections Data StructureJava
Create a queue using LinkedList class : QueueCollections Data StructureJava
But I don't really understand what they're doing different besides using polymorphism. Any explanation is appreciated.
If it helps with context, this is what we have to do.
Code :
1. Implement a Linked Queue of type DataElement as described in the lecture.
You may use either the custom Queue Class approach the Queue Interface as
described in the lecture.
2. Implement a Linked Queue using your existing Linked-List Class.
3. An Application Challenge:
Write a program to encode and decode a message using
a repeating key set.
Implement your solution using the Queue Class you developed.
Test Case:
Message: "All programmers are playwrights and all
computers are lousy actors.“
Key Set: {5, 12, -3, 8, -9, 4, 10}
--- Update ---
And another problem I'm having is a NullPointerException when using the addQueue method.
Code :
public class TestQueueClass{
public static void main(String[] args){
Queue q = new Queue();
DataElement data = new IntElement(5);
q.addQueue(data);
}
}
Code :
--------------------Configuration: <Default>--------------------
QueueRear: 0 DataElement: 5
Queue Copy: 5
Exception in thread "main" java.lang.NullPointerException
at Queue.addQueue(Queue.java:83)
at TestQueueClass.main(TestQueueClass.java:7)
Process completed.
It points to the line in the addQueue method which it takes a copy of the DataElement (which is currently 5) and places it in the list position of 0. How can that possibly be null?!
Edit: Nevermind, I fixed it. I overlooked not defining the array properly up top...
Updated:
Code :
public class TestQueueClass{
public static void main(String[] args){
Queue q = new Queue();
q.intializeQueue();
q.addQueue(new IntElement(5));
q.addQueue(new IntElement(12));
q.addQueue(new IntElement(-3));
q.addQueue(new IntElement(8));
q.addQueue(new IntElement(-9));
q.addQueue(new IntElement(4));
q.addQueue(new IntElement(10));
q.addQueue(q.front());
q.deleteQueue();
System.out.println("Front of queue: " + q.front());
System.out.println("Back of queue: " + q.back());
}
}
