4
\$\begingroup\$

Please review my code and help me to improve it. I have written this code using template. Can I use more C++11? Is using top in this code is necessary?

#include <iostream>


template<class T>
class Stack{
 struct Node{
 T data;
 Node *next;
 Node(T val):data(val),next(nullptr) {}
 };
 Node *head;
 int top;

 public:
     Stack(){
     top=-1;
     head=nullptr;
     }
    ~Stack();
     bool stack_empty();
     void push(T);
     T pop();

     void display(std::ostream& out = std::cout) const
     {
       Node *node=head;
       while(node!=nullptr){
        out<<node->data<<" ";
        node=node->next;
       }
     }
};
template<class T>
bool Stack<T>::stack_empty(){
  if(top==-1)
    return true;
  else
    return false;
}

template<class T>
void Stack<T>::push(T val){

  if(top>=-1){
    top++;
    Node *node=new Node(val);
    Node *tmp=head;
    if(tmp==nullptr) head=node;
    else{
        while(tmp->next!=nullptr)
            tmp=tmp->next;
        tmp->next=node;
    }
  }
  else
    std::cout<<"Overflow"<<std::endl;
}

template<class T>
T Stack<T>::pop(){
  if(stack_empty()==true)
    std::cout<<"Underflow"<<std::endl;
  else{
    top--;
    Node *node=head;
     while(node->next!=nullptr){
        node=node->next;
     }
    return node->data;
  }
}

template<class U>
std::ostream & operator <<(std::ostream& os, const Stack<U>& s){
s.display(os);
return os;
}

template<class T>
Stack<T>::~Stack(){
Node *tmp=nullptr;
  while(head){
    tmp=head;
    head=head->next;
    delete tmp;
  }
  head=nullptr;
}
int main()
{
 Stack<int> stack1;

 stack1.push(3);
 stack1.push(4);
 stack1.push(11);
 stack1.push(30);
 std::cout<<stack1<<std::endl;
 std::cout<<stack1.pop()<<std::endl;
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

Dont use if to test and return bool

  if(top==-1)
    return true;
  else
    return false;

This is easier to write as:

  return top == -1;

Overflow

  if(top>=-1){
      // STUFF
  }
  else
    std::cout<<"Overflow"<<std::endl;

Is top being -1 really overflow? Would not overflow be when you ran out of memory for list items. Especially since there is not interface that allows you to get the size of the stack.

Also I don't expect a diagnostic message. If something fails to happen its an error (by that I mean exception). If you fail to push the code that called push needs to know that the operation failed otherwise it will keep on doing what it is doing. The best way to indicate to the calling code something went wrong is an exception.

Design

You push and pop to the back of the list. Why not push and pop from the front of the list then you will never need to traverse the list to find the item.

Bug

When you pop, you don't actually remove the item from the list (or delete it). So poping gives you the last value but does nto remove it thus it will continue to give you the last item.

Efficiency

Checking for underflow/overflow. Sure this is good practice. But what about code were I know it is not going to under/over-flow. Do I need to check then? In most C++ code effeciency is paramount and you usually provide unchecked versions for situations where the check is not needed.

Stack   s;
// Fill stack

while(!s.empty())
{
     std::cout << s.pop();   // Does this pop need to be checked.
                             // We have already done a manual check
                             // to make sure that a pop() is valid
                             // by calling empty() first.
}

Note: There is no issue with having both a checked and unchecked version of a call. Lookat std::vector<> and operator[] Vs at().

Minor Things

The call to empty should be const:

 bool Stack<T>::stack_empty() const
                              ^^^^^

Easier to declare the operator<< as a friend then you don't need to worry about the template declaration.

template<class U>
std::ostream & operator <<(std::ostream& os, const Stack<U>& s){
    s.display(os);
    return os;
}

Put it inside the class and mark as friend:

    friend std::ostream& operator<<(std::ostream& os, Stack const& s) {   
        s.display(os);
        return os; 
    };  

Revised Version

#include <iostream>


template<class T>
class Stack{
    struct Node{
        T data;
        Node *next;
        // This is the standard constructor
        // Where you copy the `val` into the node.
        Node(Node* next, T const& val)
            : data(val)
            , next(next)
        {}  
        // This is the move constructor
        // It moves the content of `val` into the node. For
        // types like vectors this is much more efficient as it
        // simply means copying three (or so) pointers and thus
        // transferring the internal containers without the cost
        // of copying all the elements in the vector.
        Node(Node* next, T&& val)
            : data(std::move(val))
            , next(next)
        {}  
        // This is an emplace constructor.
        // Rather than passing a `T` into the node you pass all the
        // parameters need to construct a `T` then create the T
        // in place as the node object is constructed.
        template<typename... Args>
        Node(Node* nect, Args&&... args)
            : data(std::forward<Args>(args)...)
            , next(next)
        {}  
    };  
    Node*     head;

    public:
    Stack()
        : head(nullptr)
    {}  
    // Disable the copy semantics as the default version does not
    // work when you have an owned RAW pointer in your class (like head).
    Stack(Stack const&)            = delete;
    Stack& operator=(Stack const&) = delete;
    ~Stack()
    {   
         // Reclaiming all the nodes.
         for(Node* next; head != nullptr; head = next)
         {   
             next = head->next;
             delete head;
         }   
    }   
    bool empty() const
    {   
        return head == nullptr;
    }   
    // Pass a reference to a value and use it to create a node with a copy.
    void push(T const& value)
    {   
        head = new Node(head, value);
    }  
    // Pass an r-value reference to a value and use it to create a node with a move. 
    void push(T&& value)
    {   
        head = new Node(head, std::move(value));
    } 
    // Pass a reference to set of parameters that can be used to
    // construct a T object in place. This is know as perfect forwarding.  
    template<typename... Args>
    void push(Args&&... args)
    {   
        head = new Node(head, std::forward<Args>(args)...);
    }   
    // pop a value from the head node
    // delete and remove the head node.
    T pop()
    {   
        Node* tmp   = head;
        head = head->next;
        T result = std::move(tmp->data);
        delete tmp;
        return result;
    }   
    // Print a stack.
    void display(std::ostream& out = std::cout) const
    {   
        for(Node* loop = head; loop != nullptr; loop = loop->next)
        {   
            out << loop->data << " ";
        }   
    }   
    // Implement the stream operators for Stack
    friend std::ostream& operator<<(std::ostream& os, Stack const& s)
    {   
        s.display(os);
        return os; 
    }
};

int main()
{
    Stack<int> stack1;

    stack1.push(3);
    stack1.push(4);
    stack1.push(11);
    stack1.push(30);
    std::cout<<stack1<<std::endl;
    // No need to check pop()
    // I know there are four items in the stack
    // If a push had failed it would have thrown an exception.
    std::cout<<stack1.pop()<<std::endl;
}
\$\endgroup\$
  • \$\begingroup\$ Why do you handle T&& and const T& separately? \$\endgroup\$ – Deduplicator Aug 1 '17 at 17:28
  • \$\begingroup\$ Habbit. I should probably stop that. Can I pass a const object to a && bind point? \$\endgroup\$ – Martin York Aug 1 '17 at 18:12
  • \$\begingroup\$ If it's a forwarding-reference one, sure. That's the magic of them. \$\endgroup\$ – Deduplicator Aug 1 '17 at 18:23
2
\$\begingroup\$

You leak every single node you pop. You need to delete the node.

You should add move and emplace push overloads. So that non-copyable T can be stored.

you check against "overflow" by testing top is less than -1. However signed overflow is undefined behavior and if you ever had more than 2 billion items in your stack you probably ran out of ram earlier. You can check if the stack is empty by testing if head is nullptr. So top isn't really necessary.

For every operation you seek the end of the stack, that is not necessary at all.

template<class T>
void Stack<T>::push(T val){
    top++;
    Node *node=new Node(val);
    node->next = head;
    head=node;
}

template<class T>
T Stack<T>::pop(){
  if(stack_empty()==true)
    std::cout<<"Underflow"<<std::endl;
  else{
    top--;
    Node *node=head;
    head = node->next;
    T tmp = std::move(node->data);
    delete node;
    return tmp;
  }
}
\$\endgroup\$
  • \$\begingroup\$ I think there will be no case of overflow because we are using linked list and it can change its size dynamically \$\endgroup\$ – coder Jul 31 '17 at 14:52
  • \$\begingroup\$ @coder, on successful push you increment top, it is an int, which can overflow, which leads to undefined behavior. Though the contents of the list will remain the same. \$\endgroup\$ – Incomputable Aug 1 '17 at 4:21
0
\$\begingroup\$

Well, let's deal with the overarching concern first:

Why do you implement the stack completely new from the ground up?

I'm sure you already have data-structures allowing you to insert and remove elements. Adapt one of them! For bonus points, allow the user to override which one you adapt.


Now, let's look at your code and what you can improve:

  1. Your indentation is haphazard. Please fix it, preferably before showing your code to anyone else. Also, consider surrounding binary operators with space, and having exactly one after a comma. Proper code-formatting considerably helps readability.

  2. Consider putting the next-pointer first in Node. It's potentially slightly more efficient.

  3. Remove the constructor from Node and use aggregate-initialization. That also allows you to construct a pushed value in-place. All else being equal, be brief.

  4. You should not need top. Just insert and remove at the front.

  5. You are violating the rule of 3 / 5. The default copy- and move- ctor and assignment-operator violate ownership semantics, leading to double-free's, and memory-leaks.

  6. Implement the free function swap(a, b) for use of the copy-and-swap-idiom in move-ctor and move-/copy- assignment, as well as for its own value.

  7. bool stack_empty() should be simply empty(), as in all standard containers.

  8. push() should accept any number and type of arguments for constructing the pushed value.

    template<class... X>
    auto push(X&&... x)
    -> decltype((void)T(std::forward<X>(x)...))
    {
        head = new T { head, T(std::forward<X>(x)...) };
    }
    
  9. display does good work, as does the corresponding free operator<<. I just wonder why you emulated the for-loop using while...

  10. Library-code should never interact with the user / logging, unless it's (part of) the reason for its existence. Let the caller handle any errors, be it by signalling using error-codes (if expected) or exceptions (if exceptional). Of course, finding internal corruption justifies logging and abnormal termination.

  11. Never use an if-else-statement to return a boolean / set the same boolean in both branches. Just use the condition directly, if neccessary after forcing it to bool.

  12. .push() as implemented by you corrupts internal state if allocation or initialization of the new Node fails. You should have incremented top after creating the new Node.

  13. .pop() does not actually pop a Node. It just decrements top and returns a copy of the data-member of the last-pushed Node.

  14. Setting head in the dtor is superfluous. Happily, any optimizing compiler worth its name will remove that.

  15. Your test-suite in main() is beyond unsatisfactory. You should have exercised .pop() more and .empty() as well, at a minimum.

  16. Avoid std::endl unless you need the manual flush, as flushing is quite expensive.

  17. return 0; is implicit for main().

\$\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.