COSC 2011 Section N
Tuesday, March 13 2001

Once again, this lecture will continue with Abstract Data Types. In particular, focus will be placed on Inspectable Containers, the Tree and Binary Tree ADT. There are various definitions related to Trees however, this material will not be covered! Students are responsible for reviewing the definitions on their own (see pages 228-233 in the first edition and pages 144-149 in the second edition).

Similarly, you are also encouraged to look over the following material which may not necessarily be covered in the lecture depending on time availability (if you have any problems with this material, email me or come see me during office hours!)

Implementing Stacks and Queues with Deques: page 94
Realization of a Deque with a Vector: page 116
Bubble-Sort on a Sequence: pages 134-136

Second Edition

Implementing Stacks and Queues with Deques: page 171-172
Realization of a Deque with a Vector: page 186
Bubble-Sort on a Sequence: pages 211-214

1st edition book:

Pages	Section
149 - 151	5.1.2 - 5.1.3
164 - 165	5.3.2
32-35	2.2
40-41	2.4.3

2nd edition book

Pages	Section
228-236	6.1.2 - 6.1.3
247-248	6.3.1 - 6.3.2
100 - 103	3.2
108-109	3.4.3

Java Source Code (taken from Professor Franck van Vreugel)

ArrayStack
StackFullException
ArrayQueue
QueueFullException
ArrayVector
VectorFullException
Implementation of a stack, queue and ranked sequence with an array in pseudocode: PDF version (Written by Professor Franck van Breugel)

You may find the following useful to review:

A Quick Mathematical Review:

first edition: pages 35-38

second edition: pages 103 - 106.

Finally, the following material is not required but is recommended if you have some spare time!

first edition: Stacks in the Java Virtual Machine: pages 74-77
second edition: Stacks in the Java Virtual Machine: pages 145-149

Time permitting, Pseudo Code and Loop Invariants will be introduced as well as implementations for Stacks and Queues.

Sample Questions
Solutions to Sample Questions