2.Container Class Design Issues§

Storing a record vs. Storing a reference to a record
Homogeneity: Allow different record types? Check and block?
Deletion: What happens to the record?

Stacks

LIFO: Last In, First Out.

Restricted form of list: Insert and remove only at front of list.

Notation:

Insert: PUSH
Remove: POP
The accessible element is called TOP.

Stack ADT

public interface Stack<E> { // Stack class ADT
  // Reinitialize the stack.
  public void clear();

  // Push "it" onto the top of the stack
  public boolean push(E it);

  // Remove and return the element at the top of the stack
  public E pop();

  // Return a copy of the top element
  public E topValue();

  // Return the number of elements in the stack
  public int length();
  
  // Tell if the stack is empty or not
  public boolean isEmpty();
}

Array-Based Stack (1)

Issues:

Which end is the top?
Where does “top” point to?
What are the costs of the operations?

Array-Based Stack (2)

class AStack<E> implements Stack<E> {
  private E stackArray[];         // Array holding stack
  private static final int DEFAULT_SIZE = 10;
  private int maxSize;            // Maximum size of stack
  private int top;                // First free position at top

  // Constructors
  @SuppressWarnings("unchecked") // Generic array allocation
  AStack(int size) {
    maxSize = size;
    top = 0;
    stackArray = (E[])new Object[size]; // Create stackArray
  }
  AStack() { this(DEFAULT_SIZE); }

Linked Stack

// Linked stack implementation
class LStack<E> implements Stack<E> {
  private Link<E> top;            // Pointer to first element
  private int size;               // Number of elements

  // Constructors
  LStack() { top = null; size = 0; }
  LStack(int size) { top = null; size = 0; }