2016-04-01 Deque

posted Apr 1, 2016, 8:15 AM by Samuel Konstantinovich   [ updated Apr 1, 2016, 10:45 AM ]
Goal: Double Ended Queue : Deque ...

http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html (pronounced Deck)
You will write MyDeque.java in your github folder 10. I expect several commits per coding session to track your changes over time. I expect you to have several commits in class as you build this data structure. 

-You will be using a "circular array" to implement this. 
-You can add to the beginning or end of a circular array, and just update the start and end variables which store the index of the last and first value. 
-When you go past the end of the array, you wrap around to the beginning. 
-When you have 1 value, start == end
-When you have 0 values, the start and end do not matter. 
Some examples of how the array wraps around:
Empty:
  0  1  2  3  4  5  6  7  8  9
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
size is 0
start and end do not matter.

full of 0's:
  0  1  2  3  4  5  6  7  8  9
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
size is 10
start = 0
end = 9

full of 0's with a different start/end:
  0  1  2  3  4  5  6  7  8  9
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
size is 10
start = 3
end = 2


full of 0-9 with a different start/end:
  0  1  2  3  4  5  6  7  8  9
[ 5, 6, 7, 8, 9, 0, 1, 2, 3, 4]
size is 10
start = 5
end = 4

NOT-full contains 3-8 :
  0  1  2  3  4  5  6  7  8  9
[ 8, 0, 0, 0, 0, 3, 4, 5, 6, 7]
size is 6
start = 5
end = 0


LAB!
You will now write a MyDeque()
You can use a Deque as a queue or a stack!
This Deque will be faster for many operations once the Deque stops resizing to be larger. 

For your MyDeque<T>



0a. You need an array of objects!!!!
This means you need to typecast to object and here is how we can get rid of the warnings. 
This is REALLY bad form, but we will discuss it in class on Tuesday.

public class Tester<T>{
    //generic array
    T[] data;

    //suppress this ONE function from
    //having warnings.
    @SuppressWarnings("unchecked")	    
    public Tester(){
	//typecast object array to generic array
	data = (T[]) new Object[10];
    }
    
    public void add(T n){
	data[0]=n;
    }

    public T get(){
	
	return data[0];
    }
    
    public static void main(String[]args){
	Tester<String> x = new Tester<String>();
	x.add("fish");
	System.out.println(x.get());
    }
}


0b. You need a private method to grow the array and copy over the values. 
There are 6 public methods:
1. void addFirst(T value)
2. void addLast(T value)
-When the array is full, re-size, then add. 
-No exceptions are required since you will re-size.

3. T removeFirst()  
4. T removeLast()  
-NoSuchElementException is thrown when there are no elements. 

5. T getFirst()
6. T getLast()
-NoSuchElementException is thrown when there are no elements. 

Comments