Simple stack implementation using linked list

Question

Please review my Stack using linked list:

template<class T>
struct Node {
    T item;
    Node* next;
    Node(T t = {}, Node* link = nullptr) :item{t}, next{link} { }
    ~Node() { delete next; }
};

template<class T>
class Stack {
public:
    int size() const { return n; }
    bool empty() const { return n == 0; }
    void push(const T&);
    T pop();
    T peek();
private:
    Node<T>* first;
    std::size_t n;
};

template<class T>
void Stack<T>::push(const T& t) {
    Node<T>* old{first};
    first = new Node<T>{t,old};
    ++n;
}

template<class T>
T Stack<T>::pop() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    auto t = first->item;
    first = first->next;
    --n;
    return t;
}

template<class T>
T Stack<T>::peek() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    return first->item;
}

A few notes:

• I would like to experiment to try to avoid allocating in the heap, but I really can't because I don't know how to keep the newly created and added node in push() alive.
• Is it correct to use std::size_t when tracking the size of the stack?

I thought that since my Stack class acts like a handle to nodes, I thought I should write my own copy and move operations so I can avoid member-wise copying, but something very funny happens when I tested my Stack:

int main() {
    Stack<std::string> x{};
    x.push("str");
    x.push("tring");
    x.push("string");
    Stack<std::string> y = x;
    y.pop();
    std::cout << x.peek() << '\n';
    y.pop();
    std::cout << x.peek() << '\n';
    y.pop();
    std::cout << x.peek() << '\n';
    y.push("nox");
    std::cout << x.peek() << '\n';
    std::cout << x.size() << '\n';
    std::cout << y.size() << '\n';
}

When x.peek() is called the result is always "string", x.size() is 3 and y.size() is 1. It seems the default copy operation works correctly. I thought it shouldn't because first is a pointer so they should refer to the same elements. So I did not write a copy and move operation because it seems the default operations work correctly but I really don't know why and how. Can anyone explain why?

How can I make this code better?

Answer 1

I see some things that you might want to use to improve your code.

Use appropriate #include files

The implementation requires #include <stdexcept> so that should part of the template.

Eliminate unneeded variables

The push function doesn't really need any temporary variables:

template<class T>
void Stack<T>::push(const T& t) {
    first = new Node<T>{t,first};
    ++n;
}

Create a default constructor for Stack

An instance of Stack is not necessarily initialized to any particular values when it's created. To address this, you should implement a default constructor.

Stack() : first{nullptr}, n{0} {}

Match new with delete

If you allocate memory using new, you must also free it using delete or your program will leak memory. Since you use new in push(), you should use delete in pop():

template<class T>
T Stack<T>::pop() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    Node<T>* oldnode = first;
    T t = first->item;
    first = first->next;
    --n;
    delete oldnode;
    return t;
}

Create a copy constructor if you need one

The compiler will create a default copy constructor which does a shallow copy, but this won't work for data structures, like yours, which use pointers. Instead, if you really want to create a new Stack from an existing one, you'll need to creat your own copy constructor:

template<class T>
Stack<T>::Stack(const Stack<T> &s) : first(nullptr), n(0) {
    for (auto t=s.first; t; t = t->next)
        push(t->item);
}

The default-constructed operator= will now use this copy constructor.

Create a destructor if you need one

For similar reasons, you need have a delete for Stack and not for Node. The one for Stack could be like this:

template<class T>
Stack<T>::~Stack() {
    while (!empty())
        pop();
}

Use const where possible

The peek() function doesn't (and shouldn't) alter the underlying Stack so it should be declared const.

Consider using references

While this code works (with the adjustments listed above), ther is still some room for improvement. First, things inserted into the stack are copied rather than moved there. Also things that are popped from the stack are also copied rather than moved. This means that there are many more constructor and destructor calls made than are strictly necessary.

To see how this works, here's a class that contains a string, but includes instrumentation so we can see what's happening:

class MyString {
public:
    MyString() : str(), id(serial++) { std::cout << "creating empty string " << id << "\n"; }
    MyString(const char *msg) : str(msg), id(serial++) { 
        std::cout << "creating string \"" << str << "\" " << id << "\n"; }
    MyString(const MyString &s) : str(s.str), id(serial++) { 
        std::cout << "copying string \"" << str << "\" " << id << "\n"; }
    MyString(MyString &&s) : str(), id(serial++) { 
        std::swap(str, s.str);
        std::cout << "moving string \"" << str << "\" " << id << "\n"; }
    ~MyString() { std::cout << "destroying string " << id << "\n"; }
    friend std::ostream &operator<<(std::ostream &out, const MyString &m) {
        return out << m.str;
    }
private:
    static unsigned serial;
    std::string str;
    unsigned id;
};

unsigned MyString::serial = 0;

Now we specialize your templated stack and try it out:

int main() {
    Stack<MyString> x{};
    x.push("one");
    x.push("two");
    x.push("three");
    std::cout << x.peek() << '\n';
}

Output from this program (with the other fixes included):

creating string "one" 0
copying string "one" 1
copying string "one" 2
destroying string 1
destroying string 0
creating string "two" 3
copying string "two" 4
copying string "two" 5
destroying string 4
destroying string 3
creating string "three" 6
copying string "three" 7
copying string "three" 8
destroying string 7
destroying string 6
copying string "three" 9
three
destroying string 9
copying string "three" 10
destroying string 8
destroying string 10
copying string "two" 11
destroying string 5
destroying string 11
copying string "one" 12
destroying string 2
destroying string 12

As you can see, even though we've only got three items on the stack, we've created and destroyed 13 objects. By making only a single small change to the Node constructor, we can reduce that to 10:

Node(const T &t, Node* link) :item{t}, next{link} {}

More savings could be realized by not using pop in the destructor since pop creates a copy of T to return:

template<class T>
Stack<T>::~Stack() {
    if (first) {
        for (Node<T> *n = first->next; n; n = first->next) {
            delete first;
            first = n;
        }
        delete first;
    }
}

Consider using smart pointers

Using something like a std::unique_ptr would free you (pun intended) from having to manage the mechanics of new and delete explicitly.

Answer 2

You seem to have bugs and leak memory.

• In class Node:

  template<class T>
  struct Node {
      T item;
      Node* next;
      Node(T t = {}, Node* link = nullptr) :item{t}, next{link} { }
      ~Node() { delete next; }
  };
  

  You keep the head of stack in Stack::first and consecutive nodes pointers in next, right? So, in destructor, if you delete first, you will delete whole stack and crash on last deletion of what you assume to be nullptr.

• In class Stack, you seem not to initialize first and size.
• In class Stack, you need a destructor to clear Nodes.
• After you create constructor and destructor in Stack class, it's recommended to create copy constructor and assignment operator, it's so called Rule of Three. In C++11 it was extended to Rule of Five (More on this on wikipedia)

• Stack::pop

  template<class T>
  T Stack<T>::pop() {
      if (empty()) {
          throw std::out_of_range("underflow");
      }
      auto t = first->item;
      first = first->next;
      --n;
      return t;
  }
  

  You are not deleting anywhere the the head, which leads to why it does not crash in first point. This is quite serious, as every Node you create will remain in the memory.

• You may try nesting Node in Stack, as it does not have any real use outside it's scope. But that's a personal preference.
• Take a look at unique_ptr, you may use it in Node for automated garbage collection.

Answer 3

You never actually call a Node using the default values, so you can simplify the constructor to:

Node(T t, Node* link) :item{t}, next{link} { }

It also only copies the parameters, so they can be written as const references

Node(const T &t, const Node* &link) :item{t}, next{link} { }

As Abrixas2 said, you did not delete the now unused pointer in pop

All this requires is a temporary variable to hold the location of first

template<class T>
T Stack<T>::pop() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    auto t = first -> item;
    auto temp = first;
    first = temp -> next;
    delete temp;
    --n;
    return t;
}

Now you should see some things start to fail.

When you made a copy, because there was no specific copy constructor, you only did a shallow copy, getting a copy of the pointer first (which will link to the same node as x) and the current size n (which makes it now completely independent of x). When you popped the values, you changed the pointer first only in y, but the values in x still point to the undeleted data (with the change above, this should point at garbage). Again, n was only copied once, so variable x did not get informed about anything getting deleted or size changing because it was only seen in y