CS 201: Data Structures (Winter 2017)

Lab03: Implement a generic linked stack

1. Goals

To practice implementing a linked stack and learn to implement a generic interface.

2. Linked Stack

Today you will implement a stack using links. This is a good chance to practice working with linked structures and to ask questions about the linked list homework.

Before you begin coding

• Review the Stack interface.
• Discuss the design of a linked stack with your partner:
  • What instance variables will you need?
  • Where should you put the last item added to the stack?
  Jot down your notes on a sheet of paper. (I often plan on paper before I start coding.) Think through how to store your data to make your operations (push, pop, peek, isEmpty, and clear) as efficient as possible.
• What is the efficiency of the five methods under your plan? If any of them is less efficient than O(1), rethink your design.
• Download starter files and pay attention to these right now:
  • Stack.java: interface which we will implement (recall that Java does not have a built-in stack interface).
  • LinkedStack.java: skeleton file for a linked stack implementation. Compile it now. It has just enough code to allow you to compile everything, although nothing has actually been implemented.
• Some initial tests are provided to you. (You may run LinkedStack now to see most of them fail.) You may make any changes you want to the tests; my tests do not provide good coverage of all the methods, so you might add some tests, especially for pop and clear.
• Sometimes when tests fail, you don't know if your implementation is wrong or the testing code itself is wrong. You may temporarily switch from LinkedStack to CarlStack to use the testing code on a stack implementation that supposedly works. This is why I included CarlStack.class. You do not need it otherwise.
• Generics: Look at the class declaration to see how we can write an implementation of a generic interface that also allows generic arguments. If you're confused by anything you see about generics, this is a great time to ask; you'll be implementing generic classes in future homework.

Start implementing LinkedStack.java

• Write a Node class to store your links. If you're stuck, look back at your notes or worksheet from last class. If you get really stuck, click here to see a Node class.
• Write a constructor for LinkedStack.
• Add code to each method. Once you've implemented a method, compile and run your code to see if it passes the relevant tests. Developing incrementally will be much more effective than writing everything at once and having to fix 23 compiler errors all at once.

3. Array Stack

Once you have your linked stack working, talk with your partner about implementing an array stack (no need to actually implement it). Discuss where newly added items to the stack should go, and how efficient pop and push will be. You should be able to come up with a design that will usually be as efficient as the linked implementation.

4. Recursive Stack

You can think of a stack as having two parts: a top item and a stack containing the rest of the items. Take a look at the RecursiveStack.java demo.

5. Extensions

Note: These are provided as extra practice and challenge. You're not intended to get all the way through them or even necessarily to start them.

• Copy your LinkedStack into a new class: LinkedDeque. This class should be able to add at the front (push for a stack), remove from the front (pop for a stack, remove for a queue), examine the front (peek for a stack, element for a queue), add at the back (add for queue), remove from the back, and examine the back. An interface for a Deque was included with the downloaded files for this lab.
• Start with the push, pop, and peek you already have, renaming them to addFirst, removeFirst, and getFirst.
• Write addLast to add to the back. What instance variable can you add to make addLast easier?
• Write removeLast and getLast.
• Can you make all your operations O(1)? You will likely need to modify your Node class.

This lab modified from one designed by Anna Rafferty.