ADT Queue

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 asking questions.

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 programming.

ADT Queue

Queue is FIFO; stack is FILO.

Operations

• CreateQueue() --- Create empty queue.
• DestroyQueue().
• 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.

Array-Based Implementation

• Max size: compile-time, run-time.
• ``Circular'' array.
• Keeping track of head and tail: two ways.

Dynamic, Pointer-Based Implementation

• ``Custom'' linked-list: head and tail pointers, one pointer and a circular list.

A Derived Class Implementation

• Base class would be a privately inherited List class (as-a relationship).
• See Chapter 8; will discuss in more detail later.