Question

import java.util.NoSuchElementException;

public class ArrayBasedDeque<AnyType> implements deque<AnyType> {
  
   private static int MAX_SIZE = 5; // initial array size
   //DO NOT CHANGE this, it is set to 5 to make sure your code
   //will pass all the tests and works with no issue.

  
   // add all data fields which are required

   /**
   * ArrayBasedDeque() constructs an empty deque.
   */
   public ArrayBasedDeque(){
       //complete
   }
  
   /**
   * Returns the size of the deque
   * @return the number of elements in this deque
   */
   public int size() {
       //complete
      
   }
  
   /**
   * Removes all elements from this deque
   */
   public void clear() {
       //complete
   }
  
   /**
   * Tests if the deque contains no element
   * @return true if the deque contains no element
   */
   public boolean isEmpty() {
   //complete
   }
  
   /**
   * Adds an item to this front of the deque
   * @param x any object
   */
   public void addFirst(AnyType x) {
       //complete
   }
  
   /**
   * Adds an item to this rear of the deque
   * @param x any object
   */
   public void addLast(AnyType x) {
       //complete
   }
  
   /**
   * Remove and return the item at the front of the deque.
   * @return the item that was removed from the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType removeFirst() throws NoSuchElementException{
       //complete
   }
  
   /**
   * Remove and return the item at the rear of the deque.
   * @return the item that was removed from the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType removeLast() throws NoSuchElementException{
       //complete
   }
  
   /**
   * Returns the item at position index in deque
   * front of the deque will be considered as index 0,
   * index 1 is the next item, and so on
   * @param index the index to search in
   * @return return the item in index
   * @throws IndexOutOfBoundsException if index is out ot bound
   */
   public AnyType get(int index) throws IndexOutOfBoundsException {
       //complete
   }
  
   /**
   * Return the item at the rear of the deque.
   * @return the item the rear of the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType getLast() throws NoSuchElementException{
       //complete
   }
  
   /**
   * Return the item at the front of the deque.
   * @return the item the front of the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType getFirst() throws NoSuchElementException{
       //complete
   }
  
   public String toString() {
       //complete
       String output = "[ ";
       for(int i = 0; i < numItems; i++)
           output += items[i] + " ";
   output += "]";
       return output;
   }
}

if the following methods,

can someone help me what should i use/input in the method- size, clear, isempty, addfirst, addlast, removefirst, removelast, get , getlast, getfirst?(method fields are empty and there is a comment to complet them)

we have to use recursion and these are the requirements,

Your operations are subject to the following rules:

● All four operations on add and remove must not involve any looping or recursion. Each operation must take “constant time”, except during expanding the array.

● size, get, getFirst and getLast operations must take “constant time”

Answer 1

Following are implementation method that is asked for.

import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class ArrayBasedDeque<AnyType> implements Deque<AnyType> {
  
   private static int MAX_SIZE = 5; // initial array size
   //DO NOT CHANGE this, it is set to 5 to make sure your code
   //will pass all the tests and works with no issue.
   
   private Object [] items;
   
   private int numItems;
  
   // add all data fields which are required

   /**
   * ArrayBasedDeque() constructs an empty deque.
   */
   public ArrayBasedDeque(){
       //complete
       items = new Object[MAX_SIZE];
       numItems = 0;
   }
  
   /**
   * Returns the size of the Deque
   * @return the number of elements in this deque
   */
   public int size() {
       //complete
      return numItems;
   }
  
   /**
   * Removes all elements from this deque
   */
   public void clear() {
       //complete
       for(int i = 0; i < numItems; i++)
       {
           items[i] = null;
       }
   }
  
   /**
   * Tests if the deque contains no element
   * @return true if the deque contains no element
   */
   public boolean isEmpty() {
   //complete
   
   return numItems == 0;
   }
  
   /**
   * Adds an item to this front of the deque
   * @param x any object
   */
   public void addFirst(AnyType x) {
       //complete
       if(items.length == numItems)
       {
           Object []temp = new Object[items.length + MAX_SIZE];
           
           System.arraycopy(items, 0, temp, 1,items.length );
           
           items = temp;
       }
       else if(numItems > 0)
       {
           System.arraycopy(items, 0, items, 1,numItems );
       }
       
       numItems++;
       
       items[0] = x;
   }
  
   /**
   * Adds an item to this rear of the deque
   * @param x any object
   */
   public void addLast(AnyType x) {
       //complete
       
       if(items.length == numItems)
       {
           Object [] temp = new Object[items.length + MAX_SIZE];
           
           System.arraycopy(items, 0, temp, 0,items.length );
           
           items = temp;
       }
       
       numItems++;
       
       items[numItems - 1] = x;
   }
  
   /**
   * Remove and return the item at the front of the deque.
   * @return the item that was removed from the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType removeFirst() throws NoSuchElementException{
       //complete
     
       if(numItems == 0)
           throw new NoSuchElementException();
       
       Object first = items[0];
       
       System.arraycopy(items, 1, items, 0,items.length - 1 );
       
       items[numItems - 1] = null;
       
       numItems--;
       
       return (AnyType)first;
   }
  
   /**
   * Remove and return the item at the rear of the deque.
   * @return the item that was removed from the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType removeLast() throws NoSuchElementException{
       //complete
       
       if(numItems == 0)
           throw new NoSuchElementException();
       
       Object last = items[numItems-1];
       
       items[numItems-1] = null;
       
       numItems--;
       
       return (AnyType)last;
   }
  
   /**
   * Returns the item at position index in deque
   * front of the deque will be considered as index 0,
   * index 1 is the next item, and so on
   * @param index the index to search in
   * @return return the item in index
   * @throws IndexOutOfBoundsException if index is out ot bound
   */
   public AnyType get(int index) throws IndexOutOfBoundsException {
       //complete
       if(index > numItems)
           throw new IndexOutOfBoundsException();
       return (AnyType)items[index];
   }
  
   /**
   * Return the item at the rear of the deque.
   * @return the item the rear of the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType getLast() throws NoSuchElementException{
       //complete
       
       if(numItems == 0)
           throw new NoSuchElementException();
       return (AnyType)items[numItems - 1];
   }
  
   /**
   * Return the item at the front of the deque.
   * @return the item the front of the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType getFirst() throws NoSuchElementException{
       //complete
       if(numItems == 0)
           throw new NoSuchElementException();
       return (AnyType)items[0];
   }
  
   public String toString() {
       //complete
       String output = "[ ";
       for(int i = 0; i < numItems; i++)
           output += items[i] + " ";
       output += "]";
       return output;
   }
}

If you don't implement Deque<AnyType> then above code is complete.

Since aove code not implemented all mehtod of Deque, is not complete and give error. Below are complete code.

import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class ArrayBasedDeque<AnyType> implements Deque<AnyType> {
  
   private static int MAX_SIZE = 5; // initial array size
   //DO NOT CHANGE this, it is set to 5 to make sure your code
   //will pass all the tests and works with no issue.
   
   private Object [] items;
   
   private int numItems;
  
   // add all data fields which are required

   /**
   * ArrayBasedDeque() constructs an empty deque.
   */
   public ArrayBasedDeque(){
       //complete
       items = new Object[MAX_SIZE];
       numItems = 0;
   }
  
   /**
   * Returns the size of the Deque
   * @return the number of elements in this deque
   */
   public int size() {
       //complete
      return numItems;
   }
  
   /**
   * Removes all elements from this deque
   */
   public void clear() {
       //complete
       for(int i = 0; i < numItems; i++)
       {
           items[i] = null;
       }
   }
  
   /**
   * Tests if the deque contains no element
   * @return true if the deque contains no element
   */
   public boolean isEmpty() {
   //complete
   
   return numItems == 0;
   }
  
   /**
   * Adds an item to this front of the deque
   * @param x any object
   */
   public void addFirst(AnyType x) {
       //complete
       if(items.length == numItems)
       {
           Object []temp = new Object[items.length + MAX_SIZE];
           
           System.arraycopy(items, 0, temp, 1,items.length );
           
           items = temp;
       }
       else if(numItems > 0)
       {
           System.arraycopy(items, 0, items, 1,numItems );
       }
       
       numItems++;
       
       items[0] = x;
   }
  
   /**
   * Adds an item to this rear of the deque
   * @param x any object
   */
   public void addLast(AnyType x) {
       //complete
       
       if(items.length == numItems)
       {
           Object [] temp = new Object[items.length + MAX_SIZE];
           
           System.arraycopy(items, 0, temp, 0,items.length );
           
           items = temp;
       }
       
       numItems++;
       
       items[numItems - 1] = x;
   }
  
   /**
   * Remove and return the item at the front of the deque.
   * @return the item that was removed from the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType removeFirst() throws NoSuchElementException{
       //complete
     
       if(numItems == 0)
           throw new NoSuchElementException();
       
       Object first = items[0];
       
       System.arraycopy(items, 1, items, 0,items.length - 1 );
       
       items[numItems - 1] = null;
       
       numItems--;
       
       return (AnyType)first;
   }
  
   /**
   * Remove and return the item at the rear of the deque.
   * @return the item that was removed from the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType removeLast() throws NoSuchElementException{
       //complete
       
       if(numItems == 0)
           throw new NoSuchElementException();
       
       Object last = items[numItems-1];
       
       items[numItems-1] = null;
       
       numItems--;
       
       return (AnyType)last;
   }
  
   /**
   * Returns the item at position index in deque
   * front of the deque will be considered as index 0,
   * index 1 is the next item, and so on
   * @param index the index to search in
   * @return return the item in index
   * @throws IndexOutOfBoundsException if index is out ot bound
   */
   public AnyType get(int index) throws IndexOutOfBoundsException {
       //complete
       if(index > numItems)
           throw new IndexOutOfBoundsException();
       return (AnyType)items[index];
   }
  
   /**
   * Return the item at the rear of the deque.
   * @return the item the rear of the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType getLast() throws NoSuchElementException{
       //complete
       
       if(numItems == 0)
           throw new NoSuchElementException();
       return (AnyType)items[numItems - 1];
   }
  
   /**
   * Return the item at the front of the deque.
   * @return the item the front of the deque
   * @throws NoSuchElementException if the deque is empty
   */
   public AnyType getFirst() throws NoSuchElementException{
       //complete
       if(numItems == 0)
           throw new NoSuchElementException();
       return (AnyType)items[0];
   }
  
   public String toString() {
       //complete
       String output = "[ ";
       for(int i = 0; i < numItems; i++)
           output += items[i] + " ";
       output += "]";
       return output;
   }

        @Override
        public boolean offerFirst(AnyType e) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean offerLast(AnyType e) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType pollFirst() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType pollLast() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType peekFirst() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType peekLast() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean removeFirstOccurrence(Object o) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean removeLastOccurrence(Object o) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean add(AnyType e) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean offer(AnyType e) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType remove() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType poll() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType element() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType peek() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public void push(AnyType e) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public AnyType pop() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean remove(Object o) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean contains(Object o) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public Iterator<AnyType> iterator() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public Iterator<AnyType> descendingIterator() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public Object[] toArray() {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public <T> T[] toArray(T[] a) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean containsAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean addAll(Collection<? extends AnyType> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean removeAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }

        @Override
        public boolean retainAll(Collection<?> c) {
            throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
        }
    }

If you find this helpful give thumb up.

if you have any query, ask in comment section.

Regard.