A StringBag Abstract Data Type (ADT) is a simple collection of strings ordered by time of entry (not alphabetical). Like a stack, the last string entered goes on the top. The strings are not alphabetized in the bag. Client programs can insert strings into the bag, check its size, clear it, use its toString, remove the top string, and check to see if it is full. We want to keep things simple, so we allow duplicates. There is no provision to see if a given string is already in the bag. Further, the client can only remove the string on top, like a stack. The StringBag is a LIFO collection. See the StringBagInterface, below. Create a class to implement the interface using a private linked list to hold the inserted strings. Note: if the list is not empty, then the following code will remove the first item in a linked list: head = head.getLink(); Design a test driver that shows that your StringBag.java class works correctly.

public interface StringBagInterface {

void insert(String element);

// Precondition: This StringBag is not full.

// Places element into this StringBag.

boolean isFull();

// Returns true if this StringBag is full, otherwise returns false.

boolean isEmpty();

// Returns true if this StringBag contains no strings.

int size();

// Returns the number of Strings in this StringBag.

String remove();

// Precondition: the Bag is not empty

// Removes the string at the top of the bag and returns it.

void clear();

// Makes this StringBag empty. String getName();

// Returns the name of this StringBag

String toString();

// Returns a nicely formatted string representing the

// name of the bag and all of its contents.

}