85bb.md

Back to questions

85bb: String stack iterators

An iterator is an object that can be used to navigate through a collection, inspecting each element of the collection. For example, if we wish to display every element of a set of strings, we can write the following:

void showSet(Set<String> s) {
  Iterator<String> it = s.iterator();
  while(it.hasNext()) {
    String x = it.next();
    System.out.println(x);
  }
}

We are more used to writing the following more convenient version:

void showSet(Set<String> s) {
  for(String x : s) {
    System.out.println(x);
  }
}

but this is simply shorthand for the version that uses an iterator.

In this question, you will provide iterator facilities for your StringStack interface and implementing classes StringStackArray and StringStackList of question 1486.

Step 1

Create an interface, StringStackIterator, that offers the following methods:

public boolean hasNext();

public String next();

Step 2

Add a new method to the StringStack interface:

public StringStackIterator iterator();

The idea is that, given an instance of type StringStack, it should be possible to retrieve a StringStackIterator from the StringStack, and then use this iterator to visit each element of the stack, from the top down.

You should now find that StringStackArray and StringStackList no longer compile. This is because they do not implement the iterator method.

Step 3

In order to fix this, you need to create two new classes: StringStackArrayIterator, and StringStackListIterator. Both classes should implement the StringStackIterator interface. Writing these classes is a little tricky, but once you have them, implementing the iterator method in StringStackArray is straightforward: simply return a new StringStackArrayIterator; implementing iterator in StringStackList is similarly straightforward.

So, how should you implement the iterator classes? There are two choices:

1. Create a fresh class for each of StringStackArrayIterator and StringStackListIterator. Let us consider the StringStackArrayIterator case.

   StringStackArrayIterator should have a field of type String[]: a reference to the contents of the stack. In addition, this class should have a field of type int that refers to the stack element that the iterator is currently pointing to. This should be initialised to the top of the stack. This solution is OK, but it requires the internal details of a StringStackArray to be indirectly exposed to the separate StringStackArrayIterator class, since a StringStackArrayIterator is constructed using the internals of a StringStackArray. More importantly, this setup allows clients to construct instances of StringStackArrayIterator independently of any actual StringStackArray. This doesn't really make sense. The extent of this problem can be limited by making the StringStackArrayIterator only package visible.

2. Use inner classes. Again, let us discuss the "array" case; the "list" case is similar. You can create a class called StringStackArrayIterator inside StringStackArray. This class can be declared private, meaning that only StringStackArray is aware of its existence. (Recall that standard classes cannot be declared private -- this would make such a class completely useless. However, inner classes can be private, visible only to their enclosing classes; there is a compelling case for this, as the iterator example illustrates.) Only an object of type StringStackArray can create a StringStackArrayIterator. Every instance of StringStackArrayIterator implicitly holds a reference to the StringStackArray object that created it, and has direct access to (even private) fields of this object. This direct access allows you to implement the iterator methods without violating encapsulation. Try it!

If you are very confident with Java, try the inner classes approach. If you not so confident, try the first approach using standard classes. Ideally, try both so that you understand the differences.

Step 4

Once you have implemented your iterators, implement toString in each of StringStackArray and StringStackIterator, so that the contents of the stack is represented as a string, with elements separated by commas. You can use your StringStackIterator interface to iterate through the stack in order to do this.

You should find that toString looks exactly the same in both classes!

Step 5

As a result, we can raise the implementation of toString to a more abstract level. Create an abstract class, AbstractStringStack which implements the StringStack interface. Now change StringStackArray and StringStackList so that instead of implementing StringStack they extend AbstractStringStack. Now move the duplicate implementations of toString into a single implementation of toString in AbstractStringStack.

Step 6

Finally, write a Demo class which constructs two stacks, displays them both, uses transferStacks from question 1486 (which you should be able to copy into your new Demo class unchanged) to transfer one stack to the other, then displays them both.

Do you appreciate the power of abstract classes and interfaces here? We are able to implement the algorithm behind toString completely independently of the particular stack representation that is being used.

Advanced: anonymous inner classes

Some software engineers argue that it is wasteful to give names to very simple inner classes, such as iterators. Furthermore, if an inner class is supposed to have a single point of creation, we may wish to enforce this. Java supports the definition of anonymous classes. This is where a nameless class is specified, and an instance of this class is immediately created. Because the class has no name, it cannot be instantiated from elsewhere. If you are really on top of things, then search online or in books for a tutorial on creating anonymous classes in Java, and rewrite your StringStackArray and StringStackList classes so that the inner "iterator" classes are anonymous.