Implementing a Simplified Generic Stack – Generics

11.8 Implementing a Simplified Generic Stack

The Node<E> class from Example 11.2, p. 568, can be used to implement linked data structures. Example 11.10 is an implementation of a simplified generic stack using the Node<E> class. The emphasis is not on how to develop a full-blown, industrial-strength implementation, but on how to present a simple example in the context of this book in order to become familiar with code that utilizes generics. For thread-safety issues concerning a stack, see §22.4, p. 1396.

The class MyStack<E> implements the interface IStack<E> shown in Example 11.10, and uses the class Node<E> from Example 11.2. The class NodeIterator<E> in Example 11.10 provides an iterator to iterate over linked nodes. The class MyStack<E> is Iterable<E>, meaning we can use the for(:) loop to iterate over a stack of this class (see (9) and (12)). It is instructive to study the code to see how type parameters are used in various contexts, how the iterator is implemented, and how we can use the for(:) loop to iterate over a stack. For details on the Iterable<E> and Iterator<E> interfaces, see §15.2, p. 791.

Example 11.10 Implementing a Simplified Generic Stack

Click here to view code image

/** Interface of a generic stack */
public interface IStack<E> extends Iterable<E> {
  void push(E element);           // Add the element to the top of the stack
  E pop();                        // Remove the element at the top of the stack.
  E peek();                       // Get the element at the top of the stack.
  int size();                     // No. of elements on the stack.
  boolean isEmpty();              // Determine if the stack is empty.
  boolean isMember(E element);    // Determine if the element is in the stack.
  E[] toArray(E[] toArray);       // Copy elements from stack to array
  @Override
  String toString();              // Return suitable text representation of
                                  // elements on the stack: (e1, e2, …, en)
}

Click here to view code image

import java.util.Iterator;
import java.util.NoSuchElementException;
/** Simplified implementation of a generic stack */
public class MyStack<E> implements IStack<E> {                     // (1)
  // Top of stack.
  private Node<E> tos;                                             // (2)
  // Size of stack
  private int numOfElements;                                       // (3)
  @Override public boolean isEmpty() { return tos == null; }       // (4)
  @Override public int size()        { return numOfElements; }     // (5)
  @Override public void push(E element) {                          // (6)
    tos = new Node<>(element, tos);
    ++numOfElements;
  }
@Override public E pop() {                                       // (7)
    if (!isEmpty()) {
      E data = tos.getData();
      tos = tos.getNext();
      –numOfElements;
      return data;
    }
    throw new NoSuchElementException(“No elements.”);
  }
  @Override public E peek()  {                                     // (8)
    if (!isEmpty()) return tos.getData();
    throw new NoSuchElementException(“No elements.”);
  }
  // Membership
  @Override public boolean isMember(E element) {                   // (9)
    for (E data : this)
      if (data.equals(element))
        return true;       // Found.
    return false;          // Not found.
  }
  // Get iterator.
  @Override public Iterator<E> iterator() {                        // (10)
    return new NodeIterator<>(this.tos);
  }
  // Copy to array as many elements as possible.
  @Override public E[] toArray(E[] toArray) {                      // (11)
    Node<E> thisNode = tos;
    for (int i = 0; thisNode != null && i < toArray.length; i++) {
      toArray[i] = thisNode.getData();
      thisNode = thisNode.getNext();
    }
    return toArray;
  }
  // Text representation of stack: (e1, e2, …, en).
  @Override public String toString() {                             // (12)
    StringBuilder rep = new StringBuilder(“(“);
    for (E data : this) {
      rep.append(data + “, “);
    }
    if (!isEmpty()) {
      int len = rep.length();
      rep.delete(len – 2, len);                   // Delete the last “, “.
    }
    rep.append(“)”);
    return rep.toString();
  }
}

Click here to view code image

import java.util.Iterator;
/** Iterator for nodes */
public class NodeIterator<E> implements Iterator<E> {
  private Node<E> thisNode;
  public NodeIterator(Node<E> first) { thisNode = first;  }
  @Override public boolean hasNext() { return thisNode != null; }
  @Override public E next() {
    E data = thisNode.getData();
    thisNode = thisNode.getNext();
    return data;
  }
  @Override public void remove() { throw new UnsupportedOperationException(); }
}