CSC161 2010F, Class 51: Designing More ADTs: Stacks and Queues

Overview:
* Questions on Exam 3.
* Stacks.
* Queues.
* Generalizing: Linear Structures.
* Other Policies.

Admin:
* Does anyone want to be on the "CS Students" mailing list?
* How I know I'm in the wrong business: The rumored Google/Groupon deal.
* EC for Cool convo tomorrow.
* EC for Cool CS Extra tomorrow.
* EC for Jazz / Latin American Ensemble 8 p.m. on Friday
* EC for Collegium Compline Service at some random church

Questions on Exam 3:

* Are you sure the code works on problem 3?
  Yes
* How does one get a loop using the struct list datatype?s
  * You can't!  That's why we wrote it.
  * You get it with the struct node datatype
    struct node *a = cons("a", NULL);
    struct node *b = cons("b", a);
    a.set_cdr(b);
* How do I tell how big a loop is?
  * Suppose np is a node in a loop
    struct node *tmp = np;
    int size = 1;
    while ((tmp = tmp->next) != np);
      ++size;

Stacks!
* Basically: The most recent thing you've added is the first thing you
  get.
* Useful for: 
  * Implementing HP calculators.
  * Implementing function calls in languages that are not fortran
  * Really deranged to do lists
* Key operations
  struct stack *new_stack(capacity?): create a new stack 
  int push(struct stack *stack, char *thingtoadd): add something to the stack
    // Success or failure (or perhaps size)
  char *pop (struct stack *stack): grab something from the top of the stack
  char *top (struct stack *stack); Grab something from the top of the stack, but don't remove it
  int size (struct stack *)

struct stack {
  char *contents[STACK_SIZE];
  int top;
}

/**
 * Procedure:
 *   push
 * Parameters:
 *   stack, a stack created by new_stack
 *   stuff, a non-null string
 * Purpose:
 *   Add a value to the top of the stack.
 * Produces:
 *   succeeded, an integer that indicates whether the operation succeeded
 * Preconditions:
 *   There is capacity in the stack to add another element.
 * Postconditions:
 *   Size of the stack has increased by 1.
 *   top(stack) is stuff.
 */
int
push (struct stack *stack, char *stuff)
{
  if (top >= STACK_SIZE)
    return 0;
  contents[top] = stuff;
  ++top;
  return 1;
} // push

So, we may need an "is_full" procedure in our stacks.

Stacks are great, but don't provide a sufficient model.

Queues: A Line (as in at a grocery store)

Operations
* new_queue (capacity?): Create a new queue
* enqueue: add to the back of the queue
* dequeue: remove from from the front of the queue
* size
* is_empty
* is_full

Can we implement queues with linked lists?
* Sure, keep track of the front and the back
  * Enqueue is append
  * Dequue is "grab head"; q->head = q->head->next;  cleanup

Can we implement queues with arrays?

Yes!

struct queue {
  char *contents[QUEUE_CAPACITY];
  int front;
  int back;
  int size;
}

struct queue *
new_queue() {
  struct queue *sure = malloc (sizeof (struct queue));
  queue->front = 0;
  queue->back = 0;
  queue->size = 0;
}

int 
enqueue(struct queue *q, char *str)
{
  if (q->size > QUEUE_CAPACITY)
    return 0;
  q->contents[q->back] = str;
  q->back = (q->back + 1) % QUEUE_CAPACITY;
  ++(q->size);
  return 1;
} // enqueue

char *
dequeue(struct queue *q)
{
  if (q->size == 0)
    return NULL;
  char *result = q->contents[q->front];
  q->front = (q->front + 1) % QUEUE_CAPACITY;
  --(q->size);
} // dequeue



---

Same basic operations:
* add,
* remove
* empty
* full
* size
* peek

Differ only in what they are called and interpretation of remove

* The "linear structure" is the ADT for collections that have those
  basic operations.
* A policy determines what you remove
  FIFO - Queue
  LIFO - Stack
  Priority - Priority Queue
  Arbitrary - Random Collection