For this lab, you will write a class called LastN which is a collection which implements the following API:

Function	Signature	Description
constructor	LastN(int nToKeep)	constructor
keep	void keep(String s)	adds a String to the list
getLastN	String[] getLastN()	returns the last nToKeep items passed to keep()

LastN will keep track of the most recent nToKeep Strings passed to the keep() function. This could be used, for example, to keep track of the last few lines of a file by passing lines one at a time to keep(). At any time, the function getLastN may be called to get an array containing the last nToKeep Strings as an array, with the least recent String in index 0.

The following sequence of calls:

 LastN ln = new LastN(3); ln.keep("one"); ln.keep("two"); ln.keep("three"); ln.keep("four"); ln.keep("five"); String[] last = ln.getLastN(); 

would result in last being this array of 3 Strings:

 last[0] = "three"; last[1] = "four"; last[2] = "five"; 

IMPORTANT DETAIL: Your implementation of LastN may not store more than nToKeep Strings. You CANNOT store every String passed to keep(). Points will be deducted if you use more memory than necessary. Assume that a LastN object may be asked to keep only the last 10 of a million strings.

Since we're working on section 1.3 of the text, you may assume that you need to use either a stack, queue, or bag to do this. The authors' implementation of all three of these collection types will be provided. You do NOT need to implement your own stack, queue, or bag ADT; just use the one provided.

Note that LastN is not a generic API; it stores String objects only. However, you will have to supply the proper type parameter to whichever of Stack, Queue, or Bag that you choose to use here.

Your getLastN() function may not remove items from the collection. For example, if the code above was then followed by

 ln.keep("six"); last = ln.getLastN(); 

this would leave the following data in last:

 last[0] = "four"; last[0] = "five"; last[0] = "six"; 

It is possible for getLastN() to be called before nToKeep calls to keep() have been made. In that case, the returned array should only return as many items as there are in the collection.