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();
