Implementation of Stack using Linked List

Question 1

Please review my code and help me to improve it. I have written this code using template. Can I use more C++11? Is usingtop 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;}

Question 2

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 stackwhile(!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. Lookatstd::vector<> andoperator[] Vsat().

Minor Things

The call to empty should be const:

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

Easier to declare theoperator<< 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;}

Question 3

Why do you handleT&& andconst T& separately?

Question 4

Habbit. I should probably stop that. Can I pass a const object to a&& bind point?

Question 5

If it's a forwarding-reference one, sure. That's the magic of them.

Question 6

You leak every single node you pop. You need todelete 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 ifhead isnullptr. 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;  }}

Question 7

I think there will be no case ofoverflow because we are using linked list and it can change its size dynamically

Question 8

@coder, on successful push you incrementtop, it is an int, which can overflow, which leads to undefined behavior. Though the contents of the list will remain the same.

Question 9

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:

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.
Consider putting thenext-pointer first inNode. It's potentially slightly more efficient.
Remove the constructor fromNode and use aggregate-initialization. That also allows you to construct a pushed value in-place. All else being equal, be brief.
You should not needtop. Just insert and remove at the front.
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.
Implement the free functionswap(a, b) for use of the copy-and-swap-idiom in move-ctor and move-/copy- assignment, as well as for its own value.
bool stack_empty() should be simplyempty(), as in all standard containers.

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)...) };}

display does good work, as does the corresponding freeoperator<<. I just wonder why you emulated thefor-loop usingwhile...
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.
Never use anif-else-statement to return a boolean / set the same boolean in both branches. Just use the condition directly, if neccessary after forcing it tobool.
.push() as implemented by you corrupts internal state if allocation or initialization of the newNode fails. You should have incrementedtopafter creating the newNode.
.pop() does not actually pop aNode. It just decrementstop and returns a copy of thedata-member of the last-pushedNode.
Settinghead in the dtor is superfluous. Happily, any optimizing compiler worth its name will remove that.
Your test-suite inmain() is beyond unsatisfactory. You should have exercised.pop() more and.empty() as well, at a minimum.
Avoidstd::endl unless you need the manual flush, as flushing is quite expensive.
return 0; is implicit formain().

Loki Astari 97.7k5 gold badges126 silver badges341 bronze badges · Accepted Answer · 2017-08-01 03:56:44Z

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 stackwhile(!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. Lookatstd::vector<> andoperator[] Vsat().

Minor Things

The call to empty should be const:

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

Easier to declare theoperator<< 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;}

Habbit. I should probably stop that. Can I pass a const object to a&& bind point?
If it's a forwarding-reference one, sure. That's the magic of them.

Movatterモバイル変換

Stack Exchange Network

Implementation of Stack using Linked List

3 Answers3

Dont use if to test and return bool

Overflow

Design

Bug

Efficiency

Minor Things

Revised Version

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS