Videos
Hullo. I'm currently working on an assignment revolving around creating my own Queue methods through Linked List implementation. I've done an assignment that required me to do the same for Stacks (pop, push, printStack), so I (naively) went into this thinking I could reuse my code from before.
And I wasn't wrong for the printQueue and enQueue methods. I know that Queues work on a First In First Out basis, and I'm having trouble with my deQueue method, which removes and returns the first element. For example, with a queue consisting of [3,2,1], with the entry order being 1,2, then 3, the method should remove 1, then 2, then 3. For the most part, I have this part working up until the the last element of the queue, fails to get removed and instead my code throws a NullPointerException.
public E dequeue() {
Node temp = head;
if((head == null)){ //if the head is null, then the tail is too
tail = null;
System.out.println("The list is empty.");
return null;
}
while(temp.next.next != null){
temp = temp.next;
}
temp.next = null;
return temp.data;
}The while loop iterates through the queue until it recognizes that it has reached the tail node. According to my debugger, an issue arises once I only have one node/element. I used that code for another assignment a few months back, but now it's giving me a major issue (and headache). Starting to think my implementation of temp.next.next is giving me the exception, though any help would be greatly appreciated!
Use:
Queue<Object> queue = new LinkedList<>();
You can use .offer(E e) to append an element to the end of the queue and .poll() to dequeue and retrieve the head (first element) of the queue.
Java defined the interface Queue, the LinkedList provided an implementation.
It also maintains references to the Head and Tail elements, which you can get by .getFirst() and .getLast() respectively.
credit to @Snicolas for suggesting queue interface
If you use LinkedList be careful. If you use it like this:
LinkedList<String> queue = new LinkedList<String>();
then you can violate queue definition, because it is possible to remove other elements than first (there are such methods in LinkedList).
But if you use it like this:
Queue<String> queue = new LinkedList<String>();
it should be ok,as this is heads-up to users that insertions should occur only at the back and deletions only at the front.
You can overcome defective implementation of the Queue interface by extending the LinkedList class to a PureQueue class that throws UnsupportedOperationException of any of the offending methods. Or you can take approach with aggreagation by creating PureQueue with only one field which is type LinkedList object, list, and the only methods will be a default constructor, a copy constructor, isEmpty(), size(), add(E element), remove(), and element(). All those methods should be one-liners, as for example:
/**
* Retrieves and removes the head of this queue.
* The worstTime(n) is constant and averageTime(n) is constant.
*
* @return the head of this queue.
* @throws NoSuchElementException if this queue is empty.
*/
public E remove()
{
return list.removeFirst();
} // method remove()