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:
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:
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.
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.
public class TestQueueClass{ public static void main(String[] args){ Queue q = new Queue(); DataElement data = new IntElement(5); q.addQueue(data); } }
--------------------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:
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()); } }