542 Chapter 12 Support for Object-Oriented Programming
nodes to be inserted at either end of a list object, nodes to be removed from
one end of a list, and lists to be tested for empty.
The following definitions provide stack and queue classes, both based on
the single_linked_list class:class stack : public single_linked_list {
public:
stack() {}
void push(int value) {
insert_at_head(value);
}
int pop() {
return remove_at_head();
}
};
class queue : public single_linked_list {
public:
queue() {}
void enqueue(int value) {
insert_at_tail(value);
}
int dequeue() {
remove_at_head();
}
};Note that objects of both the stack and queue subclasses can access the
empty function defined in the base class, single_linked_list (because
it is a public derivation). Both subclasses define constructor functions that
do nothing. When an object of a subclass is created, the proper construc-
tor in the subclass is implicitly called. Then, any applicable constructor in
the base class is called. So, in our example, when an object of type stack
is created, the stack constructor is called, which does nothing. Then the
constructor in single_linked_list is called, which does the necessary
initialization.
The classes stack and queue both suffer from the same serious problem:
Clients of both can access all of the public members of the parent class,
single_linked_list. A client of a stack object could call insert_at_
tail, thereby destroying the integrity of its stack. Likewise, a client of a
queue object could call insert_at_head. These unwanted accesses are
allowed because both stack and queue are subtypes of single_linked_
list. Public derivation is used where the one wants the subclass to inherit
the entire interface of the base class. The alternative is to permit derivation
in which the subclass inherits only the implementation of the base class. Our
two example derived classes can be written to make them not subtypes of their