Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
4
I think this is a continuation of this other post:
http://forum.codecall.net/java-tutorials/41122-generic-queue.html
In wich I read about a generic queue made with memory references. So now that I have a little free time I'm going to post my code and explain it.
This one could be a little complicated to understand because I am using what we can call "pointers". For that I've implemented a generic Node, wich has a pointer to the next element of the queue and for the element that is before him.
package classes;
public class Node<T>
{
private T element;
private Node<T> next;
private Node<T> before;
public Node(T element)
{
this.element = element;
next = before = null;
}
public void setElement(T element)
{
this.element = element;
}
public T getElement()
{
return element;
}
public void setNext(Node<T> next)
{
this.next = next;
}
public Node<T> getNext()
{
return next;
}
public void setBefore(Node<T> before)
{
this.before = before;
}
public Node<T> getBefore()
{
return before;
}
}
Quite simple, a generic element and two references, that's it.
The generic element is quite simple but now is when we have problems. It is you who is supposed to check if every memory reference has been asigned correctly. Here is the class:
package classes;
public class GenericQueue<T>
{
private Node<T> first;
private Node<T> last;
private int numElem; //Number of elements
public GenericQueue()
{
numElem = 0;
first = last = null;
}
public GenericQueue(T value)
{
numElem = 1;
first = new Node<T>(value);
last = first;
}
public int getNumElem()
{
return numElem;
}
public T getHeadElement()
{
return first.getElement();
}
public void Push(T value)
{
switch(numElem)
{
case 0:
first = new Node<T>(value);
last = first;
break;
case 1:
last = new Node<T>(value);
last.setBefore(first);
first.setNext(last);
break;
default:
Node<T> aux = new Node<T>(value);
aux.setBefore(last);
last.setNext(aux);
last = aux;
break;
}
numElem++;
}
public T Pop()
{
T value = null;
if(numElem != 0)
{
if(numElem == 1)
{
value = last.getElement();
first = last = null;
}
else
{
value = first.getElement();
first = first.getNext();
first.setBefore(null);
}
numElem--;
}
return value;
}
public boolean isEmpty()
{
return numElem == 0;
}
}
Instead of an array or arraylist, we have two main variables in the class: the head (first) and the tail (last) of the queue. The numElem is just the number of element in the queue. I've made it like this just to don't have to calculate it constantly, and only has a public get, no setters.
isEmpty: returns if the queue is empty by looking the number of element in the queue
getHeadElement: returns the first element in the queue. Does the same thing as Pop but without deleting the first element of the queue
getNumElem: returns the number of elements in the queue
GenericQueue(): Constructor. Makes an empty queue
GenericQueue(T value): Constructor. Makes a queue with one element
And now, the main methods: push and pop.
PUSH
We have 3 possible scenarios when we insert an element in a queue:
1.- The queue is empty
2.- The queue has one element
3.- The queue has more than one element
For the first possibility, we just have to do the same as the constructor GenericQueue(T value), no big deal.
For the second, we have to create a node. That will be our new last element of the queue (the tail), now we have to assign the element before the tail as the head node, and the next node of the head as the tail node
last = new Node<T>(value); last.setBefore(first); first.setNext(last);
For the last one, we create an auxiliar node and set the same reference as the tail. After that create the new tail node and assign references as in the second option
Node<T> aux = new Node<T>(value); aux.setBefore(last); last.setNext(aux); last = aux;
POPIn this method we have another two options:
1.- The queue has 1 element
2.- The queue has more than 1 element
For the first option we save the value of the head or the tail (it will have the same references) and then, delete the node.
value = last.getElement(); first = last = null;
For the last option we save the vaule of the head. After this reassign the reference of the head to his next element
value = first.getElement(); first = first.getNext(); first.setBefore(null);
An here we have a main class to see how it works x)
package main;
import classes.GenericQueue;
public class Main {
/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
GenericQueue<Integer> q = new GenericQueue<Integer>();
q.Push(3);
q.Push(7);
q.Push(8);
System.out.println("First element in the queue: "+q.getHeadElement());
while(!q.isEmpty())
{
System.out.println(q.Pop());
}
}
}
And it's output:
First element in the queue: 3
3
7
8
Hope this could help someone x)
Back to top
