In the above example you see that our Base class implements a virtual function called MorphMePlease() and that our Derived class overrides that function with its own implementation. Depending on what you pass into the non-member function SomeNonMemberFunction() either the Base or the Derived class' function can be called. How is that? When a pointer to a Derived object is passed in, it is implicitly upcast to a Base pointer. Even though the cast is performed, the object's vpointer is unchanged, and therefore still points to the VTABLE of Derived function addresses. This type of functionality demonstrates the ability to change functional behavior based on object type at runtime. This is the polymorphism we mentioned earlier.

So what happens with pure virtual functions? If by definition, they don't have a default definition, how does the compiler treat them? Well, as we mentioned earlier, the compiler must guarantee that every function call be associated with a corresponding function body address. If this were not guaranteed, we'd have all kinds of runtime errors when a function call was invoked that had no body (imagine the madness...). When the compiler sees that an object type has a pure virtual function, it reserves a row in the VTABLE for the associated function body, but doesn't actually insert the address (b/c there isn't one). Of course, this makes the VTABLE for that object type incomplete. Since the table is incomplete, the compiler cannot guarantee safe execution of that object's code. Because of this, the compiler will throw an error if an object of that type is instantiated anywhere in the compiled code. Because you cannot actually instantiate this object type, it becomes what is known as an abstract class type. Let's take a look at our previous example using pure virtual functions instead.

class Base
{
public:
    Base();
    ~Base();

    void PrintStuff();

    // Pure virtual functions require that a 
    // derived class define the function body.
    virtual long MorphMePlease() = 0;
};

class Derived : public Base();
{
public:
    Derived();
    ~Derived();

    // Derived class defines the function body
    // and is therefore allowed to be instantiated.
    long MorphMePlease();
};

// Derived function definition that defines the 
// Base class' pure virtual function
long
Derived::MorphMePlease()
{
    return 1;
}

In our updated example above, we notice the Base::MorphMePlease() function declaration is assigned to zero. That assignment signals to the compiler that a function is pure virtual (and therefore makes the class abstract). You will also notice that the Base::MorphMePlease() function definition is not provided. If you tried to provide one the compiler would barf and say you need to make up your mind b/w virtual and pure virtual functions (paraphrasing of course *grin*). If you were to remove the declaration and definition of the Derived::MorphMePlease() function, the Derived class would also become abstract and therefore not instantiatable. This is because the Derived object type's VTABLE would be incomplete as well.

Now that virtual functions and call binding have been explained, there are a few more points that need mentioning. First, the initialization of the VTABLE and vpointer structures is performed during object construction. The compiler provides this hidden code for you in your constructor and therefore you don't have to write it. Second, be careful about how you cast objects up/down the inheritance tree. Casting down or casting from a base object to a derived object is not guaranteed to work and has additional performance overhead. This is because there is no runtime information which guarantees the downcast to succeed. Therefore, an explicit cast is required. It is safest to use the dynamic_cast() function to cast a base object to its derived type. dynamic_cast() performs a runtime check to verify the cast will succeed and then performs the operation. This additional runtime type verification is the performance overhead I hinted at earlier. If you know more about your object hierarchy during downcasting you might be able to save the performance overhead of dynamic_cast() and substitute it with static_cast(). static_cast() doesn't perform the runtime check and there isn't guaranteed to be a safe operation. The benefit is that it is faster than dynamic_cast(). If the downcast fails, it returns a NULL pointer to the calling code. You just need to add a check for NULL before using the newly cast pointer. Casting up, on the other hand, is always safe. A derived class object is always a Base class object. This casting is performed implicitly for you and doesn't require the use of code>dynamic_cast or any other explicit cast code.

Virtual functions allow C++ to implement late binding and therefore polymorphic object behavior. They can sometimes be a bit tricky to grasp, but once understood, they become a fundamental principle that C++ programmers rely on. Until next time...

- Gilemonster

A queue is also a dynamic linear data structure with predetermined insertion and deletion operations. The main difference between a stack and queue is that a queue practices FIFO ("First In First Out"). This means that new items are added at the top of the queue (or tail) and are removed from the bottom (or head). A good analogy is your standard waiting line to get into the movie theater. You get in line at the end and wait until those customers before you have purchased tickets and walked away. Then you get to go next while the people who entered the line after you await their turn. Insert and delete operations are called enqueue and dequeue respectively and both are performed in constant time O(1) just like stacks.

Queues require slightly more work because we are required to keep up with both the beginning (the "head") and the ending (the "tail") of the structure in our implementations. With stacks, all we have to do is just make sure that the top-most element is within boundary limits. With queues, we are required to make sure that when an element is added, it goes in the tail's current location and when an item is removed, we have to make sure that the element in the head's current location is deleted. Also, the same boundary conditions in stacks exist for queues (e.g. underflows and overflows). Below, I have provided some pseudocode showing how a simple queue structure works:

void Enqueue(int newVal)
{
    if (Queue isn't full (e.g. overflow))
    {
        - Add your value to the tail of the queue
        - Increment your tail index (or wrap it)
    }
}

void Dequeue(int & newVal)
{
    if (Queue isn't empty (e.g. underflow))
    {
        - Remove item from queue and assign to the
          newVal parameter
        - Increment your head index (or wrap it)
    }
}

Stacks and queues are simple and easy to use for certain programming projects (e.g. postfix/infix evaluations). The easiest implementation technique used for both is to use an array as the internal structure (my pseudocode examples use an array). There are more complex implementations but arrays are used more frequently because of the simplicity. As always, post comments if something isn't clear and I'll try to help out. If you'd like the full queue and stack class files (.h & .cpp) let me know and I'll provide a link to them. Until next time...

-Gilemonster