CS231 lecture notes, Fall 1998
Week 9, Wednesday

Quiz 6 on tranforming object methods into class methods and vice versa.

Review of syntax for constructors (using Stack as example)

Global/class variables usually initialized at declaration

Instance variables initialized in constructor.

-----

Set the way-back machine... let's talk about the implementation of
stacks and queues.  Read notes14.txt and Standish 6.6 and 6.8.

Also look at http://rocky.colby.edu/cs231/code/StackArray/
and http://rocky.colby.edu/cs231/code/StackList/

Let's see... I haven't provided implementations of Queues.
Wouldn't that make an excellent exam question?!?

-----

1) Implementation of stacks

   a) using arrays
   b) using lists (this time the lists are implemented internally)


Most of this is almost identical to the array implementation
of PriorityQueue:

public class Stack {
  private int count;
  private int capacity;
  private int capacityIncrement;
  private Object[] itemArray;

  public Stack () {
    count = 0;
    capacity = 10;
    capacityIncrement = 10;
    itemArray = new Object[capacity];
  }

  public boolean empty () {
    return (count == 0);
  }

  public void push (Object obj) {
    if (count == capacity) {
      capacity += capacityIncrement;
      capacityIncrement *= 2;
      Object[] tempArray = new Object[capacity];
      for (int i=0; i<count;i++) {
        tempArray[i] = itemArray[i];
      }
      itemArray = tempArray;
    }
    itemArray[count] = obj;
    count++;
  }

The first difference is that we are dealing with Objects instead
of PQItems, but other than that the only interesting difference is
in pop:

  public Object pop () {
    if (count == 0) return null;
    count--;
    return itemArray[count];
  }

We can just pull the top item off the stack -- no need to search
for the one with the highest key.  Based on pop, peek is a no-
brainer:

  public Object peek () {
    if (count == 0) return null;
    return itemArray[count-1];
  }

For the list implementation, we need a new kind of list node that
has an Object as cargo:

public class StackNode {
  Object item;
  StackNode next;

  StackNode (Object item_, StackNode next_) {
    item = item_;
    next = next_;
  }
}

The instance variable here is called topNode and it just
point to the element on the top of the stack:

public class Stack {
  StackNode topNode;

  public Stack () {
    topNode = null;
  }

The constructor creates an empty stack by initializing the
instance varaible to null.  So naturally we can test for an
empty stack as so...

  public boolean empty () {
    return (topNode == null);
  }

Now, for putting things on and taking things off the list,
we could have used the list methods we developed at the beginning
of the semester, but it turns out that the list operations we
want to perform are so simple that we can pretty much go ahead
and do them ourselves.

push is the same as addNewFirstNode:

  public void push (Object obj) {
    topNode = new StackNode (obj, topNode);
  }

pop is the same as removeFirstNode, except that we have to play
some games with a temporary variable:

  public Object pop () {
    if (topNode == null) return null;
    Object ret = topNode.item;
    topNode = topNode.next;
    return ret;
  }

peek is a no-brainer.

  public Object peek () {
    if (topNode == null) return null;
    return topNode.item;
  }



Implementation of queues
------------------------

List Implementation

     insert new things at the end, take from the beginning

     (adding takes constant time, removing takes time proportional
      to the number of elements in the queue)

      Alternative: maintain head and tail pointers

      Normal cases:

      a) insert at end, update tail
      b) remove from beginning, update head

      Have to deal with special cases:

      a) inserting an elt in an empty list (head = tail = new)
      b) removing the last elt from a list (head = tail = null)

      Does this approach save work?  Roughly doubles the cost
      of inserting/removing.

      Assume a normal operation costs 1 and a two-headed operation
      costs 2.  Also assume that traversing a list costs n, where
      n is the length of the list.
      
      What is the cost of 10 insertions followed by 10 deletions?
      What about 20 alternating insertions/deletions?

Array implementation

      Insert things at the end, remove from the beginning.

      Use two indices to indicate next available space and front
      of the queue.

      Normal case

      1) insert puts the new value in the array and increments
         tail index.

      2) remove takes an element out of the array and increments
         the head index.

      How do we know if the queue is empty?  If head == tail.

      What do we do when the tail pointer goes past the end of the
      array?

      a) allocate more space
      b) wrap around, using modular arithmetic

      head = (head + 1) % n;
      tail = (tail + 1) % n;

      This trick is called a circular buffer.

      But it is still possible for the buffer to fill.

      How can we tell?  If the tail wraps around and catches
      up with the head.   if (tail + 1) % n == head, were full.

      Or just keep track of the count and the capacity (like the book).

      Expanding the buffer is a little tricky since the queue is
      sort of in two pieces.