Tom Kelliher, CS23
Mar. 22, 1996
This discussion of the ADT will be brief. I bet most, if not all, of you
know what a queue is, so there's little point in me explicitly covering it.
I'll just define the ADT and mention a few implementations. There's a good
chance I won't even discuss this material in class; so you're responsible
for it and I'll leave it to you to clear up any points of confusion by
What we'll really do is either:
- Watch Bjarne Stroustrup (the creator of C++) discuss C++.
- Watch Danny Ignalls (a heavyweight in OOP) discuss object-oriented
Queue is FIFO; stack is FILO.
- CreateQueue() --- Create empty queue.
- QueueIsEmpty() --- Boolean.
- QueueAdd(NewItem, Success) --- Add NewItem to
tail of queue.
- QueueRemove(Success) --- If queue is non-empty, remove item
at head of queue.
- GetQueueFront(QueueFront, Success) --- If queue is non-empty,
retrieve value of item at head of queue through QueueFront.
- Max size: compile-time, run-time.
- ``Circular'' array.
- Keeping track of head and tail: two ways.
- ``Custom'' linked-list: head and tail pointers, one pointer and a
- Base class would be a privately inherited List class (as-a
- See Chapter 8; will discuss in more detail later.
Thomas P. Kelliher
Thu Mar 21 10:44:33 EST 1996