14
\$\begingroup\$

This is a working stack implementation using a linked list. I'm just curious to know if this is a good way of doing it. Any suggestions are welcome. Can we keep track of the number of elements in the stack using a count variable as used in the code?

#include <cstdlib>
#include<iostream>
using namespace std;

class node
{
 public:
    int data;
    node* next;
};

class StackusingList
{
public:
StackusingList(int max)
{
    top = NULL;
    maxnum = max;
    count=0;
}

void push(int element)
{
    if(count == maxnum)
            cout<<"stack is full";
    else
    {
        node *newTop = new node;
        if(top == NULL)
        {       
            newTop->data = element;
            newTop->next = NULL;
            top = newTop;
            count++;
        }
        else
        {
            newTop->data = element;
            newTop->next = top;
            top = newTop;
            count++;
        }
    }
}

void pop()
{
    if(top == NULL)
            cout<< "nothing to pop";
    else
    {
        node * old = top;
        top = top->next;
        count--;
        delete(old);
    }
}
void print()
{
    node *temp;
    temp = top;
    while(temp!=NULL)
    {
        cout<<temp->data<<",";
        temp=temp->next;
    }
}
private:
    node *top;
    int count; //head
    int maxnum;
    int stackData;      
};

int main(int argc, char** argv) {   
    StackusingList *sl = new StackusingList(5);
    sl->push(1);
    sl->push(2);
    sl->push(3);
    sl->push(4);
    sl->push(5);
    sl->push(6);

    sl->pop();
    cout<<"new stack\n";
    sl->print();

    return 0;
}
\$\endgroup\$
10
\$\begingroup\$
  • At some point, I'd recommend using template here. This will allow you to store any date type, not just ints, in your structure.

  • It'd be better to define node as a struct inside StackusingList as private. In your current implementation, node's fields are not hidden because they are all made public.

    class LinkedList
    {
    private:
        struct Node
        {
        };
    
    public:
    
    };
    
  • Prefer nullptr to NULL if you're using C++11.

  • StackusingList() should be an initializer list:

    StackusingList(int max) : top(NULL), maxnum(max), count(0) {}
    
  • count should be of type std::size_t.

  • In both push() and pop(), you'll need to return if the stack is full or empty respectively. Otherwise, the function will continue to execute, defeating the purpose of the check.

  • print():

    // no data members are being modified,
    //   so make this const
    void print() const
    {
        // could just be initialized
        // the asterisk is commonly
        //   put next to the type in C++
        node* temp = top;
    
        while (temp)
        {
            cout << temp-> data << ",";
            temp = temp->next;
        }
    }
    
  • Watch out:

    StackusingList *sl = new StackusingList(5);
    

    You do not call delete with this new, thereby causing a memory leak! Always call delete properly with every new.

    At the end of main() before the return:

    delete s1;
    

    Beyond that, you really don't need to use new here. It's only necessary with the nodes, which you're already doing. It's best to just avoid manual allocation/deallocation as much as possible.

  • stackData isn't used anywhere (and doesn't have a clear meaning), so just remove it.

  • You're missing a few useful public member functions:

    std::size_t size() const { return count; } // put into header
    

    bool empty() const { return count == 0; } // put into header
    

    template <typename T>
    T StackusingList<T>::top() const { return top->data; }
    
  • There is no destructor! You're allocating new nodes, so you have to define the destructor to properly delete them:

    StackusingList::~StackusingList()
    {
        node* current = top;
    
        while (current)
        {
            node* next = current->next;
            delete current;
            current = next;
        }
    
        top = NULL;
    }
    

    With the destructor defined, you'll need to satisfy The Rule of Three. This is also important because the default copy constructor and assignment operator will perform a shallow copy of top. This means that the pointer itself will be copied instead of just the data at that pointer. This will cause problems if you try to copy list objects or initialize new ones with existing ones.

\$\endgroup\$
  • \$\begingroup\$ @Jamal quick question why you hide the node in the private class ? \$\endgroup\$ – Lamar Oct 16 '15 at 19:24
  • \$\begingroup\$ @Lamour: It's because it shouldn't be exposed to the public interface. \$\endgroup\$ – Jamal Oct 16 '15 at 20:42
4
\$\begingroup\$

I'm just curious to know if this is a good way of doing it?

No.

Any suggestions are welcome.

Hold On.

Can we keep track of the number of elements in the stack using a count variable as used in the code?

Yep.

Basically your memory management is broken.
When you push elements on you create them with new and when you pop elements off you delete them. But what happens when the stack object goes out of scope? Anything still left in the stack is now leaked.

Also the use of a maximum count in the constructor suggests that you should be allocating a single piece of storage once on construction to store all the values. The point of using a linked list is to allow the list to grow dynamically. It would be a better idea to just create a storage area and keep track of how full it is (if you are allowed to use std::vector in your assignment this does all the hard work for you).

From this:

int main(int argc, char** argv) {   
    StackusingList *sl = new StackusingList(5);

One assumes you have a Java background.
If you don't need your object to live beyond the time span of the function then you don't need use new. What you need is just create a local object.

int main(int argc, char** argv) {   
    StackusingList    sl(5);

This variable is created locally. It is destroyed when the function terminates. If you had written it correctly the destructor would then clean up any internal memory it had allocated.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.