This is DynamicArray.java:

import java.util.Arrays;
public class DynamicArray{
   private int array[];
   // holds the current size of array
   private int size;
   // holds the total capacity of array
   private int capacity;
   
   // default constructor to initialize the array and values
   public DynamicArray(){
       array = new int[2];
       size=0;
       capacity=2;
   }
   
   // to add an element at the end
   public void addElement(int element){
       // double the capacity if all the allocated space is utilized
       if (size == capacity){
           ensureCapacity(2);
       }
       array[size] = element;
       size++;
   }
   
   // to add an element at a particular index
   public void addElement(int index, int element){
       // double the capacity if all the allocated space is utilized
       if (size == capacity){
           ensureCapacity(2);
       }
       // shift all elements from the given index to right
       for(int i=size-1;i>=index;i--){
           array[i+1] = array[i];
       }
       // insert the element at the specified index
       array[index] = element;
       size++;
   }

   // to get an element at an index
   public int getElement(int index){
       return array[index];
   }
   
   // to remove an element at a particular index
   public void remove(int index){
       if(index>=size || index           System.out.println("No element at this index");
       }else{
           for(int i=index;i               array[i] = array[i+1];
           }
           array[size-1]=0;
           size--;
       }
   }
   
   /* method to increase the capacity, if necessary, to ensure it can hold at least the
   *  number of elements specified by minimum capacity arguement
   */
   public void ensureCapacity(int minCapacity){
       int temp[] = new int[capacity*minCapacity];
       for (int i=0; i            temp[i] = array[i];
       }
       array = temp;
       capacity = capacity * minCapacity;
   }
   
   /*
   *  Trim the capacity of dynamic array to the current size. i.e. remove unused space
   */
   public void trimToSize(){
       System.out.println("Trimming the array");
       int temp[] = new int[size];
       for (int i=0; i            temp[i] = array[i];
       }
       array = temp;
       capacity = array.length;
       
   }
   
   // to get the current size
   public int size(){
       return size;
   }
   
   // to get the current capacity
   public int capacity(){
       return capacity;
   }
   
   // method to print elements in array
   public void printElements(){
       System.out.println("elements in array are :"+Arrays.toString(array));
   }
}

This is ListArray.java:

import java.io.*;

public class LinkedList {

   Node head;
   static class Node {

       int data;
       Node next;
       Node(int num)
       {
           data = num;
           next = null;
       }
   }

   public static LinkedList insert(LinkedList list,int data)
   {
       Node new_node = new Node(data);
       new_node.next = null;
       if (list.head == null)
       {
           list.head = new_node;
       }
       else
       {
           Node last = list.head;
           while (last.next != null)
           {
               last = last.next;
           }
           last.next = new_node;
       }
       return list;
   }
   public static void printList(LinkedList list)
   {
       Node currNode = list.head;

       System.out.print("LinkedList: ");

       while (currNode != null)
       {
         
           System.out.print(currNode.data + " ");
           currNode = currNode.next;
       }
   }
}

This is StackInterface:

interface StackInterface {

   /*
    * Add an element to the top of the stack.
    */
   void push(int value);

   /*
    * Remove and return the top element in the stack.
    *
    * If the user attempts to pop an empty stack, ignore the
    * request (i.e. make no changes to the stack) and return -1.
    */
   int pop();

   /*
    * Return (but do NOT remove) the top element of the stack.
    *
    * If the user attempts to peek on an empty stack, ignore the
    * request (i.e. make no changes to the stack) and return -1.
    */
   int peek();

   /*
    * Returns true if the stack has no elements.
    */
   boolean isEmpty();

   /*
    * Returns the number of elements in the stack.
    */
   int size();

   /*
    * Removes all elements from the stack.
    */
   void clear();

}

Requirements Many data structures are built with either arrays or linked structures. You will implement a stack and a queue in both of these ways and then compare their performance. Two files are provided, StackInterface.java and QueueInterface.java which define the interfaces for a stack and queue. Six classes need to be implemented: DynamicArray.java - a dynamic array, an array that can be resized. LinkedList.java - a singly linked list. ArrayStack.java - implementation of the StackInterface using DynamicArray. ListStack.java - implementation of the StackInterface using LinkedList. ArrayQueue.java - implementation of the QueueInterface using DynamicArray. ListQueue.java - implementation of the QueueInterface using LinkedList. In addition to the methods defined in the interfaces, the following methods need to be implemented: toString equals copy constructors The toString method should return a string in the format: "{0,1,2,3,4,5}". There are no spaces in the string and if there are no elements at all, then print "{}". In the above example, '0' would be at the bottom of the stack and '5' would be at the top. If it was a queue, '0' would be at the front of the queue and '5' would be at the back. Two stacks (or queues) are equal if their sizes and all of their elements are equal. For each method in the stack and queue interfaces that you implement, put in the comment section the time complexity for the method, using big-O notation. Only simple error handling is used in this PA. Athough later we will use exceptions, here the 'error' return values are specified in the comments of the interfaces. You should not print anything in any of your classes. i.e. do not call 'System.out.println' anywhere in your code. You can use print statements to debug but be sure to remove them all before submitting your files.