Stack implementation in C++ using linked list

Question

I am learning C++ and I made a simple stack class using a (reversed) linked-list to test my knowledge.

Are there any problems with the following code, or any suggestions to improve it?

I want to make sure I am getting things correct in the beginning so I don't make the same mistakes again in the future - especially memory management and avoiding leaks.

One thing to point out is that I included the implementation in the header file... I wouldn't normally do this but apparently there are problems when implementing methods with templates in .cpp files.

#ifndef TEST_STACK_H
#define TEST_STACK_H

#include <stdexcept>

template <class T>
class stack {

    struct node {
        T data;
        node* previous;

        node(T data, node *previous) : data(data), previous(previous) {}
    };

    node* head = nullptr;

    int size = 0;
    int max = -1; // -1 so isFull() == false when default constructor used

public:
    stack() = default;

    stack(int max) {
        if (max <= 0) throw std::out_of_range("stack size must be > 0");
        this->max = max;
    }

    ~stack() {
        node* n = head;

        while (n != nullptr) {
            node* previous = n->previous;
            delete n;

            n = previous;
        }
    }

    void push(const T &object) {
        if (isFull()) throw std::overflow_error("cannot push to a full stack");

        head = new node(object, head);
        ++size;
    }

    T pop() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

        T item = head->data;
        head = head->previous;

        --size;

        delete head;
        return item;
    }

    T peek() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
        return head->data;
    }

    int getSize() {
        return size;
    }

    bool isFull() {
        return size == max;
    }

    bool isEmpty() {
        return head == nullptr;
    }
};

#endif

Answer 1

Bug

Your main issue is memory management.

You did not implement the "Rule of Three" (you can google it).

The problem is that if you do not define the copy constructor or the assignment operator the compiler will generate these methods for you automatically. Under most conditions these generated methods work correctly. BUT when your class contains an "Owned" pointer they do not work.

Note: An "Owned" pointer is a pointer you are responsible for deleting.

{
    stack<int>   x;
    x.push(12);


    stack<int>   y(x);  // Copy constructor used.
                        // The default implementation does a shallow copy
                        // of each member from x into y.
                        // This means that x and y point at the same list.

}
// Here your destructor has destroyed the same list twice.
// This is a bug.

To fix this you need to define the copy constructor and assignment operator. But there is a nice pattern that allows you to define the assignment operator in terms of the copy constructor. Look up the "Copy And Swap Idiom".

You need to add the following to your class:

class stack
{
    // Stuff
    public:
        stack(stack const& rhs)
            : head(copyList(rhs.head))
            , size(rhs.size)
            , max(rhs.size)
        {}
        stack& operator=(stack const& rhs)
        {
            stack tmp(rhs);            // make a copy using copy constructor.
            swap(tmp);                 // swap the tmp and this object
            return *this;
        }
        void swap(stack& other) noexcept
        {
            using std::swap;
            swap(head, other.head);
            swap(size, other.size);
            swap(max,  other.max);
        }

    private:
        node* copyList(node* l)
        {
            if (l == nullptr) {
                return null;
            }
            return new node{l->data, copyList(l->previous)};
        }
    // STUFF
};

Your pop() has a bug. You delete the NEW head item before returning but leak the original head item.

T pop() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

    T item = head->data;
    head = head->previous;     // You just leaked the old head.
                               // You need to keep a pointer to the old head

    --size;

    delete head;               // So you can delete the old head here.
    return item;
}

Other Stuff

Design of pop()

You make your pop() method return the top value and remove it from the stack. This is fine if your T type is simple. But if T is a complex type there is no way to do this safely (and maintain "Strong Exception Guarantee"). So most implementations of stack split this into two separate functions. A top() that returns the top value and a pop() that simply removes the top value.

So I would rewrite this:

void pop() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

    node* old = head;
    head = head->previous;

    --size;
    delete old;
}
T const& top() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

    return head->data;
}

Return by reference

Your pop() and peek() return the result by value. This is OK for simple types of T (like integer). But if T is a complex object you are making a copy of this complex object. Instead you should return a reference to the object. If the user is doing somehting simple they can do the action without copying if they want to keep a copy they can make that decision and save the value in a local variable.

T peek()

// Change to:

T const& peek();   // Don't really need this if you have top()
                   // Or you could use peek instead of top()

But notice the const& as the return type. You are returning a reference to the object so no copy is made. If you need a local copy then you can save it like this:

int   val = x.top();
x.pop();

Answer 2

Updated Code

Changes (with the help of Martin):

• Added copy constructor and assignment operator overload
• Changed return type of peek() to const T& rather than T (this prevents unnecessary copying of data)
• Changed return type of pop() to void; it now only removes the top item rather than returning it on top. The user can call peek() and then call pop() to retrieve and then delete the item. This means we don't have to return T by value, and also maintains the "Strong Exception Guarantee".
• Fixed a bug in pop() where the new head is deleted rather than the old one

#ifndef TEST_STACK_H
#define TEST_STACK_H

#include <stdexcept>

template <class T>
class stack {

    struct node {
        T data;
        node* previous;

        node(T data, node *previous) : data(data), previous(previous) {}
    };

    node* head = nullptr;

    int size = 0;
    int max = -1; // -1 so isFull() == false when default constructor used

public:
    stack() = default;

    stack(int max) {
        if (max <= 0) throw std::out_of_range("stack size must be > 0");
        this->max = max;
    }

    // copy constructor

    stack(stack const& rhs) :
        head(copyList(rhs.head)),
        size(rhs.size),
        max(rhs.size) {}

    // assignment operator

    stack& operator = (stack const& rhs)
    {
        stack tmp(rhs);
        swap(tmp);

        return *this;
    }

    ~stack() {
        node* n = head;

        while (n != nullptr) {
            node* previous = n->previous;
            delete n;

            n = previous;
        }
    }

    void push(const T &object) {
        if (isFull()) throw std::overflow_error("cannot push to a full stack");

        head = new node(object, head);
        ++size;
    }

    const void pop() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

        node* old = head;
        head = head->previous;

        --size;
        delete old;
    }

    T peek() {
        if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
        return head->data;
    }

    int getSize() {
        return size;
    }

    bool isFull() {
        return size == max;
    }

    bool isEmpty() {
        return head == nullptr;
    }

private:
    void swap(stack& other) noexcept
    {
        using std::swap;
        swap(head, other.head);
        swap(size, other.size);
        swap(max,  other.max);
    }

    node* copyList(node* l)
    {
        if (l == nullptr) {
            return nullptr;
        }
        return new node{l->data, copyList(l->previous)};
    }
};

#endif