Lab 11: Lists, Stacks and ADT's

Task 0: Prepare for lab

Download the following zip file: lab11.zip

Unzip this archive, and you should find a folder named lab11, and within it the files you will need for this lab.

Task 0: Understanding the ADT and Java Interfaces

Given the following List interface:

public interface List {
    Object getItem(int i);
    boolean addItem(Object item, int i);
    Object removeItem(int i);
    int length();
    boolean isFull();
}

We’ve examined two classes that implement it:

• ArrayList, which uses an array to store the items
• LLList, which uses a linked list.

Consider the following lines of client code:

List vals1 = new ArrayList(10);

vals1.addItem("hello", 0);
vals1.addItem("world!", 0);
vals1.addItem("how", 1);
vals1.addItem("are", 1);
vals1.addItem("you?", 2);

System.out.println(vals1);

1. Why can we declare vals1 to be of type List when the object that we’re assigning to it is of type ArrayList? What is the benefit of doing this?

2. Review ListClient.java from prior week’s lab.

Task 1: Analyzing the Binary Search Method on an ArrayList vs. LLList

If we knew that the item in our list were sorted, we could use the binary search approach to finding a specific element. Here is pseudocode for an iterative implementation of that algorithm:

bin_search(List list, Object item) {
    min = 0
    max = list.length()

    while (min < max) {
        mid = (min + max) / 2
        midItem = list.getItem(mid)
        if (midItem is equal to item) {
            return true
        } else if (midItem is less than item) {
            max = mid - 1    // item must come before position mid
        } else {
            min = mid + 1    // item must come after position mid
        }
    }

    return false
}

1. What is the worst-case time efficiency of this bin_search method if list referenced an instance of the ArrayList class?

2. What is the worst-case time efficiency of this bin_search method if our list referenced an instance of the LLList class?

Task 2: Understand Stacks

1. Given the following stack, depicted here from top to bottom:

   +     +
   | "f" |  top
   | "e" |
   | "a" |
   | "c" |
   | "b" |
   +-----+
   

   Show what the stack look like after each of the following sequence of pushes and pops:

   pop()
   push("x")
   push("w")
   str = pop()
   pop()
   push("z")
   push(str)
   

2. Begin by understanding the two implementations of the Stack interface, namely ArrayStack and LLStack. Create a client program called StackClient with a main() method in which you do the following:

   1. Construct a stack object (either an ArrayStack or an LLStack) and assign it to a variable.

      Hint: Don’t forget that our stack implementations are generic classes, so you’ll need to specify the type of item when you declare the variable and when you construct the stack object. For example:

      Stack<...> s1 = new ArrayStack<...>();
      or 
      Stack<...> s1 = new LLStack<...>();
      

      where you replace the ... with the appropriate data type. You can create a reference to either stack implementation and the methods will produce the same results.

   2. Perform a series of pushes to create the stack shown at the beginning of this task. Make sure that you push them in the appropriate order!

   3. Print the stack, which should show you the items from top to bottom as follows:

      {f, e, a, c, b}
      

      If you don’t see this result, modify your calls to push() as needed.

   4. Perform the above sequence of modifications to the stack. When you assign the result of the second call to pop() to a variable, you will not need a type cast. Why not?

   5. Reprint the stack after all of those operations have been performed. Doing so should provide the following output:

      {w, z, e, a, c, b}
      

3. Could you add code to your client program that removes the "z" without first removing another item? Why or why not?