In this project, you will implement a new class called a bag with receipts. This new class is similar to an ordinary bag, but the data consists of strings, and the way that the strings are added and removed is different. Each time a string is added to a bag with receipts, the insert method returns a unique integer called the receipt. Later, when you want to remove a string, you must provide a copy of the receipt as a parameter to the remove method. The remove method removes the item whose receipt has been presented and also returns that item through its return value. You may also have a method that returns a copy of the string without removing it.

Here’s an implementation idea: A bag with receipts can have a private array, like this:

private String[ ] data;

Some locations in this array may contain null, which means that that location is unused. When a new string is added, we will find the first spot that is currently unused and store the new string there. The receipt for the string is the index of the location where the string is stored.