Stacks, Queues, Binary Trees
Note: All the programs mentioned in this lecture are in:/home/cs352/SUMMER02/lecture14progs/
- Stacks - Insertion, deletion only occur at the top(push, pop) LIFO(Last In First Out) - Standard stack operations(implemented as a linear linked list): int isempty(st_ptr p); data_type top(st_ptr p); void pop(st_ptr *p, data_type *d); void push(st_ptr *p, data_type *d); where the stack holds data of type data_type. See stack.h, stackopers.c, reverse.c Also see calculator.c(includes just the evaluate, how to do construct, think of the prev. calculator program we wrote.) - Queues - Has a "front" and a "rear". - Insertion at the rear, deletion at the front. FIFO(First In First Out) - Standard queue operations(implemented as a linear linked list): int isempty(queue q); data_type first(queue q); void dequeue(queue *q, data_type *d); void enqueue(queue *q, data_type d); where the queue holds data of type data_type. see queue.h, queueopers.c Also see scheduler.c