CS231 lecture notes, Fall 1999
Week 7, Wednesday

GONNA BE DRACONIAN ABOUT THE ASSIGNMENT ON FRIDAY!

Bring two copies of the homework: one to hand in,
one to have in front of you while we discuss.

Queueness
---------

Like a stack, queue can contain any object.

Order of removal is order of insertion (no priorities, no comparability
requirement)

stack is LIFO,  queue is FIFO

Applications of queues

1) buffer between fast CPU and slow devices

   Example: send something to the printer and then go do other things

2) buffer between fast network and slow

   Example: fireline with and without storage

3) simulation of real-world queues... Queueing theory

   Good results, like one-line versus many, on-ramp metering,
   feedback queueing in operating systems.

   Evil mind games like making us walk farther in airports,
   or lines at Disney World.


Implementations
---------------

Stack:

	Linked list... nice because adding to the beginning
	and removing from the beginning are easy

	Array... use a pointer to top of Stack (next empty one
	or last filled one)?  Copy when full.

	Vector?

Queue:

	Linked List: not as much fun, unless you keep a tail
	pointer!

	Array: Circular buffer!
   



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 link;

  StackNode (Object item, StackNode link) {
    this.item = item;
    this.link = link;
  }
}

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 = (Object) topNode.item;
    topNode = topNode.link;
    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.