21. Stacks

21.1. Abstract data types

The data types we have looked at so far are all concrete, in the sense that we have completely specified how they are implemented. For example, the Card class represents a card using two integers. As we discussed in the Card objects section, there are alternative implementations, one of which we explored in Enumerated types.

An abstract data type, or ADT, specifies a set of operations (or functions) and the semantics of the operations (what they do), but it does not specify the implementations of the operations.

Why is that useful?

• It simplifies the task of specifying an algorithm if you can denote the operations you need without having to think at the same time about how the operations are performed.

• Since there are usually many ways to implement an ADT, it might be useful to write an algorithm that can be used with any of the possible implementations.

• Well-known ADTs, like the Stack ADT in this chapter, are often implemented in standard libriaries so they can be written once and used by many programmers.

• The operations on ADTs provide a common high-level language for specifying and talking about algorithms.

When we talk about ADTs, we often distinguish the code that uses the ADT, called the client code, from the code that implements the ADT, called provider code because it provides a standard set of services. The collection of classes and functions through which the client code accesses the provider codes is called the application programming interface (API).

21.2. The Stack ADT

In this chapter we will look at one common ADT, the stack. A stack is a collection. Other collections we have seen include vectors and lists.

An ADT is defined by the operations you can perform on it. Stacks can perform only the following operations:

new

Create a new, empty stack.

push

Add a new item to the stack.

pop

Remove and return an item from the stack. The item that is returned is always the last one that was added.

top

Return the value at the top of the stack without removing it.

empty

Check whether the stack is empty.

A stack is sometimes called a “last in, first out,” or LIFO data structure, because the last item added is the first to be removed.

Stacks have numerous uses in computer science, including in the run-time stack used by operating systems to manage function calls.

21.3. Implemeting stacks with linked lists

We will look at a few different implementations of the stack ADT, beginning with one that we have already written, without even knowing it.

Take a look back at the LinkedList class we wrote in the previous chapter, then look at the operations defined for the stack ADT. If it occurs to you that the push operation looks a lot like what the insert_at_front function does, and pop similarly looks like remove_from_front, then you are doing well. In fact, with just a little tweaking, our LinkedList class could perform all the functions want from stacks.

How should we do this “tweaking”? We could just write a new Stack class, burrowing most of the logic we used to create LinkLists and rewriting it, but this would violate the DRY principle that we introduced in Wrappers, helpers, and function pointers. So instead, we’ll make take advantage of another core feature of object-oriented programming languages: inheritance.

21.4. Inheritance

Inheritance is the ability to define a new class that is a modified version of a previously defined class (including a built-in class). The primary advantage of this feature is that you can add new functions or instance variables to an existing class without modifying the existing class. It allows you to reuse of the code in the existing class without having to repeat it. This is particularly useful for built-in classes, since you can’t modify them even if you want to.

The reason inheritance is called “inheritance” is that the new class inherits all the instance variables and functions of the exisiting class. Extending this metaphor, the exisiting class is sometimes called the parent class and the derived class called the child class.

Note

Another common pair of terms for the classes in the inheritance relationship is superclass and subclass.

Our desire to implement the stack ADT utilizing our existing LinkedList class provides a nice opportunity to use inheritance. Here is the entire source code for a stack class that inherits from LinkedList residing in a file named Stack.h:

#include <iostream>
#include <string>
#include "LinkedList.h"
using namespace std;


template <class T>
class Stack : public LinkedList<T>
{
  public:
    // constructors
    Stack() = default;
    
    // modifiers
    void push(T item) {
        LinkedList<T>::add_to_front(item);
    }

    T pop() {
        return LinkedList<T>::remove_from_front();
    }

    bool empty() const {
        return (LinkedList<T>::length() == 0);
    }

    T top() {
        if (LinkedList<T>::head == NULL)
            throw runtime_error("Can't return top item of empty stack!");
        return LinkedList<T>::head->cargo;
    }
};

To use it, you need to have the LinkedList.h file provided in Appendix A: Code Source in the same location as Stack.h.

The two lines:

template <class T>
class Stack : public LinkedList<T>

specify that we are creating a templated class named Stack that is a child class of LinkedList<T>. The keyword public specifies that our derived class will have access to all the instance variables and member functions of its parent class.

Note

We have been making all our classes public. Be forewarned that you may be told by more experienced C++ programmers that this is unsafe and a bad practice. C++ supports access specifiers to provide controlled access from one part of the code to another. Implementing access control is cumbersome and would have greatly complicated both our code examples and their explainations. Since our goal is to present “big ideas” here as assessibly as possible, we intentionally avoided getting stuck “in the weeds” with this topic. If your intention is to become a C++ programer, you will definitely need to learn all about it.

Stack() = default;

gives us a default constructor for our Stack class. Calling this constructor will also call the default constructor of its parent class, creating a list with instance variables num_nodes and head.

Modifier member functions push and pop just call insert_at_front and remove_from_front respectively, giving their already implemented functionality our new stack API.

The LinkedList class doesn’t have an exact equivalent of a Boolean empty function, but it does have the accessor function length. A stack is empty when the length of its list of items is 0.

Here is a small program in a file named test_stack.cpp that we can use to test our Stack implementation:

#include <iostream>
#include "Stack.h"
using namespace std;

int main()
{
    Stack<int>* stack = new Stack<int>();
    cout << "Calling stack->empty() gives: " << stack->empty() << endl;

    for (int i = 1; i <= 5; i++) {
        cout << "Pushing " << i * i << "..." << endl;
        stack->push(i * i);
    }

    cout << "Calling stack->empty() now gives: " << stack->empty() << endl;
    cout << "The top of the stack contains: " << stack->top() << endl;

    while (stack->empty() == false) {
        cout << "Popping " << stack->pop() << "..." << endl;
    }

    cout << "Calling stack->empty() after while loop gives: ";
    cout << stack->empty() << endl;

    return 0;
}

21.5. Exceptions

The last of our stack API functions, top, presents us with a problem similar to the one we saw in Preconditions. This function should only be called on a non-empty stack. In fact, non-emptiness could be considered a precondition for top. So what should happen when we try to call top on an empty stack?

The top function is defined to return a value of type T. It’s not at all clear what top should do with an empty stack, and if we don’t do anything to handle the problem, trying to access the cargo attribute of a NULL pointer to a Node will result in a runtime error. As we mentioned way back in Runtime errors, these are also called exceptions, and C++ has a standard way of handling them.

The three keywords C++ uses to handle exceptions are try, catch, and throw. The way to handle code which could cause an exception to occur is to put the code in a try-block and then to write exception-handlers which are declared with the keyword catch.

To do this for our top function, we would write something like this:

T top() {
    try {
        if (LinkedList<T>::head == NULL)
            throw runtime_error("Can't return top item of empty stack!");
        return LinkedList<T>::head->cargo;
    }
    catch (exception& e) {
        // Do something sensible here to handle the exception
    }
}

Since catch would have to return a value of type T, and since it is not at all clear how to do that, we will instead keep our previous verstion of top that calls throw after checking if head is NULL. Calling top on an empty stack will still cause the program to crash, but at least it will report the helpful measage, “Can’t return top item of empty stack!”, as it crashes.

21.6. Postfix expressions

In most programming languages, mathematical expressions are written with the operator between the two operands, as in \(1 + 2\). This format is called infix. An alternative format used by some scientific calculators is called postfix. In postfix, the operator follows the operands, as in \(1\;2\;+\).

One advantage of postfix over infix is that it eliminates the need for parenthesis in expressions like \((4 + 5) * 3\), since the postfix expression for this is unambiguously written as \(4\;5 + 3\;*\).

Another advantage of postfix for programmers (and calculator designers) is that there is a natural way to evaluate a postfix expression using a stack.

• Starting at the beginning of the expression, get one term (operator or operand) at a time.

  • If the term is an operand, push it on the stack.

  • If the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack.

• When we get to the end of the expression, there should be exactly one operand on the stack. That operand is the result.

21.7. Parsing

In order to implement the algorithm from the previous section, we need to be able to traverse a string and break it into operands and operators. This process is an example of parsing.

21.8. Implementing APIs

One of the fundamental goals of an API is to separate the interests of the provider, who writes the code that implements the API, and the client, who uses the API. The provider only has to worry about whether the implementation is correct – that calls made using the API will do what they are supposed to do – not about how it will be used.

Conversely, the client assumes that the implementation works as specified and doesn’t worry about the details. When you use C++’s standard library, you have the luxury of thinking exclusively as a client.

When you implement an API, on the other hand, you also have to write the client code to test it. In that case, you sometimes have to think carefully about which role you are playing at a given time.

In the next few sections we will switch gears and look at another way of implementing the Stack ADT using a vector.

21.9. Array implementation of the Stack ADT

Our stack data for this implementation will be stored in the simple C style array which we were introduced to in the Arrays section of the Pointers and arrays chapter.

#include <iostream>
#define MAX_SIZE 128
using namespace std;

template <class T>
class Stack
{
    int top_item;
    T items[MAX_SIZE];

  public:
    // constructors
    Stack() { 
        top_item = -1;
    }
    
    // modifiers
    void push(T item) {
        items[top_item++] = item;
    }

    T pop() {
        if (top_item == -1)
           throw runtime_error("Can't pop from empty stack!");
        return items[top_item--];
    }

    bool empty() const {
        return top_item == -1;
    }

    T top() {
       if (top_item == -1)
           throw runtime_error("Can't return top item of empty stack!");
       return items[top_item];
    }
};

The second line uses the preprocessor directive #define to define a constant value (128 in this case) named MAX_SIZE. The preprocessor will replace all occurances of MAX_SIZE with the literal value 128 before the code is compiled.

21.10. The stack in the standard template library

A standard library is a collection of programming resources (pre-defined constants, functions, classes, etc.) that can be treated by programmers as part of the language, since they come “standard” with it.

We have been using the C++ standard library since the first chapter of this book, since every time we write #include <iostream> and use cout we are using the standard library.

21.11. Glossary

abstract data type (ADT)

A data type (usually a collection of objects) that is defined by a set of operations, but that can be implemented in a variety of ways.

client

A program that uses an ADT (or the person who wrote the program).

provider

The code that implements an ADT (or the person who wrote it).

application programming interface (API)

The classes and functions through which an interface is provided from one piece of software, the provider, to another piece of software, the client.

infix

A way of writing mathematical expressions with the operators between the operands.

postfix

A way of writing mathematical expressions with the operators after the operands.

delimiter

A character that is used to separate tokens, like the punctuation in a natural language.

21.12. Exercises

• Chapter 21 Exercise Set 1