Linked list stack implementation

Question

I have used the following code for a stack implementation. The top keeps track of the topmost node of the stack. Now since top is a data member of the node function, each node created will have a top member, which ideally we wouldn't want.

1. Is this good approach to coding?
2. Will making top as static make it a better coding practice?
3. Should I have a global declaration of top?

#include<iostream>
using namespace std;
class node
{
    int data;
    node *top;
    node *link;
    public:
    node()
    {
       top=NULL;
       link=NULL;
    }
    void push(int x)
    {
        node *n=new node;
        n->data=x;
        n->link=top;
        top=n;
        cout<<"Pushed "<<n->data<<endl;
    }
    void pop()
    {
        node *n=new node;
        n=top;
        top=top->link;
        n->link=NULL;
        cout<<"Popped "<<n->data<<endl;
        delete n;
    }
    void print()
    {
        node *n=new node;
        n=top;
        while(n!=NULL)
        {
            cout<<n->data<<endl;
            n=n->link;
        }
        delete n;
    }
};


int main()
{
    node stack;
    stack.push(5);
    stack.push(7);
    stack.push(9);
    stack.pop();
    stack.print();
}

Any other suggestions welcome. I have also seen codes where there are two classes, where the second one has the top member. What about this?

Answer 1

1. In the pop and the print function, the new node seems unnecessary, since the next line modifies the pointer to point to the top. It could be simply

   node *n = top;
   

2. The delete n; also looks superfluous in the print since n will always be NULL there.

3. If I'm right making top as static or global would result that you can't have more than one stack in an application. Linked lists usually have two classes: one is a Node which stores a reference to the next node and the data, and the second is a LinkedList class which stores the head and the implementation of the push, pop, etc. methods. You can see an example in this answer.

4. Take care of the boundary cases. Calling pop on an empty stack gives a segmentation fault error. I suppose that's not the best error handling method :)

Answer 2

I'd normally structure the code more like this:

template <class T>
class stack { 
    class node {
        T data;
        node *next;

        node(T const &i, node *n=NULL) : data(i), next(n) {}
    };

    node *top;

public:

    void push(T const &in) {
        top = new node(in, top);
    }   

    stack() : top(NULL) {}
};

With this general structure, you get only one top per stack (instead of one in each node), but you can still create as many stack objects as you want (something that won't work if you make top a static or global).

I've left pop un-implemented for the moment because it's really somewhat tricky to get correct. In particular, the typical definition of pop that removes the top item from the stack and returns its value can't be made exception safe unless you place some fairly tight restrictions on the data that can be stored. The stack class in the standard library takes the route of separating the two actions -- one function to get the value of the top-most item, and a second to remove the top item from the stack.

It's not at all clear to me whether you'd really prefer to do that, or stick with a design that's easy to use, but may be unsafe.

I see a couple of problems with your print. First of all, it leaks memory -- it allocates an object, and attempts to delete it, but before the delete, the pointer has been set to NULL, so the delete is a nop. I think that's a direct consequence of the second problem: it's really quite a bit more complex than necessary. I'd normally use something closer to this:

void print() { 
    for (node *p=top; p!=NULL; p=p->next)
        std::cout << p->data << "\n";
}

One more possibility to consider would be to implement the stack as a linked list of nodes, but have each node capable of holding a number of items instead of just one. This can reduce the overhead of the pointers quite a bit (e.g., as your code is written right now, in a typical implementation you have twice as much space devoted to pointers as to the data).

Answer 3

One alternative to having a separate class is to use the return value. For example:

Node * push(int x)
{
    node *top = new node;
    top->data = x;
    top->link = this;
    return top;
}

Then:

stack = stack->push(5);
stack = stack->push(7);
stack = stack->pop();

A separate stack class is probably easier to work with, but this is an option.

Additionally, a linked list is a poor choice of data structure for a stack. In almost all circumstances, a resizable array is a much better choice.

Answer 4

By the time I had this code together lots of people have made similar comments.

Anyway, here is my attempt at refactoring your code.

Main changes:

1. templated type - more flexible.
2. cleanup mechanism - destructor.
3. general cleanup - lots of new where not required.

Looks like this:

#include<iostream>

using namespace std;

template<typename T>
class node
{
   T data;
   node *top;
   node *link;

   public:
   node()
   {
     top=NULL;
     link=NULL;
   }
   void push(const T& x)
   {
       node *n=new node;
       n->data=x;
       n->link=top;
       top=n;
       cout<<"Pushed "<<n->data<<endl;
   }
   void pop()
   {
      node *n=top;
      top=top->link;
      n->link=NULL;
      cout<<"Popped "<<n->data<<endl;
      delete n;
   }
   void print()
   {
      node *n= top;
      while(n!=NULL)
     {
         cout<<n->data<<endl;
         n=n->link;
     }
   }
   ~node() {
      if(top) {
         node* current = top;
         node* next = 0;
         while (current != NULL) {
            next = current->link;
            delete current;
            current = next;
         }
      }
   }
};


int main()
{
   node<int> stack;
   stack.push(5);
   stack.push(7);
   stack.push(9);
   stack.pop();
   stack.print();
   return 0;
}

See @Loki's comment regarding The Rule of Three. In view of that here is my flawed second attempt:

#include<iostream>

using namespace std;  //should not be in header file - just to remove std:: below

template <class T>
class stack { 
    class node {
    public:
       T data;
       node* next;

       node(T const &d) : data(d), next(0) {}

       node() : data(0), next(0) {}
    };

    node *top;

  public:
    stack() : top(0) {}

    stack(const stack& s) {
        node* nextnode = s.top;
        while(nextnode != 0)
        {
           node* newnode = new node;
           newnode->data = nextnode->data;
           newnode->next = nextnode->next;
           nextnode=nextnode->next;
           top = newnode;
           cout<<"copy constructed "<< newnode->data <<endl;
        }
    }

    stack& operator=(const stack& s) {
        node* nextnode = s.top;
        while(nextnode != 0)
        {
           node* newnode = new node;
           newnode->data = nextnode->data;
           newnode->next = nextnode->next;
           top = newnode;
           cout<<"operator = "<< newnode->data <<endl;
           delete nextnode;
           nextnode=nextnode->next;
        }        
    }

    ~stack() {
       if(top) {
          node* current = top;
          node* next = 0;
          while (current != 0) {
             next = current->next;
             cout << "dtor deleting node " << current->data << endl;
             delete current;
             current = next;
          }
       }
    }

    void push(const T& item)
    {
        node *n=new node;
        n->data=item;
        n->next = top;
        top=n;
        cout<<"Push new'd node "<< n->data << endl;
    }
    void pop()
    {
        node *n=top;
        top=top->next;
        n->next=NULL;
        cout<<"Pop delete'd node "<< n->data << endl;
        delete n;
    }
    void print()
    {
        node *n= top;
        while(n != 0)
        {
            cout<<n->data<<endl;
            n=n->next;
        }
    }
};


int main()
{
   {
    stack<int> mystack;
    mystack.push(5);
    mystack.push(7);
    mystack.push(9);

    mystack.pop();
    mystack.print();

    //test of copy ctor
    stack<int> second(mystack);
    //test of assign operator
    stack<int> third = mystack;

   }
   return 0;
}