1

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; };
Improve this question
8
  • 2
    <iostream.h> is wrong -- you should be using <iostream> instead. Also, this smells like homework -- otherwise you'd be using std::stack<t>. Commented Aug 28, 2010 at 23:57
  • Not homework; I just needed some way to learn memory management. Commented Aug 28, 2010 at 23:59
  • 2
    @eric: In production C++ code, you almost never want to be managing memory manually. You should delegate that responsibility to STL containers, std::auto_ptr, some form of shared_ptr, or some form of scoped_ptr. Commented Aug 29, 2010 at 0:02
  • Ok. I'll look into that. Commented Aug 29, 2010 at 0:04
  • 1
    Two style suggestions: if you initialize top to null in the constructor, you don't have to handle the empty stack case separately in push(). Also, you can implement the destructor in terms of pop(), cutting out more duplicate code. Commented Aug 29, 2010 at 0:20

4 Answers 4

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Er... I'm not sure. I tested it with ints and chars.. Anyways, thank you!
@eric: That's because char is convertible to int. The error is in your pop function.
@Martin: That was just an error in the code (int val = n->value; should have been T val = n->value;).
5

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.

Improve this answer

1 Comment

Agreed -- should probably be throwing an exception here instead. +1.
3

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; };
Improve this answer

2 Comments

It would be nice to null Node::next in the destructor.
@C Johnson: Why? its a complete waste of time as after the destructor the variable does not exist; and it does not add clarity or safety.
0

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;
Improve this answer

2 Comments

Well, your size calculation will work, so no -1 from me. But the performance of that is really bad: it's O(n). So if someone used getSize() as exit condition in a for loop performance would become O(n*n) ... like when people use strlen(): simple mistake, horrible performance ... try not to encourage that when building an API.
My answer is relating to OP's question i.e. memory management. You are right of course about the performance

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.