Assume that the data stored in each element is a character or integer (you may c
ID: 3747189 • Letter: A
Question
Assume that the data stored in each element is a character or integer (you may choose whichever you think is more convenient) All JAVA implementations should implement a method returning string representation of the list/queue where each element is placed between brackets "[x]" and adjacent elements are separated by a comma"," You are not allowed to use Java library implementations of the data structures (queues, lists etc.) The idea is that you should learn to implement the internals yourself Explain all lines of code, properly document everything! Question: In JAVA Implement a generic iterable FIFO-queue based on a double linked list.Explanation / Answer
A queue is a container of objects that are inserted and removed according to the first-in first-out (FIFO) principle. An example of a queue is a line of students in the food court of the UC. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed they are:
Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access.
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
Implementation of a generic iterable FIFO-queue based on a double linked list
import java.util.Iterator;
import java.util.NoSuchElementException;
//Implementation of generic iterable FIFO-queue based on a double linked list
class Queue<Item> implements Iterable<Item>
{
private int size;
private Node first; //begin node
private Node last; //end node
public Queue() //zero argument constructor
{ }
public boolean isEmpty() //returns true if queue is empty
{
return first == null;
}
public int size() //returns current size
{
return size;
}
public void addFirst(Item item) //adding of first element into queue
{
throwIfNull(item); //calls method to handle an Exception when the item is null
Node newFirst = new Node(); //creates an object to create a node
newFirst.item = item; //creation of node
if (first != null) { //inserting the first element
newFirst.next = first;
first.previous = newFirst;
}
first = newFirst;
if (last == null) last = first;
size++;
}
public Item removeFirst() //removing first element
{
throwIfEmpty(); //calls method to handle an Exception when the queue is empty
Node oldFirst = first; //creating a reference variable to point to the first item of the queue
first = first.next; // here,element next to the first element is made as first element of thequeue
if (first == null) //now the first element will be the element next to the previous first element
last = null;
else
first.previous = null;
size--;
return oldFirst.item; //returns the removed element
}
public void addLast(Item item) //adding last element into queue
{
throwIfNull(item); //calls method to handle exception when item is null
Node newLast = new Node(); //creates an object to create a node
newLast.item = item; //creation of node
if (last != null) {
newLast.previous = last; //inserting the last element
last.next = newLast;
}
last = newLast;
if (first == null) first = last;
size++;
}
public Item removeLast() //removes the last element
{
throwIfEmpty();
Node oldLast = last; //creating a reference variable to point to the last item of the queue
last = oldLast.previous;
if (last == null)
first = null;
else
last.next = null;
size--;
return oldLast.item; //returns the last element
}
private void throwIfEmpty() //throws an exception if queue is empty
{
if (first == null)
throw new NoSuchElementException();
}
private void throwIfNull(Item item) //throws an exception if the item is null
{
if (item == null)
throw new NullPointerException();
}
@Override
public Iterator<Item> iterator()
{
return new ItemsIterator();
}
private class ItemsIterator implements Iterator<Item>
{
private Node current;
public ItemsIterator() {
current = first;
}
@Override
public boolean hasNext() //retuuns true if there are any next item to the current item
{
return current != null;
}
@Override
public Item next() { //it points to the next item of the current item
if (current == null)
throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
//creates node
private class Node {
Item item;
Node next;
Node previous;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.