Linked Lists, Queues and Stacks

In this post: I outline how to make queues and stacks using a linked list, explaining some important design choices.

Useful background: C++ pointers, templates, classes.
 

Pivotal to the field of data structures are the fundamental abstract data types (ADTs) such as queues and stacks. In fact, I'd consider those two examples particularly fundamental, as they have a tendency to underpin the flow of algorithms more commonly than anything else. Personally, I realised I somewhat took them for granted until studying artificial intelligence, or, more accurately, graph traversal. The C++ STL provides a good range of ADTs suitable for a vast majority of real-world applications but, as with most things, I think the best way to truly understand them is to have a crack at implementing them yourself. Not only does this help you to understand the blood and guts, but it also helps in appreciating the sometimes obscure design decisions of these implementations compared to their theoretical outlines. Also, you have the ability to easily customise and specialise for your own applications and debugging purposes.

Queues vs Stacks

Firstly, what are these two data types? They both represent a collection of some arbitrary data type and their names more-or-less give away exactly what they achieve. Both are simple linear collections, but differ in how they represent the order of their elements. Queues operate on a first-in, first-out (FIFO) basis. In other words, the 'next' element in a queue is that which has been in it for the longest time – just like a queue of people waiting. In contrast, stacks operate on a last-in, first-out (LIFO) basis, wherein the 'next' element is that which has been in it for the shortest time – imagine a pile of plates or books.

In terms of practical applications, stacks are utterly ubiquitous. Subroutining operates on a call stack, which provides the correct order of function calls, recursion and backtracking (giving rise to the infamous 'stack overflow' error!). A lot of languages, such as C, store local data entities 'on the stack'. As mentioned previously, both stacks and queues are used in algorithms of all kinds to dictate the correct order of data discovery and processing.

In conclusion, our queue should have enqueue and dequeue operations, whilst our stack should have push and pop operations.

Linked List

It's evident that both of these structures are actually very similar, so their underlying structure can be the same. What I mean by underlying structure is how their data is actually stored on the computer, as the concept of queues and stacks are abstractions. There's generally two primary fundamental data structures to look at: the array and the linked list. Arrays are indexed contiguous memory and often a native feature of imperative languages, including C++, whereas inked lists are arbitrarily-located nodes of memory linked in order. To choose between them, let's consider that the only operations we need are addition and removal from the front and end of the collection. Arrays provide constant-time random access, but addition and removal are linear-time in nature. In contrast, linked lists provide constant-time addition and removal from its ends, whilst its linear-time random access is not needed here, making it the natural choice.

In order to provide constant-time addition and removal from both the front and back of the list, we'll store both front and back node pointers (hereinafter referred to as double-ended). We don't actually need removal from the back, so we can stick to a singly-linked list for simplicity's sake. Let's take a look at implementing a double-ended singly-linked list (DESLinkedList).

template <typename T>
class DESLinkedList
{
private:
    struct Node
    {
        T data;
        Node *next;

        Node(const T &data) : data(data), next(nullptr) {}
    };

    Node *front;
    Node *back;

As an container of some arbitrary data type, it's natural to make this a class template. Firstly, we implement a Node as a nested private class. A Node simply contains one data element and a pointer to the next Node in the list. Then, the DESLinkedList is formed of a pointer to the front node and the back node. This is actually the list definition completed; but, of course, we want to provide a public interface with basic operations.

    //Returns true if there are no elements in the list
    bool empty() const { return front == nullptr; }

It's useful to be able to test if the list is empty, not only from the public end but also because it will affect how we add elements. Naturally, the list is empty if the front pointer is null.

    //Default constructor initialises empty list
    DESLinkedList() : front(nullptr), back(nullptr) {}

    //Destructor deletes all elements
    ~DESLinkedList()
    {
        while (!empty())
        {
            Node *n = front->next;
            delete front;
            front = n;
        }
    }

Next, our constructor just makes sure the pointers are set to null. As we're dealing with dynamic memory manually, we need to ensure it's all freed by defining a destructor, which simply deletes elements from the front until empty.

Note: In defining a destructor, the rule of three recommends we also define copy and copy assignment constructors. If using this code, I recommend either adhering to this or using smart pointers.

    //The front or back of the list can be used
    enum End { FRONT, BACK };

    //Adds the given element to the given end of the list
    void add(const T &elt, End end)
    {
        Node *newNode = new Node(elt);

        if (empty())
            front = back = newNode;

        else switch (end)
        {
        case FRONT:
            newNode->next = front;
            front = newNode;
            break;
        case BACK:
            back->next = newNode;
            back = newNode;
            break;
        }
    }

This list is designed to support addition to both the front and the back, so I decided to tidy the public interface by enumerating this option; thus the add operation takes an element and an end. First, we turn the element into a Node. If the list is empty, all we have to do is set both pointers to it. Otherwise, we have set the corresponding pointers of both the list and the node/neighbour.

Next, we need to allow the access and removal of elements. In the formal definitions of queues and stacks, the dequeue/pop operations simultaneously return the next element and remove it from the list. However, you may notice that the STL containers split these into separate peek and pop operations. This is mainly due to exception safety, as if the copy constructor using a combined pop operations throws an exception, that element would be lost (see command-query separation for a generalised principle). We'll follow this lead and define separate remove and peek methods.

    //Removes the element at the given end of the list
    void remove(End end)
    {
        Node *node = nullptr;

        switch (end)
        {
        case FRONT:
            node = front;
            front = node->next;
            delete node;
            break;
        case BACK:
            //NOT IMPLEMENTED
            break;
        }
    }

    //Returns the element at the given end of the list
    T &peek(End end)
    {
        Node *node = (end == FRONT) ? front : back;
        return node->data;
    }

As mentioned before, removal from the back end is not necessary and thus not implemented. If you want it, you'll have to iterate through the list to find the penultimate Node. Unlike all of our other operations, this would be linear in complexity, so it would be best to refactor the list to be doubly-linked (wherein each Node keeps a pointer to its predecessor as well as its successor). Peeking at both ends is trivial.

Note: alarm bells may be ringing at the fact we're not doing any bound-checking when accessing elements. Your initial reaction may be to throw an exception if attempting to remove or peek on an empty list, which is far from bad practice. However, the STL containers offer a no-throw guarantee in these cases, allowing undefined behaviour if removing or peeking from empty. This is for efficiency reasons -- here, we've just taken their lead.

    //Outputs the list to the stream
    friend std::ostream& operator<<(std::ostream &os, const DESLinkedList &l)
    {
        Node *n = l.front;
        while (n)
        {
            os << n->data << " ";
            n = n->next;
        }
        return os;
    }

Finally, I also provided the ability to output the entire list to a stream. The STL doesn't provide iteration to containers like queues and stacks, so I enjoy using this custom version for debugging purposes, or indeed a simple use where printing is desired. Don't forget to #include <iostream>!

Deriving the Queue and Stack

Testing the DSELinkedList out, you should find you can use it as a queue or a stack, because we've finished all the heavy lifting and provided all the interface we need. However, it's desirable to encapsulate the functionality into respective classes.

template <typename T>
class Stack : protected DESLinkedList<T>
{
public:
    using DESLinkedList<T>::empty;

    //Pushes the given element
    void push(const T &elt)
    {
        this->add(elt, this->FRONT);
    }

    //Pops the next element
    void pop()
    {
        this->remove(this->FRONT);
    }

    //Returns the next element
    T &peek()
    {
        return DESLinkedList<T>::peek(this->FRONT);
    }

    //Outputs the stack to the stream
    friend std::ostream& operator<<(std::ostream &os, const Stack &q)
    {
        return os << static_cast<const DESLinkedList<T> &>(q);
    }
};

Here, I've derived the subclass using the protected modifier, which means the public members of DSELinkedList become protected in Queue. I chose to do this in order to remove the ability to freely add/remove from either end of the list because, after all, the whole point of these subclasses is to abstract the public interface of the list into the concept of the queue/stack. The enqueue operation adds to the back and the dequeue/peek operations removes/returns from the front. The using notation provides a simple passthrough of the superclass method, and the stream operator does the same thing in a more unfortunately verbose manner. The Stack class is almost identical to Queue, except its push operation adds to the front, instead.

Conclusion

I first found myself coding a custom queue class when I began dealing with artificial intelligence search algorithms and desired the ability to regularly print out the contents of the container as the algorithm progressed, for debugging purposes. I'd say that if any of the STL containers seem to lack some specialisation or feature you'd find particularly useful for some task, then maybe have a crack at coding your own version of the underlying structure – I know I always enjoy the learning experience, to boot.

Source code

• Double-ended singly-linked list (C++)
• Queue and stack based on linked list (C++)