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