Extra Credit

Stacks

Objective:

Write a generic class that creates an instance of a stack data structure using a linked list (NOT an array).  This is a last in first out (LIFO) data structure.  This means information put into it at the beginning can only be accessed at the end.  Here’s a picture

Background

• For generics, read the following (follow the Next links as you read): https://docs.oracle.com/javase/tutorial/java/generics/index.html
• It is possible to create a class inside anouther class -- an interior class.
• You should also look up linked lists. The idea is simple but the thing that is subtly different is the "nodes" in a linked list have a link (reference) to the next node in the list. We haven't seen a class that does this sort of thing; we've made classes that reference other classes but not ones that reference others of the same type.

Rules

• Your code must mostly work.
• Code that does not compile will not be graded

Stack, which is a generic Stack

• It must work with any type
• Write an interior class called StackNode
  • This means it is a private class within Stack
  • Attributes of this interior class will be
    • Data – this is the data of the generic type
    • Next – a link (reference) to the next node
  • Create the following constructor for this interior type
    • A constructor where it has parameters for the data and the next link
• Attributes of this Generic Stack class are
  • Head – an instance of the StackNode that always keeps track of the top of the list
  • Create the following constructors
    • Default – sets both head and current to null
• Create the following Methods
  • push – this takes in generic data type and then creates a new instance of the stack node and then pushes it on as the new head
  • pop – this returns the generic type value of the current head and then removes it from the list by resetting the head to the head’s next link
  • peek – this returns the value at the top of the stack but does not remove the item from the head of the list
  • canPop – this returns true if the head is not null
  • printStack – this iterates through the stack printing the data values of each item in the stack

Demo/Driver Code

Finally write a class that demonstrates that all the stack functionality works. Make sure to demonstrate both Stack and generic traits of your code.