CS 201: Data Structures (Winter 2018)
Lab2: 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?
push
,pop
,peek
,isEmpty
, andclear
) 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 forpop
andclear
. - 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
toCarlStack
to use the testing code on a stack implementation that supposedly works. This is why I includedCarlStack.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 aNode
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 efficientpush
and pop
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 theRecursiveStack.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 aDeque
was included with the downloaded files for this lab. - Start with the
push
,pop
, andpeek
you already have, renaming them toaddFirst
,removeFirst
, andgetFirst
. - Write
addLast
to add to the back. What instance variable can you add to makeaddLast
easier? - Write
removeLast
andgetLast
. - 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.