Data Structures I Lab (3) - University of Washington



Data Structures I Lab (3)CSS 162 : Programming Methodology Autumn 2012, Instructor Rob NashSummaryThe purpose of this lab is to practice what we’ve covered in class and in the readings (Chapter 6,15) by building a stack, queue, and a list. Data Structure BackgroundA Data Structure is a composite data storage tool that organizes elements of a set and offers operations over those elements in the set. Frequently called a structure, class or set, these tools are used to provide order and operations to a collection of elements. Data structures vary in how they are built internally, how they organize data (sorted or unsorted, for example), and the operations provided. Frequently these operations are compared to one another with respect to efficiency using a notation we will cover shortly in class, called ”Big Oh” notation. One structure that is useful for quick searches (say for an airlines company searching for connections) may have disadvantages in other areas, such as in memory consumed – or trade one fast operation that will be used frequently for a slow operation that will be rarely used. Static Data StructuresIf your data structure’s size is declared at compile-time, you are a static structure in the sense that you cannot grow or shrink at runtime depending on the applications needs. These are implemented on top of arrays, which are mapped contiguously in memory for fast (or constant, meaning a Big-O(1)) access to any element. Using arrays to build more complex data structures serves as a great introduction to the behaviors and mechanics of Stacks, Queues, and (more generally) Lists. Dynamic Data StructuresThese structures can allocate and de-allocate memory at runtime depending on the requirements of the client application. These are dynamic structures in that their memory footprint may change over the duration of the program’s execution. To build such structures, it would be a needless limitation to impose contiguous storage, requiring n back-to-back blocks of memory to hold a list of n items. Thus the total memory required may be available, but if we insist on a linear mapping we may be unable to use the memory, even if available, due to fragmentation (what about coalescing holes?). Our dynamic structures will instead allocate only the memory they need wherever there is RAM available, and we will “stitch together” lists from these individual elements or nodes.Getting StartedStart by downloading the driver code and executing it. Note that the code compiles and runs as is, even though we have yet to make any data structures. This is because the driver is using Java’s preexisting library of Data Structures (which is expansive). Once you have this driver up and running, we’ll replace one data structure at a time with one you’ve built and rerun the tests looking for the same behavior we observed when using Java’s predefined data structures.Building an Array-Based Stack Class (LIFO)Create a new class called ArrayStack and define two data members for use in managing this stack. In this example, we’ll build a stack of Strings, so your array will be of type String and your count an integer.Create a new class called ArrayStack.Declare an array for your Strings and an integer for your sizepublic void push(String next) This pushes the next element onto the top of the stackpublic String pop()This returns the top element on the stack and decrements the size variablepublic boolean isEmpty()Determines if the size is zeroGo to the driver software and uncomment out the Stack driver portion, leaving the other tests commented pile and run your software with the driver Test your Stack – does it reverse the order of elements when pushed and popped?Change the type of element your stack will hold from String to ObjectYou’ll have to change the type in the push() and pop() methods, too.Did your code have errors upon making this change?Why not? How is this related to inheritance?Building an Array-Based Queue (FIFO)Start by creating a new class named ArrayQueue, and copying-and-pasting over the class we just completed (ArrayStack) above. Note that, with Inheritance, we could avoid this extra copying. Create a new class called ArrayQueue.Copy the code from ArrayStack to ArrayQueue.Change the methods push() and pop() to enqueue() and dequeue()Modify the dequeue method so that instead of returning the last element in the array it accomplishes the following:You return the first element in the array (FIFO instead of LIFO)You shift all the elements in the array over to the left by one, effectively overwriting the first element in the array (and as a side-effect, duplicating the last element)Decrement the count by 1.Test your code with the provided Queue driver.Does it print the sentence out in correct order, or reverse the words?Array-Based ListA List is more flexible than the Stack and Queue in that you can add or remove an item at any location in the list (as opposed to inserts and removes only at the ends of the list). When we have a List structure at our disposal, it’s easy to build stacks and queues on top of the list by restricting where elements are inserted and removed. Using inheritance, you can quickly reuse your List code in your Stack and Queue classes. Start by creating a new class, and copying over the code from an existing class such as ArrayQueue.Create a new class called ArrayListCopy the code from ArrayStack or ArrayQueue to ArrayListChange the methods from push() and pop() to insert(int idx) and remove(int idx)Modify the insert(int idx) method so that it will:Make room in your array by shifting all elements over starting at index idx and ending at countPut the new data item at data[idx]Add one to your count (see the diagram below to conceptualize this)tiBNotice how we shift one element beyond the existing size, to make room for the newly inserted element.tiiBInsert at 1 Overwrite the old value with the newaBtiModify the remove(int idx) method so that it will:Overwrite the element at idx with the element at idx+1, all the way to the end of your array (size – 1).Decrement your count by one.Delete index 1Test your List code using the provided driver.BtiattiBDecrement size so this is the last elementA Linked List Implementation of a StackNow that we’re familiar with the array-based versions of the Stack and Queue, we will create a new version of Stack using a different implementation. We will build a structure that functions externally just like our array-based stack we built earlier, but differs internally with respect to how we accomplish these behaviors. You start by copying and pasting your code from the Stack Class we built earlier. Then, remove the code inside each method, and remove the array and count data members. You will need only one data member here: a pointer to the beginning, head, or start of your list. This will point to the first Node object in the list, or null if the list is empty. Copy your existing Stack implementation to a new class (LinkedListStack)Jump ahead to the next section and build the Node class belowRemove the old data members and insert the Node member that starts your list.Modify the implementations of add/remove (or push/pop) to use Nodes. The following code snippets may be useful to you here.Node current = start;while(current.next != null) { //or current != nullcurrent = current.next; Test your Linked List Stack with the provided driver.The Node ClassDeclare a class that will hold two data items; one to populate the actual value(s) in the list, and the other to reference the next element in our list. This class will be quite small (2 data members and one constructor), and will usually be declared internally to the List, Stack, or Queue that uses it; this is called tight coupling, and we usually seek to avoid this (why?).Build a new private inner class to your Stack class called Node.Add the two data members inside of Nodeint data; //if we’re storing integersNode next; //our “next” pointer, null if we’re at the end of our listBuild a constructor used to initialize each of the fields in the Node.public Node(int d, Node n);OutcomesIf you can build one class, you can build a second more quickly by reusing the software you’ve already built. In this lab, we reuse this software by copying and pasting previous class code into new classes. This is one method for reuse, but it has several drawbacks. We will look next at inheritance whereby a new class can be derived from an existing class by extending the parent class and creating a child class that effectively “borrows” all of the data and methods of the parent class, in addition to introducing its own methods. You could then build a single, general List class which provides arbitrary inserts and removes at any point in the list, and then quickly build a Stack or a Queue by inheriting from the List class and modifying (overriding) the insert and remove methods as appropriate. This is the goal of your next assignment, which will be discussed further in class. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download