Memory leak in stack

Question

I'm implementing a stack by C++ and here I think it has memory leakage problem: in Stack::peek() and Stack::pop(), where I created heap space and returned pointer to function caller.

Users who call these two functions may perform deletion on returned pointer, which will recycle heap space once done. I am wondering what is a better approach to my current leakage prone approach.

Header file:

// this is the header file of stack data structure.

#ifndef MY_STACK_H
#define MY_STACK_H

class Node 
{
private:
    int number;
    Node * next;

public:
    Node(){number = 0; next = NULL;}

    Node(int initialNumber, Node * initialNext = NULL)
    {
        number = initialNumber;
        next = initialNext;
    }

    // copy constructor
    Node(Node & copyFromNode) 
    {
        this->number    =   copyFromNode.getNumber();
        this->next      =   copyFromNode.getNext();
    }


    // setters & getters
    int getNumber() {return number;}
    Node * getNext()    {return next;}
    void setNumber(int newNumber)   {number = newNumber;}
    void setNext(Node * newNext)    {next = newNext;}
};

class LinkedList
{
private:
    Node * head;

public:
    LinkedList(){head = NULL;}

    // very similar to Stack::push()
    void addFirst(Node *newNode)
    {
        newNode->setNext(head);
        head = newNode;
    }

    // somehow similar to Stack::pop()
    void deleteFirst()
    {
        if (head == NULL)
            return;
        else
        {
            Node * temp = head;
            head = head->getNext();
            delete temp;
        }
    }

    bool isEmpty()      {return (head == NULL);}
    Node * getHead()    {return head;}

    // there is no setter to head 
    // since head should be maintained by addFirst() & deleteFirst() only.
};

class Stack 
{
private:
    Node * top;
    LinkedList ll;
public:
    Stack(){top = NULL; }

    // push new node to the stack
    // new node will become the new top of stack
    void push(Node * newNode);

    // it checks if the stack is empty or not. 
    bool isEmpty();

    // it copies the top node on stack,
    // without deleting it. 
    Node * peek();

    // it copies the top node on stack, 
    // and deletes the node from stack. 
    Node * pop();
};

#endif

.cpp file:

// implementation for the stack


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

using namespace std;

void Stack::push(Node * newNode)
{
    ll.addFirst(newNode);
    top = ll.getHead();
}

bool Stack::isEmpty()
{
    if(top == NULL)
        return true;
    else 
        return false;
}

Node * Stack::peek()
{
    // make a copy, erase next link and return 
    // copy is made by calling copy construtor
    Node * copy = new Node(*top);   // ?? asks for reference but pointer is given

    return copy;
}

Node * Stack::pop()
{
    if (isEmpty())
        return NULL;
    else
    {
        Node * copy = new Node(*top);
        ll.deleteFirst();
        top = ll.getHead();
        return copy;
    }
}

int main()
{
    Stack stack;

    Node * nd1 = new Node(100);
    Node * nd2 = new Node(200);

    // test push()
    stack.push(nd1);
    stack.push(nd2);

    // test isEmpty()
    cout<<"Test: isEmpty(): "<< stack.isEmpty()<<endl;


    // test peek()
    cout<<"Test: peek(): "<<stack.peek()->getNumber()<<endl;


    // test pop()
    cout<<"Test: pop()"<<stack.pop()->getNumber()<<endl;
    cout<<"Test: pop()"<<stack.pop()->getNumber()<<endl;

    cout<<"Test: isEmpty(): "<<stack.isEmpty()<<endl;

    return 0;
}

Answer 1

Don't allocate nodes until you really need to.

LinkedList should not expose that it has nodes. addFirst should take an int to be stored in the node and getHead should return the value in the head node.

    void addFirst(int number )
    {
        Node* newNode = new Node();
        newNode->setNumber(number);
        newNode->setNext(head);
        head = newNode;
    }
    int getHead()    {return head->number;}

Same in stack don't expose that it deals in nodes and don't let calling code access them. That way you have more control over the lifetimes.

Answer 2

Don't use NULL unless you have to

Some IDEs will refuse to compile your code unless you include <cstdlib> so that NULL is available. If you compile using a C++ compiler using latest standards, you could use nullptr instead, since it is a language construct in those versions and does not require including anything.

Minor improvements

//bool Stack::isEmpty()
//{
//    if(top == NULL)
//        return true;
//    else
//        return false;
//}

bool Stack::isEmpty()
{
    return top == nullptr;
}

and

//Node * Stack::pop()
//{
//
//    if (isEmpty())
//        return NULL;
//    else
//    {
//        Node * copy = new Node(*top);
//        ll.deleteFirst();
//        top = ll.getHead();
//        return copy;
//    }
//}

Node * Stack::pop()
{
    if (isEmpty())
    {
        return nullptr;
    }

    Node * copy = new Node(*top);
    ll.deleteFirst();
    top = ll.getHead();
    return copy;
}

Alternative implementation

It's not difficult to devise a generic stack:

my_stack.h

#ifndef MY_STACK_H
#define MY_STACK_H

#include <iostream>
#include <stdexcept>
#include <vector>

template<typename T>
class MyStack {

    std::vector<T> storage;
    void check_not_empty()
    {
        if (storage.empty())
        {
            throw std::runtime_error{"Peeking from an empty stack."};
        }
    }

public:
    void push(const T& element)
    {
        storage.push_back(element);
    }

    void pop()
    {
        check_not_empty();
        storage.pop_back();
    }

    const T& peek() const
    {
        check_not_empty();
        return storage[storage.size() - 1];
    }

    size_t size()
    {
        return storage.size();
    }

    bool is_empty()
    {
        return storage.empty();
    }

    friend std::ostream& operator<<(std::ostream& os, const MyStack<T>& stack)
    {
        os << "[";
        std::string separator = "";

        for (size_t i = 0; i != stack.storage.size(); ++i)
        {
            os << separator << stack.storage[i];
            separator = ", ";
        }

        return os << "]";
    }
};

#endif

main.cpp

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

using namespace std;

int main()
{
    MyStack<int> stack;

    cout << stack << endl;

    for (int i = 1; i <= 5; ++i)
    {
        stack.push(i);
        cout << stack << endl;
    }

    while (!stack.is_empty())
    {
        stack.pop();
        cout << stack << endl;
    }
}

Answer 3

The other answers bring up good points, but, architecturally, the problem is that your linked list acquires control of Nodes and offers no way to relinquish it. Think about it: in deleteFirst, you delete your old list head , but how do you know that head was heapalloc'd in the first place?

Consider the following:

void example(void)
{
    LinkedList ll;
    Node n(5, nullptr);
    ll.addFirst(&n);
    ll.deleteFirst();
 }

Now you're going todelete a portion of the stack.

Instead, deleteFirst should remove and return the head, instead of deleting it. Then the consumer can delete it as necessary (or not). Then a regular user can write something like

void example(void)
{
    LinkedList ll;
    ll.addFirst(new Node(5, nullptr));
    delete ll.deleteFirst();
 }

and my example above compiles. So how do we implement this?

Node *deleteFirst(void)
{
    Node *const temp(head);
    if(head)
    {
        head = head->getNext();
    }
    return temp;
 }

At this point, you may want to rename deleteFirst; for the sake of fidelity to the problem, I shan't. Now you can write your stack as

Node &Stack::peek(void)
{
    return *top;
}
Node *Stack::pop(void)
{
    return isEmpty() ? nullptr : ll.deleteFirst();
 }

Answer 4

You say your problem is that you fear that the user may not delete the node once popped. There are many levels at which you may do something.

Get your resource management straight

Have a look at unique_ptr. A unique_ptr represents a unique owner of a resource, responsible for freeing the resource. It may not be copied, only moved. In your case, when popping, you want to give the ownership back to the user, have popreturn a unique_ptr<Node> by value. Reserve plain pointers as non-owners (a.k.a. observers) of the resource.

All your memory management problems will disappear unless the user explicitly does something dangerous. The dangerous will be made verbose.

If you want a quick look at resource management in C++11 and later, you may have a look at https://stackoverflow.com/a/28826952/2071258 (this is an answer of mine)

Fix your interface. Do not expose the nodes

The fact that there are Nodes is purely an implementation detail, worse, it fails to hide the fact that your Stack is implemented over a LinkedList (since Node belongs to LinkedList). Instead of returning a pointer to a node when popping, return a value. By value, since the node, containing the value, disappears.