Generic Stack Data Structure Using Linked Lists

Question

I am a mathematician attempting to become proficient with C++. At the moment I am learning about data structures. I am now writing a stack data structure using linked list from scratch.

I have tested my class that I wrote and everything seems to be working fine but I want to see if there are any bugs or some areas of the code I could improve on.

Here is the class:

    #ifndef Stack_h
#define Stack_h

template <class T>
class Stack {
private:
    struct Node {
        T data;
        Node* next;
    };
    Node* top;

public:
    // Constructors
    Stack() : top(nullptr){}                                                 // empty constructor
    Stack(Stack const& value);                                               // copy constructor
    Stack<T>(Stack<T>&& move) noexcept;                                      // move constuctor
    Stack<T>& operator=(Stack&& move) noexcept;                              // move assignment operator
    ~Stack();                                                                // destructor

    // Overload operators
    Stack& operator=(Stack const& rhs);
    friend std::ostream& operator<<(std::ostream& str, Stack<T> const& data) {
        data.show(str);
        return str;
    }

    // Member functions
    void swap(Stack& other) noexcept;
    bool isEmpty();
    int getSize();
    void push(const T& theData);
    void push(T&& theData);
    void pop();
    void show(std::ostream &str) const;
};

template <class T>
Stack<T>::Stack(Stack const& value) : top(nullptr) {
    for(Node* loop = value->data; loop != nullptr; loop = loop->next) {
        push(loop->data);
    }
}

template <class T>
Stack<T>::Stack(Stack<T>&& move) noexcept : top(nullptr) {
    move.swap(*this);
}

template <class T>
Stack<T>& Stack<T>::operator=(Stack<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

template <class T>
Stack<T>::~Stack() {
    while(top != nullptr) {
        pop();
    }
}

template <class T>
Stack<T>& Stack<T>::operator=(Stack const& rhs) {
    Stack copy(rhs);
    swap(copy);
    return *this;
}


template <class T>
void Stack<T>::swap(Stack<T> &other) noexcept {
    using std::swap;
    swap(top,other.top);
}

template <class T>
bool Stack<T>::isEmpty() {
    if(top == nullptr) {
        return true;
    }
    else {
        return false;
    }
}

template <class T>
int Stack<T>::getSize() {
    int size = 0;
    Node* current = top;
    while(current != nullptr) {
        size++;
        current = current->next;
    }
    return size;
}

template <class T>
void Stack<T>::push(const T &theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->next = nullptr;

    if(top != nullptr) {
        newNode->next = top;
    }
    top = newNode;
}

template <class T>
void Stack<T>::push(T&& theData) {
    Node* newNode = new Node;
    newNode->data = std::move(theData);
    newNode->next = nullptr;

    if(top != nullptr) {
        newNode->next = top;
    }
    top = newNode;
}

template <class T>
void Stack<T>::pop() {
    Node* temp;
    if(top == nullptr) {
        throw std::invalid_argument("The list is already empty, nothing to pop.");
    }
    temp = top;
    top = top->next;
    delete temp;
}

template <class T>
void Stack<T>::show(std::ostream &str) const {
    for(Node* loop = top; loop != nullptr; loop = loop->next) {
        str << loop->data << "\t";
    }
    str << "\n";
}


#endif /* Stack_h */

Here is the main.cpp file that tests the class:

#include <iostream>
#include "Stack.h"

int main(int argc, const char * argv[]) {



    ///////////////////////////////////////////////////////////////////////////////////
    ///////////////////////////// Stack Using Linked List //////////////////////////////////
    ///////////////////////////////////////////////////////////////////////////////////

    Stack<int> obj;
    obj.push(2);
    obj.push(4);
    obj.push(6);
    obj.push(8);
    obj.push(10);
    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Displaying Stack Contents---------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Pop Stack Element -------------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.pop();
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Get the size of stack -------------------";
    std::cout<<"\n--------------------------------------------------\n";
    std::cout << obj.getSize() << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"---------------Re-Add Poped Element---------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.push(10);
    std::cout << obj << std::endl;

    return 0;
}

Answer 1

General stuff

• In the copy constructor, the implementation starts to iterate over all the nodes, starting from value->data. I guess this is meant to be value.top.
• Still in the copy constructor, it pushes the values in reverse order (traversal of original: top to bottom; insertion in new Stack: bottom to top).
• The two above issues are also inherent in the copy assignment operator, as it uses the copy constructor internally.
• The body of isEmpty can be simplified to return top == nullptr;.

• Both variants of Stack<T>::push contain the following snippet:

  newNode->next = nullptr;
  
  if (top != nullptr) {
      newNode->next = top;
  }
  

  This can be simplified to newNode->next = top;

• The implementation is inconsistent in the usage of Stack<T> vs Stack.
• isEmpty and getSize can be marked const, as they don't modify the Stack object.
• #includes are missing for std::ostream, std::swap, std::move and std::invalid_argument.

Advanced stuff

Note: These require template meta programming. This might be a bit much for a beginner.

• push(T&&) could be disabled for types that aren't move-constructible by using SFINAE.
• Similar to above, push(const T&) could be disabled for non-copy-constructible types.
• Stack could use an emplace member function to construct objects in-place using perfect forwarding.

Performance

Since this class has a move constructor (and a move assignment operator), it seems to care about performance. However, the implementation of the move constructor makes unnecessary copies/assignments. Granted, the concerned objects are pointers, so they are cheap to copy, but it's still some overhead.

The move constructor first initializes top to nullptr (= 1 assignment).

Then it calls swap, which internally calls std::swap on both top pointers, which in turn will very likely boil down to a triangle swap (= 1 assignment to temp, 1 assignment from one top to the other top and 1 assignment from temp).

So there are 4 assignments in total. Compare this to:

Initialize top from other.top. (1 assignment)

Set other.top to nullptr. (1 assignment)

Only 2 assignments, and has the same results.

Other than that, just a general note: Linked lists, at least on modern processors, have generally worse performance than using contiguous memory (e.g. an array or a std::vector) because of prefetching, memory overhead and cache misses.

Memory management

Guideline R.11 from the C++ Core Guidelines discourages use of raw calls to new and delete in favor of using smart pointers. While there are some caveats if used carelessly (like stack overflow on recursive object destruction), they generally make code more robust, easier to use and leak-free.

Answer 2

#ifndef Stack_h
#define Stack_h

Your include guard is susceptible to collisions. Add differentiators that will generate keys that are more likely to be unique, like the the library name, author name, date created, or a guid.

---

    struct Node {
        T data;
        Node* next;
    };
    Node* top;

You have been writing other containers. Why not reuse them? Consider that a stack is just an abstract data type. That is, a stack is defined by its semantic behavior, Last In-First Out. Any container that maintains insertion order and allows access, insertions, and deletions from the same end can be modeled to be a stack. Read up on the adaptor pattern.

---

public:
    // Constructors
    Stack() : top(nullptr){}                                                 // empty constructor

When initializing data members with constant initializers, prefer in-class member initialization. i.e:

    Node* top{ nullptr };
    ...
    Stack() = default;

Keep comments crisp. Programmers looking at the code should already know that they are constructors. Reserve comments for stating intent, when you want to explain why something is being done and the code doesn't obviously state that intent.

---

    Stack(Stack const& value);
    Stack<T>(Stack<T>&& move) noexcept;
    Stack<T>& operator=(Stack&& move) noexcept;

Be consistent. Stack<T> vs Stack?

Use names to convey information. move suggests an action. Either other, that, or rhs would be better names to describe the other stack.

---

    Stack& operator=(Stack const& rhs);
    friend std::ostream& operator<<(std::ostream& str, Stack<T> const& data) {
        data.show(str);
        return str;
    }

Stack's typically only offer access to the top element. Do you really need to stream all elements?

As John Lakos says in "Large Scale C++ Software Design":

Latent usage errors can be avoided by ensuring that the .h file of a component parses by itself – without externally-provided declarations or definitions... Including the .h file as the very first line of the .c file ensures that no critical piece of information intrinsic to the physical interface of the component is missing from the .h file (or, if there is, that you will find out about it as soon as you try to compile the .c file).

Your file is missing the includes for std::ostream, std::swap, etc.

---

    bool isEmpty();
    int getSize();

If you want your functions to work with standard library facilities, consider using the same standard library names, i.e. empty(), size(). Otherwise, someone using your library will have to write customization points to be used with std::empty() and std::size().

If you would like to use these functions in a const-context (const Stack<T>), then specify them as const. They can also be specified as noexcept.

---

    void push(const T& theData);
    void push(T&& theData);

No emplace(Args&&... args)?

---

    void show(std::ostream &str) const;

Is show() supposed to be publicly accessible? Speaking of access, how do you access the top element of the stack?

---

template <class T>
Stack<T>::Stack(Stack const& value) : top(nullptr) {
    for(Node* loop = value->data; loop != nullptr; loop = loop->next) {
        push(loop->data);
    }
}

That for loop looks like a good candidate to abstract for reuse.

---

template <class T>
Stack<T>::Stack(Stack<T>&& move) noexcept : top(nullptr) {
    move.swap(*this);
}

template <class T>
Stack<T>& Stack<T>::operator=(Stack<T> &&move) noexcept {
    move.swap(*this);
    return *this;
}

You could just call swap(move);.

---

template <class T>
Stack<T>::~Stack() {
    while(top != nullptr) {
        pop();
    }
}

During destruction, the null check is done twice. What you really want to call is the unchecked part of pop(). Consider abstracting it into its own function and have both the destructor and pop() call that unchecked operation after each does its own check.

Stack<T>::~Stack() {
    while (top) {
        do_unchecked_pop();
    }
}

void Stack<T>::pop() {
    if (top) { throw ... }
    do_unchecked_pop();
}

void Stack<T>::do_unchecked_pop() {
    Node* tmp = top->next;
    delete top;
    top = tmp;
}

From here, you can abstract the while loop into a clear() member function and call that from the destructor.

---

template <class T>
bool Stack<T>::isEmpty() {
    if(top == nullptr) {
        return true;
    }
    else {
        return false;
    }
}

How about return top; for the body? top is a pointer and when converted to bool will return false when pointing at nullptr. It's redundant to compare to nullptr.

---

template <class T>
int Stack<T>::getSize() {
    int size = 0;
    Node* current = top;
    while(current != nullptr) {
        size++;
        current = current->next;
    }
    return size;
}

You traverse the link list every time you call for the size. That is expensive for large lists. Have you considered keeping a count data member that changes on inserts and deletions?

---

template <class T>
void Stack<T>::push(const T &theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    newNode->next = nullptr;

    if(top != nullptr) {
        newNode->next = top;
    }
    top = newNode;
}

template <class T>
void Stack<T>::push(T&& theData) {
    Node* newNode = new Node;
    newNode->data = std::move(theData);
    newNode->next = nullptr;

    if(top != nullptr) {
        newNode->next = top;
    }
    top = newNode;
}

You can remove some duplication here with adding a node to the front.

---

template <class T>
void Stack<T>::pop() {
    Node* temp;
    if(top == nullptr) {
        throw std::invalid_argument("The list is already empty, nothing to pop.");
    }
    temp = top;
    top = top->next;
    delete temp;
}

Declare variables as you need them and initialize them with a value.

---

See Container Requirements and Stack for what you are missing in regards to typedefs and operations.

---

As for your test file, use a testing framework (Catch2, GoogleTest, BoostTest). You shouldn't have to concern yourself with what is being returned but did it return what you expect. Reduce the cognitive load.

Also, follow the Beyonce Rule. If you want it, put a test on it. Every member should have a test.

Answer 3

I share most of hoffmale's review, but I want to insist on some points, including Memory Management, and the smart pointers.

General points

In your push(T const& theData) :

Node* newNode = new Node;
newNode->data = theData;
newNode->next = nullptr;

Here is a problem. When you use new Node, it will call the constructor of Node. Here, no constructor is specified, so it will be the default one which will be executed, and it consists of calling the constructor of each of its member. Constructor of T included. But just the next line, whatever the constructor did, you remove it by just copying theData.
You should instead use Node* newNode = new Node{theData,nullptr}; which we call the T copy constructor, instead of constructor+copy-assignment.
Moreover, I think that if T has no default constructor (by deleting it on purpose), the code should not compile (to be tested).

Smart Pointers

A smart pointer is a pointer which holds the ownership (either exclusive or shared) of an object. When the smart pointer is destroyed (in the case of an exclusive ownership) or when all smart pointers pointing the same object are destroyed (in shared ownership), the object is destroyed too.

Here, you have a stack. Each node is referred by exactly one pointer (its parent node, which can be the stack class). The node is destroyed when this pointer changes its content. Sounds like a perfect use for std::unique_ptr (<memory> header, c++11).

So your node class becomes :

struct Node {
    T data;
    std::unique_ptr<Node> next;
};

Then, your push function becomes :

template <class T>
void Stack<T>::push(const T &theData) {
    std::unique_ptr<Node> newNode(new Node {theData, nullptr}); // (1)
    if(top) { // (2)
        newNode->next = std::move(top); // (3)
    }
    top = std::move(newNode); // (4)
}

So, there are now four lines, let me explain what they do :

1. std::unique_ptr constructor, which takes the raw pointer as argument
2. implicit cast to boolean from unique_ptr checks if the pointer is not nullptr.
3. operator -> is still available. top is transfering his object to newNode->next. After this assignment, top now holds nullptr (because there is only one pointer which can refers to one object, in unique_ptr).
4. top now holds the new node, and newNode holds nullptr.

The main purpose of smart pointer is the absence of delete. So your pop function had this :

temp = top;
top = top->next;
delete temp;

and now it has :

top = std::move(top->next);

Voilà ! When top got assigned, its last object is destroyed before being actually assigned. No need for delete.

Notice that now, your destructor is trivial : it needs to do nothing.

~Stack() {}

Because top will be destroyed, which will destroy top->next which will destroy top->next->next, etc. At the end, every node is correctly destroyed.
As pointed by hoffmale, you should have a loop because the recursion can cause stack overflow if there are enough nodes.

tl;dr

Smart pointers are a gift from heaven. A unique_ptr has zero overhead so it should be used whenever possible. For more information on how to use them, please check the C++ Core Guildelines, R.* .