1486.md

Back to questions

Solution to 1486: String stack

See code at solutions/code/tutorialquestions/question1486

The StringStackArray class implementation is straightforward: see the sample solution.

The StringStackList class implementation is even more straightforward; perhaps so straightforward you may have worried that you were missing something! Look at the sample solution. The only slightly tricky part is implementing pop() so that the last element of the list is removed.

You will see in the sample solution that StringStackArray and StringStackList both implement the StringStack interface. Notice that the interface methods are declared public. This is not actually necessary, as they are implicitly public. However, it does no harm. The implementations of these methods in StringStackArray and StringStackList must be declared public regardless.

See how simple the implementation of transferStacks in Demo.java is:

public static void transferStacks(StringStack dst, StringStack src) {
  while(!src.isEmpty()) {
    dst.push(src.pop());
  }
}

Because we have a StringStack interface, we can write this method purely in terms of the interface type, regardless of the classes that provide actual types for src and dst.

The power of this is illustrated in main, where we can write:

StringStack first = new StringStackArray();
StringStack second = new StringStackList();
...
transferStacks(second, first);

Polymorphism here allows us to treat a StringStackArray and a StringStackList uniformly as objects of type StringStack when we call transferStacks. Note that it would also work if we wrote:

StringStackArray first = new StringStackArray();
StringStackList second = new StringStackList();
...
transferStacks(second, first);

In this case, the compiler upcasts first and second to StringStack when transferStacks is called.

Finally, if we want to change StringStackList to use a LinkedList instead of an ArrayList, we need only change:

elements = new ArrayList<String>();

to

elements = new LinkedList<String>();

in the constructor of StringStackList.