Instructions

You have two parts to this assignment. The parts are related, but different in their implementation. To better understand the assignment itself, it may be helpful to go back through the book, slides, notes, etc. and do implementations of the regular array-based and linked list-based Stack, along with the Stack ADT.

Part I

One widespread use of stacks is to provide the undo operation, familiar to us from many different applications. While support for undo can be implemented with an unbounded stack (one that keeps growing and growing as long as memory permits), many applications provide only limited support for such an undo history. In other words, the stack is fixed-capacity. When such a stack is full, and push is invoked, rather than throwing an exception, a more typical approach is to accept the pushed element at the top, while removing the oldest element from the bottom of the stack to make room. This is known as leaking. Note that this does not mean that the ADT exposes a method to allow removal from the bottom directly. This is only performed when the stack becomes full. For this part, you are to give an implementation of such a LeakyStack abstraction, using some array-based implementation. Note that you must create a Leaky Stack interface, and then use the C++ : operator to implement that interface (using public inheritance) with your LeakyArrayStack implementation. See the Interface specified near the end of the assignment instructions.

Part II

Repeat Part I, but use a singly linked list instead of an array for the actual data storage, and allow for a maximum capacity specified as a parameter to the constructor.

NOTES:

Both the array-based and linked-list based Leaky Stacks should use the same LeakyStackInterface, specified below. Remember this is a LeakyStack ADT. It specifies what the LeakyStack does, not how. So, the interface should not be different in order to provide an implementation. Use public inheritance in both Parts You should write a SinglyLinkedList class first, before trying to do part II o Then, use containment (aggregation or composition, a has-a relationship) to implement the part II

The LeakyStacklnterface The interface for the Leaky Stack is as follows: tifndef LEAKY STACK INTERFACE #define LEAKY STACK INTERFACE template