An internal iterator for a bag is a collection of methods that allows a programmer to step through the elements of a bag one at a time.

For example, we might have an internal iterator consisting of four methods: start, advance, isCurrent, and getCurrent. The start method initializes the internal iterator; the isCurrent method is a boolean method that tells whether the iterator has a specified current element that can be retrieved with the getCurrent method; and the advance method moves the iterator to its next element.

For this project, add an internal iterator to the bag from Section 9.5. The implementation technique is to use a private instance variable called s. The instance variable s is a stack of references to nodes.

Each of the elements in the stack refers to a node whose element has not yet been processed by the internal iterator. The current element of the internal iterator is always in the node at the top of the stack.

The pseudocode for the internal iterator methods is given here:

The start method: Clear the stack. For an empty tree, there is no more work. For a non-empty tree, do an in-order traversal of the tree’s nodes, pushing a reference to each node onto the stack.

The isCurrent method: Return true if the stack is nonempty.

The getCurrent method: Check the precondition (the stack must be non-empty). Then peek at the top node on the stack (without removing it). Return the data element from this node.

The advance method: Check the precondition (the stack must be non-empty). Then pop the top node off the stack.

Changing the bag by adding or removing elements should invalidate the internal iterator (by clearing the stack).

When the internal iterator is started, use an inorder traversal to push node references onto the stack. As you pop the stack, these references come off in reverse order so that the iterator will advance through the elements from largest to smallest. If you prefer a smallest-to-largest order, you could use a queue instead of a stack.