Have I managed the memory correctly here? (simple C++ stack)

Question

I'm a complete noob with dynamically allocated memory. Will this have a memory leak or any other memory problem?

#include <iostream.h>

template <class T> class stack
{
         struct node
         {
                T value;
                node* next;
         };

         public:
                stack()
                {
                       size = 0;
                }

                ~stack()
                {
                       while(size > 0)
                       {
                           node *n = top->next;
                           delete top;
                           top = n;
                           size--;
                       }
                }

                void push(T value)
                {
                     node *n = new node;
                     n->value = value;

                     if(size == 0)
                     {
                          top = n;
                     }
                     else
                     {
                         n->next = top;
                         top = n;
                     }

                     size++;
                }

                T pop()
                {
                       if(size<1)
                       {
                            std::cerr<<"Stack underflow"<<endl;
                            exit(0);
                       }
                       else
                       {
                           node* n = top;
                           int val = n->value;
                           top = n->next;

                           delete n;
                           size--;

                           return val;
                       }
                }

                int getSize()
                {
                    return size;
                }

        private:
                int size;
                node *top;
};

Answer 1

I don't see any memory management errors -- but I do see several other kinds of errors. For example, what happens when T is something other than int? :)

Also, implementing a stack as a linked list is wasteful and will perform relatively poorly when compared to a deque or vector implementation like that used by std::stack.

Answer 2

You missed the copy constructor/assignment operator of Stack.

When you create objects of Stack::Node you do not always initialization the next member. Write constructor destructor for stack node and everything else becomes simple.

#include <iostream.h>

template <class T> class stack
{
         /*
          * The stack object contains a RAW pointer (top)
          * So when the object is copied with either copy constructor or
          * assignment operator when need to handle that fact. The simplist way
          * to handle is to make sure it can not happen. To do this make them
          * private (You do not need to define them as they can't be used).
          */
         Stack(Stack const&);            // Not defined
         Stack operator=)(Stack const&); // Not defined

         struct Node
         {
                // Initialize Node
                Node(Node* n, T v)
                  :next(v)
                  ,value(v)
                {}
                ~Node() // Destroy whole chain.
                {    delete next;
                }
                // Data
                T     value;
                Node* next;
         };

         public:
                stack()
                   :size(0)
                   ,top(NULL)
                {}

                ~stack()
                {
                    /// destructor is now simple
                    delete top;
                }

                void push(T value)
                {
                   /// As is the push.
                     top  = new node(top, value);
                     ++size;
                }

                T pop()
                {
                    /// The pop is just the same.
                       if(size<1)
                       {
                            std::cerr<<"Stack underflow"<<endl;
                            exit(0);
                       }
                       else
                       {
                           node* n   = top;
                           T     val = n->value;
                           top       = n->next;
                           n->next   = NULL;    // Set to NULL to stop the delete chaining.

                           delete n;
                           size--;

                           return val;
                       }
                }

                // Make this method a constant.
                // As it does not change the object.
                int getSize() const
                {
                    return size;
                }

        private:
                int size;
                node *top;
};

Answer 3

In addition to the other excellent answers, one more note:

if(size<1)
{
    std::cerr<<"Stack underflow"<<endl;
    exit(0);
}

I would suggest thinking about either an assert or an exception here. exit is a bit rash, but if you decide to exit, do not exit with 0: that typically indicates success, which is the last thing you want in an error.

Answer 4

a few other tips:

instead of simulating the stack internally just use a normal list where you have a pointer to the first and last element of the list, there is no need to mimic a stack internally as long as you provide the push/pop functionality.

i would also skip the 'size' member altogether, instead just count the nodes in the list. this way you don't need to keep the size counter and the list synchronized. Just make sure you initialize the pointers to NULL. calculating size would then look something like:

for(Node* p=first; p!=NULL; p=p->next) ++size;