The Concept of an Abstract Data Type (ADT)
Recall that a data type has two components:
To date we have seen examples of built-in data types like ints, chars, and arrays, and examples of simple classes like student. The remainder of this course will deal primarily with Abstract Data Types, usually abbreviated ADTs. An ADT consists of a formal, public description of the behavior of the ADT, along with a set of of public operations on it. In addition, there will be an implementation of the ADT. Typically the implementation details are hidden from the user. Nevertheless, the user can use ADTs because the operations are public. This is important because a software maintainer can make changes in the implementation code of an ADT without other programmers having to know about these changes.
There are a number of more or less standard ADTs that are widely used. This worksheet will describe four such ADTs, the Set, the List (or sequence), the Stack, and the Queue.
The ADT Set
Consider the ADT Set. A Set consists of a collection of items, with the order unspecified. (Surely you have studied sets in your math courses.) Duplicate items are not allowed. Here is a set of possible operations on a set. In all cases, the type of the set, (i.e. the type of item which the set contains), will be represented by the keyword TYPE.
~Set() a destructor which returns all allocated memory
to the heap (this may not be needed if the implementation does not
allocate new memory with new).
Of course this is not a complete list of operations that one might want on a set, but it is a representative sample. Notice that this description says nothing about how a set might be implemented. The obvious way to implement such a set is with an array, but there are other ways of doing it. Note also that different programmers might implement a set differently, but other modules that use the ADT Set would not be affected.
The keyword const after some of the functions means that the function is guaranteed not to change any of the data members of the instance of the class.
Exercise 1: Write a template class Set with all of these operations.
Other operations on a set might include the following:
+).
*).
Note that the arguments are passed in as const reference pointers. It is customary when passing in classes as arguments to pass them in as reference pointers. This has two advantages.
The ADT List
Another important data type is a List, also known as a Sequence. A List is a collection of items in a particular order. Here are some typical operations on a list.
~List() the destructor (may not be needed if the implementation
does not use dynamic memory allocation with new)
As with a set, there may be other member functions as well, this is a core set. Note also that a List is an abstract concept; there are a number of possible implementations of a list, and the user of a list does not need to know how it is implemented in order to use it.
Exercise 2: Write a template class List with the above member functions.
The ADT Stack
A Stack is a variant of a list. It consists of a collection of ordered items, but the user can only add items at one end (usually called the top) and remove items from the same end. In other words, a stack is Last In, First Out (LIFO). It is called a stack because it is analogous to a stack of plates in which you can only add a new plate to the top or and only retrieve the top plate.
Here is a list of possible member functions for the ADT stack.
~Stack() a destructor
Many implementations of a stack split the Pop function into two separate functions:
Exercise 3: What would the following program print (assuming that Pop both returns the top value and removes it from the stack)?
#include "Stack.h"
int main()
{
Stack<int> S1;
int r;
S1.Push(23);
S1.Push(44);
S1.Push(32);
r = S1.Pop();
cout << r << endl; // ____
S1.Push(30);
S1.Push(18);
r = S1.Pop();
cout << r << endl; // ____
r = S1.Pop();
cout << r << endl; // ____
r = S1.Pop();
cout << r << endl; // ____
S1.Push(29);
S1.Push(77);
r = S1.Pop();
cout << r << endl; // ____
r = S1.Pop();
cout << r << endl; // ____
r = S1.Pop();
cout << r << endl; // ____
return 0;
}
A Stack is typically implemented as an array with the bottom of the stack at position zero, and a private variable top which points to the first empty slot. The constructor initializes top to zero. Here is a simple implementation of Push and Pop (the array is called simply array and is of type TYPE.).
void Stack::Push(TYPE item)
{
array[top++] = item;
}
TYPE Stack::Pop()
{
if (top == 0) Error(); // an unspecified error handler
else {
top--;
return array[top];
}
}
The ADT Queue
A queue is another variant of a list. A queue is like a line at a deli counter; as people arrive, they go to the end (tail) of the queue and as they are served, they are removed from the head of the queue. A queue is an ordered list with a first in first out (FIFO) property.
Here are some typical member functions:
~Queue() a destructor
A queue is often implemented as an array, with two private indices to it, head and tail. The index head points to the first item to be dequeued, and the index tail points to the next empty slot. Head is increased by a Dequeue operation and tail is increased by an Enqueue operation.
Arrays are of fixed size, and so eventually head and tail will get to the end of the array. It is fairly easy to have a wrap-around feature, i.e. if the array size is MAX, when tail reaches MAX, it is set to zero and starts over again.
For example, if MAX is 100, after 40 enqueue operations and 15 dequeue operations tail would have the value 40 and head would have the value 15. There are 25 items in the queue. Note that the order of the enqueue and dequeue operations does not matter as long as dequeue operations are only called when the queue has at least one item in it. After 105 enqueue operations, and 80 dequeue operations, tail would have the value 5, head would have the value 80, and there would be 25 items in the queue. After 150 enqueue operations and 145 dequeue operations, tail would have the value 50, head would have the value 45, and there would be 5 items in the queue.
As always, there are other ways to implement a queue, and the user does not need to know how a queue is implemented in order to use it.
Exercise 4: Implement the ADT Queue as described above.
Alert: Some of the quizzes may ask you to build on your implementations of these four data structures, and other quizzes may be closed book, closed notes.
Answer to exercise 3
32 18 30 44 77 29 23