Data Structures Programming in Java

Here is a sample makefile that you can copy and modify as needed (if you use other .java classes). For any classes described in the assignment, use the filenames and naming conventions we provide for uniformity. http://www1.cs.columbia.edu/ bert/courses/3134/hw2/Makefile

(Weiss 3.28)

A deque is a data structure consisting of a list of items, on which the following operations are possible: push(x): Insert item x on the front end of the deque. pop(): Remove the front item from the deque and return it. inject(x): Insert item x on the rear end of the deque. eject(): Remove the rear item from the deque and return it. Each of these operations should execute in O(1) time. Name your deque class MyDeque and use the exact method names described above. Your class should be generic and may use either the built in Java ArrayList/LinkedList classes or the textbooks MyArrayList/MyLinkedList implementations. (Hint: you should only need one of these.) Alternatively, you can also build this data structure from scratch, without piggybacking on these other classes. Test your class using the class MyDequeTester.

/* * MyDequeTester.java. A simple test class for the deque data * structure. First some basic integrity checks to make sure the * ordering of pushed, popped, injected and ejected items is correct, * then a stress test injecting and popping 500 thousand items, which * should be fast as long as the operations are implemented * efficiently with O(1) time. */ public class MyDequeTester { public static void check(Integer x, Integer y) { if (x.equals(y)) System.out.println("Success!"); else System.out.println("********* Failure: value was "+x); } public static void main(String [] args) { Integer tmp; MyDeque dq = new MyDeque(); System.out.println("Pushing 100"); dq.push(100); System.out.println("Pushing 150"); dq.push(150); System.out.println("Pushing 200"); dq.push(200); System.out.println("The deque is currently: "+dq); System.out.println("Popping... Should be 200"); tmp = dq.pop(); check(tmp, 200); System.out.println("Ejecting... Should be 100"); tmp = dq.eject(); check(tmp, 100); System.out.println("Injecting 1000"); dq.inject(1000); System.out.println("Ejecting... should be 1000"); tmp = dq.eject(); check(tmp, 1000); System.out.println("Ejecting... should be 150"); tmp = dq.eject(); check(tmp, 150); // Begin stress testing for (int i=0; i<250000; i++) { dq.push(i); dq.inject(-i); } System.out.println("Stress testing complete. If that didn't take too "+ "long, your class is efficiently coded"); } }