Question

Language: Java

Topic: Deques

Using the following variables/class:

public class ArrayDeque<T> {

/**
* The initial capacity of the ArrayDeque.
*
* DO NOT MODIFY THIS VARIABLE.
*/
public static final int INITIAL_CAPACITY = 11;

// Do not add new instance variables or modify existing ones.
private T[] backingArray;
private int front;
private int size;

Q1: write a method called "public void addLast(T data)" which adds an element to the back of a Deque. If sufficient space is not available in the backing array, resize it to double the current capacity. When resizing, copy elements to the beginning of the new array and reset front to 0. Must be amortized O(1).
  
* @param data the data to add to the back of the deque
* @throws java.lang.IllegalArgumentException if data is null

Q2: write a method called "public T removeFirst()" that removes and returns the first element of the deque. Do not grow or shrink the backing array. If the deque becomes empty as a result of this call, do not reset front to 0.Replace any spots that you remove from with null. Failure to do so can result in the loss of points. Must be in O(1) and:

* @return the data formerly located at the front of the deque
* @throws java.util.NoSuchElementException if the deque is empty

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

//method to add an element to the last

public void addLast(T data) {

      // checking if array is full

      if (size == backingArray.length) {

            // creating an array of twice capacity

            T[] temp = (T[]) new Object[backingArray.length * 2];

            int index = front;

            // copying elements from old array to new array

            for (int i = 0; i < size; i++) {

                  temp[i] = backingArray[index];

                  index++;

                  if (index >= backingArray.length) {

                        // wrapping around

                        index = 0;

                  }

            }

            // replacing old array with new

            backingArray = temp;

            // resetting front to 0

            front = 0;

      }

      // (front + size) % backingArray.length will return the index of next

      // available location, adding data to this index

      backingArray[(front + size) % backingArray.length] = data;

      // updating size

      size++;

}

//remove and return element at front

public T removeFirst() {

      // throwing exception if dequeue is empty

      if (size == 0) {

            throw new NoSuchElementException("Empty Dequeue!");

      }

      // storing element at front

      T data = backingArray[front];

      // setting element at front index to null

      backingArray[front] = null;

      // updating front index, wrapping around from 0 if necessary.

      front = (front + 1) % backingArray.length;

      // updating size

      size--;

      //returning removed data

      return data;

}