Stack implementation in C++ using linked list












3












$begingroup$


I am learning C++ and I made a simple stack class using a (reversed) linked-list to test my knowledge.



Are there any problems with the following code, or any suggestions to improve it?



I want to make sure I am getting things correct in the beginning so I don't make the same mistakes again in the future - especially memory management and avoiding leaks.



One thing to point out is that I included the implementation in the header file... I wouldn't normally do this but apparently there are problems when implementing methods with templates in .cpp files.



#ifndef TEST_STACK_H
#define TEST_STACK_H

#include <stdexcept>

template <class T>
class stack {

struct node {
T data;
node* previous;

node(T data, node *previous) : data(data), previous(previous) {}
};

node* head = nullptr;

int size = 0;
int max = -1; // -1 so isFull() == false when default constructor used

public:
stack() = default;

stack(int max) {
if (max <= 0) throw std::out_of_range("stack size must be > 0");
this->max = max;
}

~stack() {
node* n = head;

while (n != nullptr) {
node* previous = n->previous;
delete n;

n = previous;
}
}

void push(const T &object) {
if (isFull()) throw std::overflow_error("cannot push to a full stack");

head = new node(object, head);
++size;
}

T pop() {
if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

T item = head->data;
head = head->previous;

--size;

delete head;
return item;
}

T peek() {
if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
return head->data;
}

int getSize() {
return size;
}

bool isFull() {
return size == max;
}

bool isEmpty() {
return head == nullptr;
}
};

#endif









share|improve this question









New contributor




Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$

















    3












    $begingroup$


    I am learning C++ and I made a simple stack class using a (reversed) linked-list to test my knowledge.



    Are there any problems with the following code, or any suggestions to improve it?



    I want to make sure I am getting things correct in the beginning so I don't make the same mistakes again in the future - especially memory management and avoiding leaks.



    One thing to point out is that I included the implementation in the header file... I wouldn't normally do this but apparently there are problems when implementing methods with templates in .cpp files.



    #ifndef TEST_STACK_H
    #define TEST_STACK_H

    #include <stdexcept>

    template <class T>
    class stack {

    struct node {
    T data;
    node* previous;

    node(T data, node *previous) : data(data), previous(previous) {}
    };

    node* head = nullptr;

    int size = 0;
    int max = -1; // -1 so isFull() == false when default constructor used

    public:
    stack() = default;

    stack(int max) {
    if (max <= 0) throw std::out_of_range("stack size must be > 0");
    this->max = max;
    }

    ~stack() {
    node* n = head;

    while (n != nullptr) {
    node* previous = n->previous;
    delete n;

    n = previous;
    }
    }

    void push(const T &object) {
    if (isFull()) throw std::overflow_error("cannot push to a full stack");

    head = new node(object, head);
    ++size;
    }

    T pop() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

    T item = head->data;
    head = head->previous;

    --size;

    delete head;
    return item;
    }

    T peek() {
    if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
    return head->data;
    }

    int getSize() {
    return size;
    }

    bool isFull() {
    return size == max;
    }

    bool isEmpty() {
    return head == nullptr;
    }
    };

    #endif









    share|improve this question









    New contributor




    Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      3












      3








      3





      $begingroup$


      I am learning C++ and I made a simple stack class using a (reversed) linked-list to test my knowledge.



      Are there any problems with the following code, or any suggestions to improve it?



      I want to make sure I am getting things correct in the beginning so I don't make the same mistakes again in the future - especially memory management and avoiding leaks.



      One thing to point out is that I included the implementation in the header file... I wouldn't normally do this but apparently there are problems when implementing methods with templates in .cpp files.



      #ifndef TEST_STACK_H
      #define TEST_STACK_H

      #include <stdexcept>

      template <class T>
      class stack {

      struct node {
      T data;
      node* previous;

      node(T data, node *previous) : data(data), previous(previous) {}
      };

      node* head = nullptr;

      int size = 0;
      int max = -1; // -1 so isFull() == false when default constructor used

      public:
      stack() = default;

      stack(int max) {
      if (max <= 0) throw std::out_of_range("stack size must be > 0");
      this->max = max;
      }

      ~stack() {
      node* n = head;

      while (n != nullptr) {
      node* previous = n->previous;
      delete n;

      n = previous;
      }
      }

      void push(const T &object) {
      if (isFull()) throw std::overflow_error("cannot push to a full stack");

      head = new node(object, head);
      ++size;
      }

      T pop() {
      if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

      T item = head->data;
      head = head->previous;

      --size;

      delete head;
      return item;
      }

      T peek() {
      if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
      return head->data;
      }

      int getSize() {
      return size;
      }

      bool isFull() {
      return size == max;
      }

      bool isEmpty() {
      return head == nullptr;
      }
      };

      #endif









      share|improve this question









      New contributor




      Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      I am learning C++ and I made a simple stack class using a (reversed) linked-list to test my knowledge.



      Are there any problems with the following code, or any suggestions to improve it?



      I want to make sure I am getting things correct in the beginning so I don't make the same mistakes again in the future - especially memory management and avoiding leaks.



      One thing to point out is that I included the implementation in the header file... I wouldn't normally do this but apparently there are problems when implementing methods with templates in .cpp files.



      #ifndef TEST_STACK_H
      #define TEST_STACK_H

      #include <stdexcept>

      template <class T>
      class stack {

      struct node {
      T data;
      node* previous;

      node(T data, node *previous) : data(data), previous(previous) {}
      };

      node* head = nullptr;

      int size = 0;
      int max = -1; // -1 so isFull() == false when default constructor used

      public:
      stack() = default;

      stack(int max) {
      if (max <= 0) throw std::out_of_range("stack size must be > 0");
      this->max = max;
      }

      ~stack() {
      node* n = head;

      while (n != nullptr) {
      node* previous = n->previous;
      delete n;

      n = previous;
      }
      }

      void push(const T &object) {
      if (isFull()) throw std::overflow_error("cannot push to a full stack");

      head = new node(object, head);
      ++size;
      }

      T pop() {
      if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

      T item = head->data;
      head = head->previous;

      --size;

      delete head;
      return item;
      }

      T peek() {
      if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");
      return head->data;
      }

      int getSize() {
      return size;
      }

      bool isFull() {
      return size == max;
      }

      bool isEmpty() {
      return head == nullptr;
      }
      };

      #endif






      c++ beginner linked-list stack






      share|improve this question









      New contributor




      Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|improve this question









      New contributor




      Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|improve this question




      share|improve this question








      edited 25 mins ago









      Jamal

      30.3k11116226




      30.3k11116226






      New contributor




      Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 5 hours ago









      Samueljh1Samueljh1

      163




      163




      New contributor




      Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Samueljh1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          1 Answer
          1






          active

          oldest

          votes


















          1












          $begingroup$

          Bug



          Your main issue is memory management.



          You did not implement the "Rule of Three" (you can google it).



          The problem is that if you do not define the copy constructor or the assignment operator the compiler will generate these methods for you automatically. Under most conditions these generated methods work correctly. BUT when your class contains an "Owned" pointer they do not work.



          Note: An "Owned" pointer is a pointer you are responsible for deleting.



          {
          stack<int> x;
          x.push(12);


          stack<int> y(x); // Copy constructor used.
          // The default implementation does a shallow copy
          // of each member from x into y.
          // This means that x and y point at the same list.

          }
          // Here your destructor has destroyed the same list twice.
          // This is a bug.


          To fix this you need to define the copy constructor and assignment operator. But there is a nice pattern that allows you to define the assignment operator in terms of the copy constructor. Look up the "Copy And Swap Idiom".



          You need to add the following to your class:



          class stack
          {
          // Stuff
          public:
          stack(stack const& rhs)
          : head(copyList(rhs.head))
          , size(rhs.size)
          , max(rhs.size)
          {}
          stack& operator=(stack const& rhs)
          {
          stack tmp(rhs); // make a copy using copy constructor.
          swap(tmp); // swap the tmp and this object
          return *this;
          }
          void swap(stack& other) noexcept
          {
          using std::swap;
          swap(head, other.head);
          swap(size, other.size);
          swap(max, other.max);
          }

          private:
          node* copyList(node* l)
          {
          if (l == nullptr) {
          return null;
          }
          return new node{l->data, copyList(l->previous)};
          }
          // STUFF
          };


          Your pop() has a bug. You delete the NEW head item before returning but leak the original head item.



          T pop() {
          if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

          T item = head->data;
          head = head->previous; // You just leaked the old head.
          // You need to keep a pointer to the old head

          --size;

          delete head; // So you can delete the old head here.
          return item;
          }


          Other Stuff



          Design of pop()



          You make your pop() method return the top value and remove it from the stack. This is fine if your T type is simple. But if T is a complex type there is no way to do this safely (and maintain "Strong Exception Guarantee"). So most implementations of stack split this into two separate functions. A top() that returns the top value and a pop() that simply removes the top value.



          So I would rewrite this:



          void pop() {
          if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

          node* old = head;
          head = head->previous;

          --size;
          delete old;
          }
          T const& top() {
          if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

          return head->data;
          }


          Return by reference



          Your pop() and peek() return the result by value. This is OK for simple types of T (like integer). But if T is a complex object you are making a copy of this complex object. Instead you should return a reference to the object. If the user is doing somehting simple they can do the action without copying if they want to keep a copy they can make that decision and save the value in a local variable.



          T peek()

          // Change to:

          T const& peek(); // Don't really need this if you have top()
          // Or you could use peek instead of top()


          But notice the const& as the return type. You are returning a reference to the object so no copy is made. If you need a local copy then you can save it like this:



          int   val = x.top();
          x.pop();





          share|improve this answer









          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "196"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });






            Samueljh1 is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211726%2fstack-implementation-in-c-using-linked-list%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1












            $begingroup$

            Bug



            Your main issue is memory management.



            You did not implement the "Rule of Three" (you can google it).



            The problem is that if you do not define the copy constructor or the assignment operator the compiler will generate these methods for you automatically. Under most conditions these generated methods work correctly. BUT when your class contains an "Owned" pointer they do not work.



            Note: An "Owned" pointer is a pointer you are responsible for deleting.



            {
            stack<int> x;
            x.push(12);


            stack<int> y(x); // Copy constructor used.
            // The default implementation does a shallow copy
            // of each member from x into y.
            // This means that x and y point at the same list.

            }
            // Here your destructor has destroyed the same list twice.
            // This is a bug.


            To fix this you need to define the copy constructor and assignment operator. But there is a nice pattern that allows you to define the assignment operator in terms of the copy constructor. Look up the "Copy And Swap Idiom".



            You need to add the following to your class:



            class stack
            {
            // Stuff
            public:
            stack(stack const& rhs)
            : head(copyList(rhs.head))
            , size(rhs.size)
            , max(rhs.size)
            {}
            stack& operator=(stack const& rhs)
            {
            stack tmp(rhs); // make a copy using copy constructor.
            swap(tmp); // swap the tmp and this object
            return *this;
            }
            void swap(stack& other) noexcept
            {
            using std::swap;
            swap(head, other.head);
            swap(size, other.size);
            swap(max, other.max);
            }

            private:
            node* copyList(node* l)
            {
            if (l == nullptr) {
            return null;
            }
            return new node{l->data, copyList(l->previous)};
            }
            // STUFF
            };


            Your pop() has a bug. You delete the NEW head item before returning but leak the original head item.



            T pop() {
            if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

            T item = head->data;
            head = head->previous; // You just leaked the old head.
            // You need to keep a pointer to the old head

            --size;

            delete head; // So you can delete the old head here.
            return item;
            }


            Other Stuff



            Design of pop()



            You make your pop() method return the top value and remove it from the stack. This is fine if your T type is simple. But if T is a complex type there is no way to do this safely (and maintain "Strong Exception Guarantee"). So most implementations of stack split this into two separate functions. A top() that returns the top value and a pop() that simply removes the top value.



            So I would rewrite this:



            void pop() {
            if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

            node* old = head;
            head = head->previous;

            --size;
            delete old;
            }
            T const& top() {
            if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

            return head->data;
            }


            Return by reference



            Your pop() and peek() return the result by value. This is OK for simple types of T (like integer). But if T is a complex object you are making a copy of this complex object. Instead you should return a reference to the object. If the user is doing somehting simple they can do the action without copying if they want to keep a copy they can make that decision and save the value in a local variable.



            T peek()

            // Change to:

            T const& peek(); // Don't really need this if you have top()
            // Or you could use peek instead of top()


            But notice the const& as the return type. You are returning a reference to the object so no copy is made. If you need a local copy then you can save it like this:



            int   val = x.top();
            x.pop();





            share|improve this answer









            $endgroup$


















              1












              $begingroup$

              Bug



              Your main issue is memory management.



              You did not implement the "Rule of Three" (you can google it).



              The problem is that if you do not define the copy constructor or the assignment operator the compiler will generate these methods for you automatically. Under most conditions these generated methods work correctly. BUT when your class contains an "Owned" pointer they do not work.



              Note: An "Owned" pointer is a pointer you are responsible for deleting.



              {
              stack<int> x;
              x.push(12);


              stack<int> y(x); // Copy constructor used.
              // The default implementation does a shallow copy
              // of each member from x into y.
              // This means that x and y point at the same list.

              }
              // Here your destructor has destroyed the same list twice.
              // This is a bug.


              To fix this you need to define the copy constructor and assignment operator. But there is a nice pattern that allows you to define the assignment operator in terms of the copy constructor. Look up the "Copy And Swap Idiom".



              You need to add the following to your class:



              class stack
              {
              // Stuff
              public:
              stack(stack const& rhs)
              : head(copyList(rhs.head))
              , size(rhs.size)
              , max(rhs.size)
              {}
              stack& operator=(stack const& rhs)
              {
              stack tmp(rhs); // make a copy using copy constructor.
              swap(tmp); // swap the tmp and this object
              return *this;
              }
              void swap(stack& other) noexcept
              {
              using std::swap;
              swap(head, other.head);
              swap(size, other.size);
              swap(max, other.max);
              }

              private:
              node* copyList(node* l)
              {
              if (l == nullptr) {
              return null;
              }
              return new node{l->data, copyList(l->previous)};
              }
              // STUFF
              };


              Your pop() has a bug. You delete the NEW head item before returning but leak the original head item.



              T pop() {
              if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

              T item = head->data;
              head = head->previous; // You just leaked the old head.
              // You need to keep a pointer to the old head

              --size;

              delete head; // So you can delete the old head here.
              return item;
              }


              Other Stuff



              Design of pop()



              You make your pop() method return the top value and remove it from the stack. This is fine if your T type is simple. But if T is a complex type there is no way to do this safely (and maintain "Strong Exception Guarantee"). So most implementations of stack split this into two separate functions. A top() that returns the top value and a pop() that simply removes the top value.



              So I would rewrite this:



              void pop() {
              if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

              node* old = head;
              head = head->previous;

              --size;
              delete old;
              }
              T const& top() {
              if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

              return head->data;
              }


              Return by reference



              Your pop() and peek() return the result by value. This is OK for simple types of T (like integer). But if T is a complex object you are making a copy of this complex object. Instead you should return a reference to the object. If the user is doing somehting simple they can do the action without copying if they want to keep a copy they can make that decision and save the value in a local variable.



              T peek()

              // Change to:

              T const& peek(); // Don't really need this if you have top()
              // Or you could use peek instead of top()


              But notice the const& as the return type. You are returning a reference to the object so no copy is made. If you need a local copy then you can save it like this:



              int   val = x.top();
              x.pop();





              share|improve this answer









              $endgroup$
















                1












                1








                1





                $begingroup$

                Bug



                Your main issue is memory management.



                You did not implement the "Rule of Three" (you can google it).



                The problem is that if you do not define the copy constructor or the assignment operator the compiler will generate these methods for you automatically. Under most conditions these generated methods work correctly. BUT when your class contains an "Owned" pointer they do not work.



                Note: An "Owned" pointer is a pointer you are responsible for deleting.



                {
                stack<int> x;
                x.push(12);


                stack<int> y(x); // Copy constructor used.
                // The default implementation does a shallow copy
                // of each member from x into y.
                // This means that x and y point at the same list.

                }
                // Here your destructor has destroyed the same list twice.
                // This is a bug.


                To fix this you need to define the copy constructor and assignment operator. But there is a nice pattern that allows you to define the assignment operator in terms of the copy constructor. Look up the "Copy And Swap Idiom".



                You need to add the following to your class:



                class stack
                {
                // Stuff
                public:
                stack(stack const& rhs)
                : head(copyList(rhs.head))
                , size(rhs.size)
                , max(rhs.size)
                {}
                stack& operator=(stack const& rhs)
                {
                stack tmp(rhs); // make a copy using copy constructor.
                swap(tmp); // swap the tmp and this object
                return *this;
                }
                void swap(stack& other) noexcept
                {
                using std::swap;
                swap(head, other.head);
                swap(size, other.size);
                swap(max, other.max);
                }

                private:
                node* copyList(node* l)
                {
                if (l == nullptr) {
                return null;
                }
                return new node{l->data, copyList(l->previous)};
                }
                // STUFF
                };


                Your pop() has a bug. You delete the NEW head item before returning but leak the original head item.



                T pop() {
                if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

                T item = head->data;
                head = head->previous; // You just leaked the old head.
                // You need to keep a pointer to the old head

                --size;

                delete head; // So you can delete the old head here.
                return item;
                }


                Other Stuff



                Design of pop()



                You make your pop() method return the top value and remove it from the stack. This is fine if your T type is simple. But if T is a complex type there is no way to do this safely (and maintain "Strong Exception Guarantee"). So most implementations of stack split this into two separate functions. A top() that returns the top value and a pop() that simply removes the top value.



                So I would rewrite this:



                void pop() {
                if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

                node* old = head;
                head = head->previous;

                --size;
                delete old;
                }
                T const& top() {
                if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

                return head->data;
                }


                Return by reference



                Your pop() and peek() return the result by value. This is OK for simple types of T (like integer). But if T is a complex object you are making a copy of this complex object. Instead you should return a reference to the object. If the user is doing somehting simple they can do the action without copying if they want to keep a copy they can make that decision and save the value in a local variable.



                T peek()

                // Change to:

                T const& peek(); // Don't really need this if you have top()
                // Or you could use peek instead of top()


                But notice the const& as the return type. You are returning a reference to the object so no copy is made. If you need a local copy then you can save it like this:



                int   val = x.top();
                x.pop();





                share|improve this answer









                $endgroup$



                Bug



                Your main issue is memory management.



                You did not implement the "Rule of Three" (you can google it).



                The problem is that if you do not define the copy constructor or the assignment operator the compiler will generate these methods for you automatically. Under most conditions these generated methods work correctly. BUT when your class contains an "Owned" pointer they do not work.



                Note: An "Owned" pointer is a pointer you are responsible for deleting.



                {
                stack<int> x;
                x.push(12);


                stack<int> y(x); // Copy constructor used.
                // The default implementation does a shallow copy
                // of each member from x into y.
                // This means that x and y point at the same list.

                }
                // Here your destructor has destroyed the same list twice.
                // This is a bug.


                To fix this you need to define the copy constructor and assignment operator. But there is a nice pattern that allows you to define the assignment operator in terms of the copy constructor. Look up the "Copy And Swap Idiom".



                You need to add the following to your class:



                class stack
                {
                // Stuff
                public:
                stack(stack const& rhs)
                : head(copyList(rhs.head))
                , size(rhs.size)
                , max(rhs.size)
                {}
                stack& operator=(stack const& rhs)
                {
                stack tmp(rhs); // make a copy using copy constructor.
                swap(tmp); // swap the tmp and this object
                return *this;
                }
                void swap(stack& other) noexcept
                {
                using std::swap;
                swap(head, other.head);
                swap(size, other.size);
                swap(max, other.max);
                }

                private:
                node* copyList(node* l)
                {
                if (l == nullptr) {
                return null;
                }
                return new node{l->data, copyList(l->previous)};
                }
                // STUFF
                };


                Your pop() has a bug. You delete the NEW head item before returning but leak the original head item.



                T pop() {
                if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

                T item = head->data;
                head = head->previous; // You just leaked the old head.
                // You need to keep a pointer to the old head

                --size;

                delete head; // So you can delete the old head here.
                return item;
                }


                Other Stuff



                Design of pop()



                You make your pop() method return the top value and remove it from the stack. This is fine if your T type is simple. But if T is a complex type there is no way to do this safely (and maintain "Strong Exception Guarantee"). So most implementations of stack split this into two separate functions. A top() that returns the top value and a pop() that simply removes the top value.



                So I would rewrite this:



                void pop() {
                if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

                node* old = head;
                head = head->previous;

                --size;
                delete old;
                }
                T const& top() {
                if (head == nullptr) throw std::underflow_error("cannot get item from empty stack");

                return head->data;
                }


                Return by reference



                Your pop() and peek() return the result by value. This is OK for simple types of T (like integer). But if T is a complex object you are making a copy of this complex object. Instead you should return a reference to the object. If the user is doing somehting simple they can do the action without copying if they want to keep a copy they can make that decision and save the value in a local variable.



                T peek()

                // Change to:

                T const& peek(); // Don't really need this if you have top()
                // Or you could use peek instead of top()


                But notice the const& as the return type. You are returning a reference to the object so no copy is made. If you need a local copy then you can save it like this:



                int   val = x.top();
                x.pop();






                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 3 hours ago









                Martin YorkMartin York

                72.9k485265




                72.9k485265






















                    Samueljh1 is a new contributor. Be nice, and check out our Code of Conduct.










                    draft saved

                    draft discarded


















                    Samueljh1 is a new contributor. Be nice, and check out our Code of Conduct.













                    Samueljh1 is a new contributor. Be nice, and check out our Code of Conduct.












                    Samueljh1 is a new contributor. Be nice, and check out our Code of Conduct.
















                    Thanks for contributing an answer to Code Review Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f211726%2fstack-implementation-in-c-using-linked-list%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    How to make a Squid Proxy server?

                    Is this a new Fibonacci Identity?

                    19世紀