java programming, need write the set,get,add and remove function in the fourque
ID: 3667825 • Letter: J
Question
java programming, need write the set,get,add and remove function in the fourque class
Design and implement a Fourque class that is a List with four fast access points. Both get(i) and set(i,x) must have constant runtime. Both add(i,x) and remove(i) should run in time O(min[i,n?i,|n/3?i|,|2n/3?i|]).
this is factory class.
import java. util. AbstractList Fourque: an implementation of the List interface * that allows for fast modifications at the FOUR places * in the list: front, 1/3 in, 2/3 in and the back * Modify the methods so that *set/get have constant runtime k -add/remove have runtime * + minl i, sizeO-i, size/3-il, 12sizeO/3-il) * Oparam the type of objects stored in this list ks/ public class FourqueExplanation / Answer
ArrayDeque.java import java.util.AbstractList; /** * An implementation of the List interface that allows for fast modifications * at both the head and tail. * * The implementation is as a circular array. The List item of rank i is stored * at a[(j+i)%a.length]. Insertions and removals at position i take * O(1+min{i, size()-i}) amortized time. * @author morin * * @param the type of objects stored in this list * TODO: Implement addAll() and removeAll() efficiently */ public class ArrayDeque extends AbstractList { /** * The class of elements stored in this queue */ protected Factory f; /** * Array used to store elements */ protected T[] a; /** * Index of next element to de-queue */ protected int j; /** * Number of elements in the queue */ protected int n; /** * Grow the internal array */ protected void resize() { T[] b = f.newArray(Math.max(2*n,1)); for (int k = 0; k n-1) throw new IndexOutOfBoundsException(); return a[(j+i)%a.length]; } public T set(int i, T x) { if (i < 0 || i > n-1) throw new IndexOutOfBoundsException(); T y = a[(j+i)%a.length]; a[(j+i)%a.length] = x; return y; } public void add(int i, T x) { if (i < 0 || i > n) throw new IndexOutOfBoundsException(); if (n+1 > a.length) resize(); if (i n - 1) throw new IndexOutOfBoundsException(); T x = a[(j+i)%a.length]; if (i 0; k--) a[(j+k)%a.length] = a[(j+k-1)%a.length]; j = (j + 1) % a.length; } else { // shift a[i+1],..,a[n-1] left one position for (int k = i; kRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.