The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Array Implementation of the Stack ADT

The instance variables for this implementation is a templated array, which is why we will use the pvector class. It will contain the items on the stack, and an integer index which will keep track of the next available space in the array. Initially, the array is empty and the index is 0.

To add an element to the stack (push), we'll copy a reference to it onto the stack and increment the index. To remove an element (pop) we have to decrement the index first and then copy the element out.

Here is the class definition:

class Stack {

    pvector<ITEMTYPE> array;
    int index;


      Stack () {
        index = 0;

The above code contains the type ITEMTYPE which is essentially just a quick way of saying, "INSERT DATATYPE HERE" because pvectors are templated and can handle various types. ITEMTYPE is not in actuality a type, just so you know. In the future, you can replace ITEMTYPE with any other data type, class, or struct.

As usual, once we have chosen the instance variables, it is a mechanical process to write a constructor. For now, the default size is 128 items. Later we will consider better ways of handling this.

Checking for an empty stack is trivial.

    bool empty () {
        return array.length() == 0;

It it important to remember, though, that the number of elements in the stack is not the same as the size of the array. Initially the size is 128, but the number of elements is 0.

The implementations of push and pop follow naturally from the specification.

    void push (ITEMTYPE item) {
        array[index] = item;

    ITEMTYPE pop () {
        return array[index];

To test these methods, we can take advantage of the client code we used to exercise pstack.

If everything goes according to plan, the program should work without any additional changes. Again, one of the strengths of using an ADT is that you can change implementations without changing client code.

Last Update: 2005-12-05