CSc 352: Lecture-14

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