Question

Create a Java code that includes all the methods from the Lecture slides following the ADTs

LECTURE SLIDES

Collect/finish the Java code (interface and the complete working classes) from lecture slides for the following ADTS: 4) Queue ADT that uses a linked list internally (call it LQueue) Make sure you keep the same method names as in the slides (automatic testing will be performed)! For each method you develop, add comments and estimate the big-O running time of its algorithm. In the comments additionally explain the advantages of the array-based implementation over the linked- list-based implementation and vice versa. Keep your code nicely formatted and follow good programming practices. Try to make the code robust and try to use generics. The Array List ADT /**Simplified version of java.util. List */ public interface List { /**Returns the number of elements in this list */ public int size(); /**Returns whether the list is empty. */ public boolean isEmpty() /** Inserts an element e to be at index I, shifting all elements after this. */ public void add(int I, E e) throws IndexOutOfBoundsException; /** Returns the element at index I, without removing it. */ public E get(int i) throws IndexOutOfBoundsException; /** Removes and returns the element at index I, shifting the elements after this. */ public E remove(int i) throws IndexOutOfBounds Exception; /**Replaces the element at index I with e, returning the previous element at i. */ public E set(int I, E e) throws IndexOutOfBoundsException; } The Queue ADT Auxiliary queue operations: The Queue ADT stores arbitrary objects object front(): returns the element at the front without Insertions and deletions follow removing it the first-in first-out (FIFO) integer size(): returns the number of elements stored scheme Insertions are at the rear of the boolean isEmpty(): indicates whether no elements are stored queue and removals are at the front of the queue Exceptions Main queue operations: Attempting the execution of dequeue or front on an queue throws an EmptyQueueException enqueue(object): inserts an element at the end of the queue empty object dequeue( removes and - returns the element at the front Attempting to enqueue an element on a queue that is full can be signaled with a FullQueueException of the queue

Answer 1

1.Queue ADT using linked list internally:

// Implementation of queue using linked list internally
// Noade class
class QNode
{
   int data;
   QNode nextNode;
  
   // constructor to create a new linked list node
   public QNode(int data) {
       this.data = data;
       this.nextNode = null;
   }
}

// A class to represent a queue
//The queue, front stores the front node and rear stores the last node of LL
class Queue
{
   QNode front, rear;
  
   public Queue() {
       this.front = this.rear = null;
   }
  
   // Method to add an data to the queue.
   void enqueue(int data)
   {
      
       // Create a new LL node
       QNode temp = new QNode(data);
  
       // If queue is empty, then new node is front and rear both
       if (this.rear == null)
       {
       this.front = this.rear = temp;
       return;
       }
  
       // Add the new node at the end of queue and change rear
       this.rear.nextNode = temp;
       this.rear = temp;
   }
  
   // Method to remove an data from queue.
   QNode dequeue()
   {
       // If queue is empty, return NULL.
       if (this.front == null)
       return null;
  
       // Store previous front and move front one node ahead
       QNode temp = this.front;
       this.front = this.front.nextNode;
  
       // If front becomes NULL, then change rear also as NULL
       if (this.front == null)
       this.rear = null;
       return temp;
   }
}

public class Example
{
   public static void main(String[] args)
   {
       Queue q=new Queue();
       q.enqueue(1);
       q.enqueue(2);
       q.dequeue();
       q.dequeue();
       q.enqueue(3);
       q.enqueue(4);
       q.enqueue(5);
      
       System.out.println("Dequeued item is "+ q.dequeue().data);
   }
}