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 that constructs a new arrayDeque called "public ArrayDeque()"

Q2: write a method called "public void addFirst(T data)" that adds an element to the front of the 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. After the resize, the new data should be at index 0 of the array. Must be amortized O(1).

* @param data the data to add to the front of the deque

* @throws java.lang.IllegalArgumentException if data is null

Answer 1

CODE

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;

public ArrayDeque() {

backingArray = (T[])new Object[INITIAL_CAPACITY];

}

public void addFirst(T data) {

if (data == null) {

throw new IllegalArgumentException();

}

if (size == INITIAL_CAPACITY) {

T[] temp = (T[])new Object[2 * INITIAL_CAPACITY];

for (int i = 0; i < backingArray.length; i++) {

temp[i] = backingArray[i];

}

backingArray = temp;

}

if (front == -1) {

front = 0;

}

else {

front = front-1;

}

backingArray[front] = data ;

size ++;

}

}