A discussion on Data Structures — Stacks.

Since the STL is fairly advanced, I talk about “containers” and “container adapters” and how I am implementing them, starting with Lists and Stacks.

Photo by Paweł Czerwiński on Unsplash

Today, let me move on to another data structure we traditionally study after Linked Lists — the logical progression — Stacks.

Containers Vs. Container Adapters.

The Standard Template Library calls some data structures Containers and some, Container Adapters. The simple distinction between them — at least from what I have gathered — is that when some Container A can be built on top of an existing one (Container B), such that it provides some specific functionality or characteristic to how Container B works, we can say that A is a Container Adapter.

For example, take Stacks and Linked Lists. As we have seen before, Linked Lists are a fundamental data structure — in the STL, they are called sequence Containers because they describe a fundamental way in which data is organized, accessed, and manipulated. Head here to read up on them and how we are implementing them in Telemetry:

A Discussion on Linked Lists.

Stacks, on the other hand, can be built on top of a variety of such containers! Cpluplus.com says that they can be built using Vector, Deque, and List (Linked Lists). More specifically, it mentions -

By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used.

Heck, most simple implementations can be achieved using Arrays!

Since Deque is a fairly complex container (believe me, I considered trying to implement it for the sake of staying as close to the STL as possible, but gave up after I started doubting my skills!) I’ll be building my Stack class using Lists as my base container. We can modify it suitably sometime later as a side project!

Stacks

Going back to our trusty sources, Cplusplus.com defines a Stack by saying:

Stacks are a type of container adaptor, specifically designed to operate in a LIFO context (last-in first-out), where elements are inserted and extracted only from one end of the container.

Essentially, think of it like a can of Pringles. As usual, I think a picture explains it better.

Fig 1. A diagrammatical representation of a Stack.

As we can see, in a Stack, the significant pointer is the Top pointer that points, as it says, to the element sitting on top of the Stack. When we remove an element from the Stack, it has to be this element. Since we start indexing from 0, an empty stack would have top = -1. Thus, when an element is inserted into the Stack, top increments by one and equals 0, that is, the index of the first element. In terms of Linked Lists, we can say that Top is initially a NULL pointer — when an element is inserted, Top points to the Head.

Operations on Stacks

The following operations are supposed to be available in Stacks:

1. empty(): Returns whether the Stack is empty or not.
2. size(): Returns the current size of the Stack (number of elements + 1, due to zero indexing).
3. top(): Access the top element. In Telemetry, I call this peek.
4. push(): Insert an element to the top of the Stack. Increments Top.
5. pop(): Take an element off the top of the Stack (and return its value). Decrements Top. If the Stack is empty, throws a StackUnderflowException.

The advantage here is that since the underlying Container we use should also support these operations (at least), functions such as stackObj.empty() can simply encapsulate those of the underlying Container, which, for us is a Linked List. (Does this also mean I don’t need to explain how these operations work? :’))

The UML (Unified Modeling Language) Class Diagram for our class is thus:

Fig 2. UML Class Diagram

Implementing Stack.h

Class definition

First, here’s the basic definition of the class (bear in mind I’m posting snippets, so things like include guards aren’t included. To see the full implementation, head over to the GitHub repository!):

template <class T>
class Stack {
private:
    static int stack_count;
    int ID;
    List<T> stack;
public:
    // utility functions;
    void push(T arg);
    T pop();
    T peek();
    int size();
    bool empty();
    static int get_stack_count();
    std::string get_ID();
    // constructors;
    Stack() {
        // increment the count of currently in-use stacks;
        ID = ++stack_count;
    }
};

Now, since the implementation of a template class must be in the same header file, the member functions are implemented as follows:

push()

template <class T>
void Stack<T>::push(T arg) {
    stack.push(arg);
}

If you look at the definition of the class closely, you will notice that stack is a List. This underlying container is being adapted by us as a Stack using its functions. For example, here, the push() function for the Stack calls the push() function of the underlying List! More such abstractions are made further.

pop()

template <class T>
T Stack<T>::pop() {
    if (stack.empty()) {
        throw StackUnderflowException(std::to_string(ID));
    } else {
        return stack.pop();
    }
}

As you can see, the pop() function is fairly straightforward too — without reinventing the wheel, we call functions of the stack object and they do the work for us. If the Stack is empty, we throw a StackUnderflowException, which is a custom Exception class we’ve created.

Side note!

While writing this function, it occurred to me that a discussion on when it is most appropriate to throw Exceptions might be in order. After all, it may seem that we could have an exception for any condition that isn’t in line with what we expect. That doesn’t seem right!

Doing some digging led me to this. Be warned, it’s a heavy discussion, but the general idea is that one should throw exceptions only when things seem bleak and unrecoverable — or to handle things you didn’t see coming. Is the user trying to divide by zero? There’s an exception for that. Trying to pull something out of an empty Stack? Yep.

Since this discussion goes a little out of scope, I’ll read about it and maybe do another post on this — what say you?

peek()

template <class T>
T Stack<T>::peek() {
    return top->data;
}

This one’s fairly simple and shows the use of the top pointer.

And I guess that’s it! While there are more functions to go, I’ll point you to the GitHub repository to go check them out there. See the bottom for the link.

In Conclusion

There isn’t very much to Stacks. Their specific structure makes them very handy in quite a few algorithms (which I will implement at a later date for each data structure we look over). If by now you’re wondering where all the code is, please go here. And that’s all I have for today, at 3 in the morning while I write this.

utkarshpant/telemetry

fin.

Edits

22nd July 2020 — I reworked the class and realized that int count and Node<T> *top are not needed in this class, since the List under the hood already supports these operations. Wherever top was used, I now return stack.get_head() instead.

References

1. Reema Thareja, 2017, Data Structures Using C, 2nd Ed., Oxford University Press.
2. std::stack (http://www.cplusplus.com/reference/stack/stack/)
3. What is the difference between a “container” and a “data structure”?https://stackoverflow.com/questions/11218100/what-is-the-difference-between-a-container-and-a-data-structure
4. What are Containers/Adapters? C++ https://stackoverflow.com/questions/3873802/what-are-containers-adapters-c
5. When to throw an exception? https://stackoverflow.com/questions/77127/when-to-throw-an-exception