CSSE 221: Fundamentals of Software Development Honors

Written Homework (due Monday, October 30, at the beginning of class)

1. Read Section 14.2 (Generics); Review 15.1 and read 15.2- 15.4 (Advanced Linked Lists) page 855-859, pp. 660-662 (Stacks and Queues)
2. (Not for the capsules) Which data structure has your team decided to use? Explain how it will be a natural part of your project (revisit the Capstone instructions if this isn’t ringing a bell).

Stacks and Queues

3. In the Java API (and many data structures books), adding a piece of data to a Stack is called "pushing" it on the Stack, and removing a piece of data from a Stack is called "popping" it off the Stack. For example, "push 12" means put the number 12 onto the top of the Stack; "pop" means remove the top item from the Stack.

   Draw a diagram of what a Stack for integer data would look like after the following commands:

   push 6
   push 7
   push 3
   pop
   push 4
   push 4
   push 15
   pop
   pop
   pop
   

   Draw an arrow to the top of the Stack in your diagram.

In the Java API, adding a piece of data to a Queue is called "offering", whereas removing a piece of data is called "polling" it. For example, "offer 6" means add the integer 6 to the end of the Queue; "poll" means remove the front item from the Queue.

Draw a diagram of what a Queue for integer data would look like after the following commands:

offer 6
offer 7
offer 3
poll
offer 4
offer 4
offer 15
poll
poll
poll

Draw an arrow to the front of the Queue in your diagram.

5. Answer the following:
   • Do students standing in the cafeteria line waiting to have their ID cards checked form a Stack or a Queue?
   • What would happen if students in that same line had to get their food using the other data structure?
6. Notice in the Java API that a Queue is an interface, implemented by a number of other classes, one of which is a LinkedList.
   1. What is a good reason for using a LinkedList rather than some type of array?
   2. Write Java code to declare a Queue of integers, then add the integers 4,5, and 6 in turn, then remove the front of the Queue. (Use the API; don't re-implement Queues!)
7. What two common conventions are followed to make it easy to identify a class as using generics?
8. Consider the following simple class used to control access to an integer.

   public class DataHolder {
   	private int data;
   	public DataHolder(int data) {
   		this.setData(data);
   	}
   	public int getData() {
   		return this.data;
   	}
   	public void setData(int data) {
   		this.data = data;
   	}
   }
   

   1. Rewrite it using generics.
   2. Declare and construct a DataHolder to hold the string "Bob" using the genericized class.
9. Prior to Java 1.5, there were no generics.
   • Say I wanted to rewrite the following code not using generics. I just take away the <String>, it won't compile. What else do I need to do? (Feel free to use your IDE to check this.)

     ArrayList<String> arr = new ArrayList<String>();
     arr.add("hello");
     String s  = arr.get(i);
     

   • Based on your answer to (a), explain briefly in your own words why using generics is advantageous.

Programming assignment