CS 112 Lab 4

Java Generics and Generics implementing an Interface

We will assume that you have heard or read the presentation on Generics and Generics implementing Interfaces: PDF

Problem One

Download the vanilla-flavored implementation of a Stack using Linked Lists: Stack.java.

Rewrite this to use Java generics, so that it can be used to implement stacks for any possible types. Here is a template for your solution: GenericStack.java.

Submit this as GenericStack.java in the next homework.

Problem Two

Now you must rewrite the generic stack code so that it implements a generic priority queue, which can work with any class which implements the Comparable interface.

Note that if you take the stack code, implemented as a linked list, and you rewrite the insert (or push) method so that it inserts the new element so that it preserves the ordering of the list, from the largest element at the top, and the smallest elements at the bottom, then it effectively implements a priority queue (a MaxQueue). To see how to do this, take a look at the method insertInOrder(...) in the Notes on recursion and linked lists.

Here is the template for your solution: GenericPQueue.java.

Submit this as GenericPQueue.java in the next homework.