Simple stack implementation using linked list

Please review my Stack using linked list:

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

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

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

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

template
T Stack::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 x{};
    x.push("str");
    x.push("tring");
    x.push("string");
    Stack 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 ope

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

Use appropriate #include files

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

Eliminate unneeded variables

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

template
void Stack::push(const T& t) {
    first = new Node{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
T Stack::pop() {
    if (empty()) {
        throw std::out_of_range("underflow");
    }
    Node* 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
Stack::Stack(const Stack &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
Stack::~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 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
Stack::~Stack() {
    if (first) {
        for (Node *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.

StackExchange Code Review Q#69402, answer score: 11