Skip to content

Instantly share code, notes, and snippets.

@ryanseys
Created April 5, 2013 04:52
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ryanseys/5316722 to your computer and use it in GitHub Desktop.
Queue Data Structure in Java
/**
* "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 */
/**
* 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