Queue Data Structure in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* "LinkEntry" class. | |
* This is an entry (or node) for a linked list containing an | |
* object of type E as the entry's data. | |
* @author Ryan Seys | |
* | |
* @param <E> the type of element which makes up the link entry. | |
*/ | |
public class LinkEntry<E> { | |
protected E element; // The entry's data. | |
protected LinkEntry<E> link; // The link to the next entry. | |
// Create a new link entry. | |
public LinkEntry(E element, LinkEntry<E> link) { | |
this.element = element; | |
this.link = link; | |
} // LinkEntry constructor | |
// Return the element of the link entry. | |
public E getElement() { | |
return element; | |
} // getElement method | |
// Return the link to the next link entry. | |
public LinkEntry<E> getLink() { | |
return link; | |
} // getLink method | |
// Set the link to the next link entry. | |
public void setLink(LinkEntry<E> newLink) { | |
link = newLink; | |
} // setLink method | |
} /* LinkEntry class */ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* The "Queue" class. | |
* Implements a queue using a linked list. A queue consists of a list (a | |
* sequence) of elements of type E. The elements can be added to and | |
* removed from the list in a first-in-first-out (FIFO) basis. | |
* @author Ryan Seys | |
* | |
* @param <E> the type of element which the queue is holding. | |
*/ | |
public class Queue<E> { | |
private LinkEntry<E> front; //references to the front of the queue | |
private LinkEntry<E> back; //references to the back of the queue | |
private int length; // the queue's current length | |
private int max_length; //max number of links in the queue | |
/** | |
* Create a new Queue object. The queue is empty to start. | |
*/ | |
public Queue() { | |
front = null; //reference to null, so no links | |
back = null; // no links | |
length = 0; //its empty to start. no items. | |
max_length = 100; //this is default | |
} | |
/** | |
* Add element to the rear of the queue. The queue must not be full. | |
* @param element the element that you want to add to the back of the queue | |
*/ | |
public void arrive(E element) { | |
//if its an empty list | |
LinkEntry<E> new_customer = new LinkEntry<E>(element, null); //make LinkEntry with its link pointing to null (back of line) | |
if(!full()) { // can't be full | |
if(front == null) { // if its an empty queue | |
front = new_customer; //no customers in line means the front is now the new_customer. | |
back = front; //front and back are the same because now there is only 1 person in the line. | |
} | |
//if there is an element | |
else { | |
back.setLink(new_customer); //old back links to new customer. | |
back = new_customer; //set the back now to the last customer. | |
} | |
length++; | |
} | |
else { | |
//the line is full | |
System.out.println("Cannot add anymore. Line is full!"); | |
} | |
} | |
/** | |
* Remove the element at the front of the queue. | |
* The queue must not be empty. | |
* @return the element just removed from the front of the queue | |
*/ | |
E leave() { | |
if(!empty()) { | |
//store the current front value (has to be returned later). | |
E element_to_return = front.getElement(); | |
//if there is only 1 element | |
if(length() == 1) { | |
//everything is null again (default) = 0 items. | |
front = null; | |
back = null; | |
} | |
else { | |
//get the person behind the front person | |
//set them as the new front. | |
front = front.getLink(); | |
} | |
//decrease the length of the queue. | |
length--; | |
//return the original front element. | |
return element_to_return; | |
} | |
else { | |
//display error | |
System.out.println("Can't leave queue. No items to leave. Null returned."); | |
//return null as error value. | |
return null; | |
} | |
} | |
/** | |
* @return the element at the front of the queue, without changing the queue. The queue must not be empty. | |
*/ | |
E peek() { | |
//as long as there is an item we can return. | |
if(!empty()) { | |
//get the element at the start of the queue and return it. | |
return front.getElement(); | |
} | |
else { | |
//display error if empty queue | |
System.out.println("Queue is empty. Cannot peek. Null returned."); | |
//return null as error value. | |
return null; | |
} | |
} | |
/** | |
* Returns the number of elements in the queue. | |
* @return number of elements in the queue. | |
*/ | |
int length() { | |
return length; | |
} | |
/** | |
* Returns whether the queue is empty or not. | |
* @return true if the queue contains no elements. | |
*/ | |
boolean empty() { | |
if(length() == 0) { | |
return true; | |
} | |
else return false; | |
} | |
/** | |
* Returns whether the queue is full or not. | |
* @return true if the queue cannot hold any more elements. | |
*/ | |
boolean full() { | |
if(length >= max_length) { | |
return true; | |
} | |
else return false; | |
} | |
/** | |
* Print the queue out, for testing purposes only. | |
*/ | |
void print() { | |
LinkEntry<E> curr = front; | |
if(length() == 0) { | |
System.out.println("Start -> [ ] <- End"); | |
} | |
else { | |
System.out.print("Start -> ["); | |
for(int i = 0; i < length(); i++) { | |
System.out.print(curr.element.toString() +", "); | |
curr = curr.link; | |
} | |
System.out.print("] <- End\n"); | |
} | |
} | |
} /* Queue class */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment