Lab 10: Stacks

This lab will consist of two parts. The first part focuses on implementing a node-based stack. The second part uses your stack and the queue from Lab 9 to convert a recusive method implementation to an iterative implemenation.

To begin this lab, you should also review your notes and lecture material for information about linked lists and stacks.

Part I

1. Create a package lab.util or re-use the package from Lab 9.
2. Add the classes Node, NodeIterator, and Stack to the package lab.util. You will already have the node classes if you are re-using your package from Lab 9. APIs can be found here.
3. Complete the implementation of the Stack class:
   1. Your stack implementation must use a node-based linked sequence to represent the stack. The sequence is very similar to a singly linked list but does not need to provide all of the functionality of a linked list. You must use the provided Node class to implement the linked sequence. All of the required fields are already provided for you in the starter code.
   2. The constructor should create an empty stack. An empty stack has no top node, and its size is zero.
   3. The push method should add a new element to the top of the stack, increasing the size of stack by one. It does so by adding a new node to the beginning of the sequence of nodes.
   4. The pop method should remove and return the element at the top of the stack, decreasing the size of the stack by one. It does so by removing the node at the front of the sequence of nodes.
   5. The peek method should return the element at the top of the stack without removing it. It does so by returning the element stored in the node at the front of the sequence of nodes.
   6. The size method should return the size of the stack.
   7. The isEmpty method should return true if the stack is empty and false otherwise.
   8. The equals method should return true if both stacks contain the same sequence of elements (i.e., both stacks have the same size, and the elements in this stack are equal to the elements in the other stack when compared in iteration order). You should use the NodeIterator class to iterate over the elements of both stacks.
4. Test your stack using the JUnit test StackTest.

Part II

Consider the following recursive implementation for computing the Fibonacci number F(n):

01  public class Fibonacci {
02    private static Map<Integer, BigInteger> cache = new HashMap<Integer, BigInteger>();
03
04    public static BigInteger fib(int n) {
05      BigInteger sum = null;
06      if (n == 0) {
07        sum = BigInteger.ZERO;
08      }
09      else if (n == 1) {
10        sum = BigInteger.ONE;
11      }
12      else if (Fibonacci.cache.containsKey(n)) {
13        sum = cache.get(n); 
14      }
15      else {
16        BigInteger fMinus1 = Fibonacci.fib(n - 1);
17        BigInteger fMinus2 = Fibonacci.fib(n - 2);
18        sum = fMinus1.add(fMinus2);
19        Fibonacci.cache.put(n, sum);
20      }
21      return sum;
22    }
23  }

The implementation above uses a technique called memoization; it stores the value of F(n) in the map named cache so that the value of F(n) can be reused (instead of recursively recomputed) when some larger Fibonacci number is computed. For example, invoking fib(5) causes the values of F(5), F(4), F(3), and F(2) to be stored in cache. If fib(6) is then invoked, the values of F(5) and F(4) can be retrieved from the cache to efficiently compute the value of F(6). It is possible to show that the method above has complexity O(n) in contrast to the naive implementation that does not use memoization which has complexity O(2ⁿ).

One problem with the above implementation, and with recursive implementations in general, is that there is a limit to the amount of memory that can be used to store the active method invocations, and this limit is much smaller than the total amount of memory available. For example, on my computer I can successfully invoke fib(5411), but invoking fib(5412) causes a StackOverflowError exception to be thrown. To understand why a StackOverflowError exception is thrown, consider the following illustration of what occurs when fib(3) is invoked:

1. An invocation of fib begins execution to compute F(3). A block of memory called a frame that contains storage for the method parameters, references to static variables, local variables, and the return value is allocated from a part of memory called the stack (not to be confused with the data structure you implemented in Part I that is also called a stack). Because the frame is allocated from the stack, the frame is often called a stack frame.
2. To compute F(3), an invocation of fib begins execution to compute F(2). Another block of memory is allocated for the stack frame for F(2).
3. To compute F(2), an invocation of fib begins execution to compute F(1). Another block of memory is allocated for the stack frame for F(1).
4. F(1) is a base case so the value of 1 can be returned to the calling method F(2) and the memory associated with the stack frame can be freed from use (or popped from the top of the stack).
5. The method invocation that is computing F(2) (whose frame is now on the top of the stack) receives the return value of F(1), and can resume execution.
6. To continue computing F(2), an invocation of fib begins execution to compute F(0). Another block of memory is allocated for the stack frame for F(0).
7. F(0) is a base case so the value of 0 can be returned to the calling method F(2) and the memory associated with the stack frame can be freed from use (or popped from the top of the stack).
8. The method invocation that is computing F(2) (whose frame is now on the top of the stack) receives the return value of F(0), and can resume execution. It computes the sum F(1) + F(0) and caches the result.
9. The method invocation that is computing F(2) is finished execution so the value of 1 can be returned to the calling method F(3) and the memory associated with the stack frame can be freed from use (or popped from the top of the stack).
10. The method invocation that is computing F(3) (whose frame is now on the top of the stack) receives the return value of F(2), and can resume execution.
11. To continue computing F(3), an invocation of fib begins execution to compute F(1). Another block of memory is allocated for the stack frame for F(1).
12. F(1) is a base case so the value of 1 can be returned to the calling method F(3) and the memory associated with the stack frame can be freed from use (or popped from the top of the stack).
13. The method invocation that is computing F(3) (whose frame is now on the top of the stack) receives the return value of F(1), and can resume execution. It computes the sum F(2) + F(1) and caches the result.
14. The method invocation that is computing F(3) is finished execution so the value of 2 can be returned to the calling method and the memory associated with the stack frame can be freed from use (or popped from the top of the stack).

Notice that in the picture above, the stack of frames grows because the bottom-most frame (which is trying to compute F(3)) must wait for all of the frames above it to finish executing (to compute F(2) and then F(1)) before it can finish executing. This can become problematic because each stack frame requires enough memory to store:

• the value of the parameter n
• a reference to cache
• the value of the return value result
• the value of the local variable a (used to store F(n - 1))
• the value of the local variable b (used to store F(n - 2))
• possibly some other book keeping values such as where the return value should be copied to and the address of where the next stack frame is located

When we try to invoke fib(5412) we end up with a stack of 5412 frames, each requiring memory as described above. This turns out to exceed the availabe stack space on my JVM. Stack memory is special because it can be allocated and deallocated very quickly; this is important for efficient method execution. However, this speed is obtained by restricting the amount of stack memory.

A larger pool of memory called the heap is available to your program. Heap memory is used to store objects (i.e., heap memory is allocated whenever the new operator is used). Allocating and deallocating heap memory is slower than for stack memory, but the size of the heap is much larger. If we can convert our recursive implementation into an iterative implementation where we replace stack frames with objects, then we might be able to compute values such as fib(5412) and larger. To do so, we have to mimic how the JVM mimics the stack by creating and managing our own stack of frames.

Implement the class FibonacciStackFrame:

• Add the classes FibonacciCallStack and Fibonacci to the package lab.util.
• The API for FibonacciStackFrame can be found here. Note that the API is unusual in that it describes many implementation details (which are not normally part of an API) to help you complete the implementation.
• A FibonacciStackFrame has the following fields:
  • a static field named cache that corresponds to the cache in the recursive implementation
  • a field named n that stores which Fibonacci number is being computed (the n in F(n)).
  • a field named caller that is a reference to the stack frame that created this stack frame; this field is required so that this stack frame knows where to return the value of F(n)
  • a field named fMinus1 that stores the value of F(n - 1) returned by another stack frame instance; this field corresponds to the variable named fMinus1 in the recursive implementation
  • a field named fMinus2 that stores the value of F(n - 2) returned by another stack frame instance; this field corresponds to the variable named fMinus2 in the recursive implementation
  • a field named sum that stores the value of F(n - 1) + F(n - 2) returned by another stack frame instance; this field corresponds to the variable named sum in the recursive implementation
• The constructor should assign a value to all of the non-static fields. You need to choose an initial value for fMinus1 and fMinus2 that indicates that these values have not been computed yet. You can use null or a negative value.
• The method receiveReturnValue simulates lines 16 and 17 of the recursive method. This method should be called exactly twice by two other FibonacciStackFrame instances (once to set the value of fMinus1 and once to set the value of fMinus2).
• The method returnValueToCaller simulates line 21 of the recursive method. This method should invoke receiveReturnValue on the creator of this stack frame (if the creator is not null) and then pop the call stack.
• The method getSum allows the client that created the initial FibonacciStackFrame instance to retrieve the final value of F(n)
• The method execute simulates lines 6 through 21 of the recursive method. To simulate a recursive invocation, you should create a new FibonacciStackFrame instance and push it onto the call stack.
• Test your stack using the JUnit test FibonacciStackFrameTest.
• Use the method fib2 in the Fibonacci class to compute the value of F(10000).

Submission instructions

• Submit your classes before Friday April 17, 4pm. To submit, log into a computer of the Prism lab (clips showing how to log in from home and transfer files can be found here).
• Transfer your Java classes to your EECS account (if they are not already there).
• Create a file named group.txt in the directory which contains the lab directory which contains the util directory which in turn contains the Java classes. Do not put the group.txt in the same directory as Java classes. Each line of the file group.txt contains the EECS login name of a member of the group.
• Submit your Java classes: Stack and FibonacciStackFrame. Each class should be submitted separately as follows. Open a terminal and go to the directory that contains the file group.txt. In that directory, run the following command to submit your Stack class.

  submit 1030 lab10 group.txt lab/util/Stack.java
  

  If something fails, you may see something like

  submitted:  group.txt (17 bytes)
  submitted:  Stack.java (5144 bytes)
  All files successfully submitted.
  
  Note: lab/util/Stack.java uses unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.
  Your Stack class compiled successfully.
  Your Stack class passed all the tests.
  Your code contains the following 1 style errors
  /eecs/home/franck/lab/util/Stack.java:3:8: Unused import - java.util.EmptyStackException.
  SUBMITTED FILE Stack HAS BEEN REMOVED.
  PLEASE SUBMIT AGAIN.
  

  Fix your code and submit again. If you successfully submitted your code, you will see something like this

  submitted:  group.txt (17 bytes)
  submitted:  Stack.java (5144 bytes)
  All files successfully submitted.
  
  Note: lab/util/Stack.java uses unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.
  Your Stack class compiled successfully.
  Your Stack class passed all the tests.
  Your code contains no style errors.
  
  Your group.txt file has been successfully validated.
  

• You can check which files you have successfully submitted by opening a terminal and running the following command.

  submit -l 1030 lab10
  

  After submitting your classes, you should see something like this

  The following files have been submitted:
  group.txt.submitted                              17 bytes
  Stack.java.submitted                           5144 bytes
  FibonacciStackFrame.java.submitted             7341 bytes
  

• If you run into problems with submitting your Java classes, please email franck@cse.yorku.ca.