Stack Linked list based implementation in C++

Question

This is my second implementation of the Stack in C++. I already implemented it as an array-based here.

I need a review for it to improve it and improve my coding skill. I also will put this implementation on my GitHub account

//======================================================
// Author : Omar_Hafez
// Created : 27 July 2022 (Wednesday) 11:02:46 AM
//======================================================
#include <iostream>
enum InsertStatus { FailedStackEmpty = -1, FailedStackFull = -2, OK = 0 };
template <class T>
class Stack {
 private:
 int size = 0;
 public:
 struct Node {
 T value;
 Node* next = nullptr;
 };
 Node* top;
 Stack() { top = nullptr; }
 Stack(int MAX_SIZE) {
 // this constructor is to keep the consistency with the array based implementation
 top = nullptr;
 }
 bool isEmpty() { return !top; }
 bool isFull() { return 0; }
 int getSize() const { return size; }
 InsertStatus push(T const& t) {
 Node* node = new Node;
 node->value = t;
 node->next = top;
 top = node;
 size++;
 return OK;
 }
 InsertStatus pop() {
 if (isEmpty()) return FailedStackEmpty;
 Node* tmp_ptr = top;
 top = top->next;
 delete tmp_ptr;
 size--;
 return OK;
 }
 T stackTop() { return top->value; }
 void clearStack() {
 for (Node* tmp_ptr; top; tmp_ptr = top) {
 top = top->next;
 delete tmp_ptr;
 }
 size = 0;
 }
};

• infinitezero: Why do you use new and delete and not smart pointers?
• Omar_Hafez: @infinitezero I think that the smart pointers are not needed in this small simple code. I think the smart pointer will be better in complicated applications.
• G. Sliepen: @Omar_Hafez It is best to teach yourself to always use smart pointers where possible, regardless of the size of the project.. As infinitezero showed in his review, even in "this small simple code", your use of manual new and delete has caused a bug.

Answer 1

Method Names

T stackTop() and void clearStack should not contain the word stack, because they already operate on a class called Stack.

Use const for methods where appropriate

As pointed out in the last code review, you should mark methods as const that do not modify your object. You did this for getSize(), but forgot this for stackTop(), isEmpty() and isFull().

Don't expose implementation details

There is no need that struct Node is accessible from outside the class (i.e. public). It is only needed within your stack, so it should be private. Same goes for the top attribute. If top is public, I could manipulate it from the outside and could invalidate your entire stack. You don't want that!

Currently I can do this:

Stack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
stack.top = nullptr;

Test your code!

If you run this code, you'll notice your clear function does not behave as expected, you'll get

double free or corruption (out)

This is a serious bug!

Use the right loop

There are different loops available. While (no pun intended!) you can pretty much use any loop to do anything, some loops are better suited for a job than others.

You should use a for loop, when you iterate from one point to another. For example from beginning to end, or from 1 to n.

for(Node* tmp_ptr; top; tmp_ptr = top){
 top = top->next;
 delete tmp_ptr;
}

This should be a while loop, because you're effectively running it while top is not pointing to null.

Also, this is the source of your bug, because you try to delete an uninitialized tmp_ptr.

You already wrote functions to delete an element and to check if the stack is empty. Use them! It is now very elegant to clear your stack.

while( !isEmpty() ){
 pop();
}

Use auto

When it is possible to deduce the type, you should use auto. This will allow you to change your code more easily without having to change all the respective types. There are other parts in your code where this is possible.

InsertStatus push(T const& t) {
 //Node* node = new Node; OLD
 auto* node = new Node;
 node->value = t;
 node->next = top;
 top = node;
 size++;
 return OK;
}

Also, consider using a constructor for your Node, so you can do new Node(t, top);

isFull / max_size

Currently this method is useless and always returns false.

You can supply your constructor with a default value. Then you do not need to declare two constructors. Also you can use the initializer list.

Stack(int MAX_SIZE = 10000) 
: top(nullptr)
, max_size(MAX_SIZE)
{
}

You should of course implement a max_size attribute. If you do not implement it, remove the MAX_SIZE altogether, because it's doing nothing at the moment (it's not even saved).

Finally

As discussed in the last example, use smart pointers. You said, it's a small example and not needed, but the fact that you programmed a serious bug is evidence enough for me, to use smart pointers even in this small example.

• Omar_Hafez: Thanks a lot for your great review and effort. I see It was a misunderstanding from me for the smart pointers. I will use it even with small simple codes:) (Actually, when the pointer is used in the code I shouldn't say that this is a simple code anyway :) ).
• Toby Speight: The other bug caused by using raw pointers to own resources will be exposed any time you copy or assign a Stack.

Answer 2

The following are in addition to infinitezero's answer:

Add some logic to your Node class.

In C++, a struct and a class are nearly identical concepts with the sole difference being whether members are private or public by default. So, you can add methods to a struct. A constructor for your Node class would simplify some of your Stack methods.

class Node
{
 Node(T the_value, Node* the_next)
 {
 value = the_value;
 next = the_next;
 }
}

Now, Stack::push(T value) can be simplified to this:

InsertStatus Stack::push(T value)
{
 top = new Node(value, top);
 ++size;
 return OK;
}

Additional benefits of smart pointers

Let's say that both Stack::top and Node::next were represented by a std::unique_ptr<T>. How does Stack::pop() change?

InsertStatus pop()
{
 if (isEmpty()) return FailedStackEmpty;
 top = std::move(top->next);
 size--;
 return OK;
}

There's a bunch of machinery under the hood of std::unique_ptr, but that one line does the correct actions: sets top to the second item in the stack and deletes the original top item.

Stack needs a destructor

When a Stack instance goes out of scope, none of the items in the Stack are deleted. The memory for those items will be uselessly used up until the program quits. This is a memory leak and needs to be fixed. Luckily, the fix is simple: create a destructor.

~Stack()
{
 clearStack();
}

• infinitezero: +1 for mentioning the destructor. Of course, this would also be a non-issue if smart-pointers were used :)
• Mark H: @infinitezero I think a destructor is still needed. Letting the smart pointer handle the Stack destructor would lead to recursive calls to destroy each item in the Stack (delete top calls delete top->next which calls delete top->next->next which ... etc.). If the Stack is too deep, then the program will crash with a stack overflow.
• Omar_Hafez: @MarkH +1 for the destructor. This is my first time noticing this important topic. Thanks a lot