18. Stacks¶

18.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 Enumerations.

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).

18.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. We will explore some of these in the exercises.

18.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 we 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 Our own find function.

Our desire to implement the stack ADT utilizing our existing LinkedList class provides a nice opportunity to use inheritence, to which we were introducted in the Inheritance of chapter 13.

Here is the entire source code for a stack object that inherits from LinkedList residing in a file named Stack.h:

#include "LinkedList.h"


template <class T>
struct Stack : public LinkedList<T>
{
    void push(T item) {
        LinkedList<T>::insert_at_front(item);
    }

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

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

    T top() {
       if (LinkedList<T>::head == nullptr)
           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.

Notice that there is no constructor defined for our stack. Instead, we are using the implicitely declared default constructor that C++ gives us, which in this case calls the no argument contructor of the base object, our linked list, creating a linked list with instance variables num_nodes and head.

Note

We have been making most of our objects public by using struct instead of class. 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 accessibly 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.

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 object 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.

Finally top returns the cargo of the head node. We can do this without the compiler complaining because we made everything in our Node objects public.

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;
    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;
}

Running it yields:

Calling stack.empty() gives: 1
Pushing 1...
Pushing 4...
Pushing 9...
Pushing 16...
Pushing 25...
Calling stack.empty() now gives: 0
The top of the stack contains: 25
Popping 25...
Popping 16...
Popping 9...
Popping 4...
Popping 1...
Calling stack.empty() after while loop gives: 1

As we have been doing, you will be asked to write automated tests for it in the exercises.

18.4. 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 == nullptr)
            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 nullptr. 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.

18.5. Implementing stacks by wrapping a list¶

Instead of having our Stack inherit from LinkedList, we could have it wrap LinkedList by having a linked list as its private data member.

#include "LinkedList.h"

template <class T>
class Stack
{
    LinkedList<T> items;

  public:
    void push(T item) {
        items.insert_at_front(item);
    }

    T pop() {
        if (empty())
           throw runtime_error("Can't pop from empty stack!");
        return items.remove_from_front();
    }

    bool empty() const {
        return items.length() == 0;
    }

    T top() {
       if (empty())
           throw runtime_error("Can't return top item of empty stack!");
       T top_item = items.remove_from_front();
       items.insert_at_front(top_item);
       return top_item; 
    }
};

This version uses the class keyword instead of struct, and makes the wrapped link list a private data member. LinkedList could also be changed to a class with its num_nodes and head data members private. Doing that prevents access to the cargo of the head node from within our stack code. The top function of this version has been written to use only list API calls. The front element is removed, returning its value, and then placed back on the front of the list.

18.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.

18.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.

18.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.

18.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.

#ifndef STACK_H
#define STACK_H
#define MAX_SIZE 128
#include <stdexcept>

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

public:
    Stack() {
        top_item = -1;
    }

    void push(const T& value) {
        if (top_item >= MAX_SIZE - 1) {
            throw std::overflow_error("Stack overflow");
        }
        items[++top_item] = value;
    }

    T pop() {
        if (empty()) {
            throw std::underflow_error("Stack underflow");
        }
        return items[top_item--];
    }

    const T& top() const {
        if (empty()) {
            throw std::underflow_error("Stack is empty");
        }
        return items[top_item];
    }

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

    size_t size() const {
        return top_item + 1;
    }
};

#endif // STACK_H

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.

18.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.

18.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.