I am a mathematician attempting to become proficient with C++. At the moment I am learning about data structures. I am now writing a stack data structure using linked list from scratch.

I have tested my class that I wrote and everything seems to be working fine but I want to see if there are any bugs or some areas of the code I could improve on.

Here is the class:

 #ifndef Stack_h
#define Stack_h

template <class T>
class Stack 
private:
 struct Node 
 T data;
 Node* next;
 ;
 Node* top;

public:
 // Constructors
 Stack() : top(nullptr) // empty constructor
 Stack(Stack const& value); // copy constructor
 Stack<T>(Stack<T>&& move) noexcept; // move constuctor
 Stack<T>& operator=(Stack&& move) noexcept; // move assignment operator
 ~Stack(); // destructor

 // Overload operators
 Stack& operator=(Stack const& rhs);
 friend std::ostream& operator<<(std::ostream& str, Stack<T> const& data) 
 data.show(str);
 return str;
 

 // Member functions
 void swap(Stack& other) noexcept;
 bool isEmpty();
 int getSize();
 void push(const T& theData);
 void push(T&& theData);
 void pop();
 void show(std::ostream &str) const;
;

template <class T>
Stack<T>::Stack(Stack const& value) : top(nullptr) 
 for(Node* loop = value->data; loop != nullptr; loop = loop->next) 
 push(loop->data);
 


template <class T>
Stack<T>::Stack(Stack<T>&& move) noexcept : top(nullptr) 
 move.swap(*this);


template <class T>
Stack<T>& Stack<T>::operator=(Stack<T> &&move) noexcept 
 move.swap(*this);
 return *this;


template <class T>
Stack<T>::~Stack() 
 while(top != nullptr) 
 pop();
 


template <class T>
Stack<T>& Stack<T>::operator=(Stack const& rhs) 
 Stack copy(rhs);
 swap(copy);
 return *this;



template <class T>
void Stack<T>::swap(Stack<T> &other) noexcept 
 using std::swap;
 swap(top,other.top);


template <class T>
bool Stack<T>::isEmpty() 
 if(top == nullptr) 
 return true;
 
 else 
 return false;
 


template <class T>
int Stack<T>::getSize() 
 int size = 0;
 Node* current = top;
 while(current != nullptr) 
 size++;
 current = current->next;
 
 return size;


template <class T>
void Stack<T>::push(const T &theData) 
 Node* newNode = new Node;
 newNode->data = theData;
 newNode->next = nullptr;

 if(top != nullptr) 
 newNode->next = top;
 
 top = newNode;


template <class T>
void Stack<T>::push(T&& theData) 
 Node* newNode = new Node;
 newNode->data = std::move(theData);
 newNode->next = nullptr;

 if(top != nullptr) 
 newNode->next = top;
 
 top = newNode;


template <class T>
void Stack<T>::pop() 
 Node* temp;
 if(top == nullptr) 
 throw std::invalid_argument("The list is already empty, nothing to pop.");
 
 temp = top;
 top = top->next;
 delete temp;


template <class T>
void Stack<T>::show(std::ostream &str) const 
 for(Node* loop = top; loop != nullptr; loop = loop->next) 
 str << loop->data << "t";
 
 str << "n";



#endif /* Stack_h */

Here is the main.cpp file that tests the class:

#include <iostream>
#include "Stack.h"

int main(int argc, const char * argv) 



 ///////////////////////////////////////////////////////////////////////////////////
 ///////////////////////////// Stack Using Linked List //////////////////////////////////
 ///////////////////////////////////////////////////////////////////////////////////

 Stack<int> obj;
 obj.push(2);
 obj.push(4);
 obj.push(6);
 obj.push(8);
 obj.push(10);
 std::cout<<"n--------------------------------------------------n";
 std::cout<<"---------------Displaying Stack Contents---------------";
 std::cout<<"n--------------------------------------------------n";
 std::cout << obj << std::endl;

 std::cout<<"n--------------------------------------------------n";
 std::cout<<"---------------Pop Stack Element -------------------";
 std::cout<<"n--------------------------------------------------n";
 obj.pop();
 std::cout << obj << std::endl;

 std::cout<<"n--------------------------------------------------n";
 std::cout<<"---------------Get the size of stack -------------------";
 std::cout<<"n--------------------------------------------------n";
 std::cout << obj.getSize() << std::endl;

 std::cout<<"n--------------------------------------------------n";
 std::cout<<"---------------Re-Add Poped Element---------------";
 std::cout<<"n--------------------------------------------------n";
 obj.push(10);
 std::cout << obj << std::endl;

 return 0;

General stuff

• In the copy constructor, the implementation starts to iterate over all the nodes, starting from value->data. I guess this is meant to be value.top.


• Still in the copy constructor, it pushes the values in reverse order (traversal of original: top to bottom; insertion in new Stack: bottom to top).


• The two above issues are also inherent in the copy assignment operator, as it uses the copy constructor internally.


• The body of isEmpty can be simplified to return top == nullptr;.


• 
  

  Both variants of Stack<T>::push contain the following snippet:

  
  
  

  newNode->next = nullptr;
  
  if (top != nullptr) 
   newNode->next = top;
  
  

  
  
  

  This can be simplified to newNode->next = top;

  
  


• The implementation is inconsistent in the usage of Stack<T> vs Stack.


• 
  isEmpty and getSize can be marked const, as they don't modify the Stack object.


• 
  #includes are missing for std::ostream, std::swap, std::move and std::invalid_argument.

Advanced stuff

Note: These require template meta programming. This might be a bit much for a beginner.

• 
  push(T&&) could be disabled for types that aren't move-constructible by using SFINAE.


• Similar to above, push(const T&) could be disabled for non-copy-constructible types.


• 
  Stack could use an emplace member function to construct objects in-place using perfect forwarding.

Performance

Since this class has a move constructor (and a move assignment operator), it seems to care about performance. However, the implementation of the move constructor makes unnecessary copies/assignments. Granted, the concerned objects are pointers, so they are cheap to copy, but it's still some overhead.

The move constructor first initializes top to nullptr (= 1 assignment).

Then it calls swap, which internally calls std::swap on both top pointers, which in turn will very likely boil down to a triangle swap (= 1 assignment to temp, 1 assignment from one top to the other top and 1 assignment from temp).

So there are 4 assignments in total. Compare this to:

Initialize top from other.top. (1 assignment)

Set other.top to nullptr. (1 assignment)

Only 2 assignments, and has the same results.

Other than that, just a general note: Linked lists, at least on modern processors, have generally worse performance than using contiguous memory (e.g. an array or a std::vector) because of prefetching, memory overhead and cache misses.

Memory management

Guideline R.11 from the C++ Core Guidelines discourages use of raw calls to new and delete in favor of using smart pointers. While there are some caveats if used carelessly (like stack overflow on recursive object destruction), they generally make code more robust, easier to use and leak-free.

#ifndef Stack_h
#define Stack_h

Your include guard is susceptible to collisions. Add differentiators that will generate keys that are more likely to be unique, like the the library name, author name, date created, or a guid.

 struct Node 
 T data;
 Node* next;
 ;
 Node* top;

You have been writing other containers. Why not reuse them? Consider that a stack is just an abstract data type. That is, a stack is defined by its semantic behavior, Last In-First Out. Any container that maintains insertion order and allows access, insertions, and deletions from the same end can be modeled to be a stack. Read up on the adaptor pattern.

public:
 // Constructors
 Stack() : top(nullptr) // empty constructor

When initializing data members with constant initializers, prefer in-class member initialization. i.e:

 Node* top nullptr ;
 ...
 Stack() = default;

Keep comments crisp. Programmers looking at the code should already know that they are constructors. Reserve comments for stating intent, when you want to explain why something is being done and the code doesn't obviously state that intent.

 Stack(Stack const& value);
 Stack<T>(Stack<T>&& move) noexcept;
 Stack<T>& operator=(Stack&& move) noexcept;

Be consistent. Stack<T> vs Stack?

Use names to convey information. move suggests an action. Either other, that, or rhs would be better names to describe the other stack.

 Stack& operator=(Stack const& rhs);
 friend std::ostream& operator<<(std::ostream& str, Stack<T> const& data) 
 data.show(str);
 return str;
 

Stack's typically only offer access to the top element. Do you really need to stream all elements?

As John Lakos says in "Large Scale C++ Software Design":

Latent usage errors can be avoided by ensuring that the .h file of a component parses by itself – without externally-provided declarations or definitions... Including the .h file as the very first line of the .c file ensures that no critical piece of information intrinsic to the physical interface of the component is missing from the .h file (or, if there is, that you will find out about it as soon as you try to compile the .c file).

Your file is missing the includes for std::ostream, std::swap, etc.

 bool isEmpty();
 int getSize();

If you want your functions to work with standard library facilities, consider using the same standard library names, i.e. empty(), size(). Otherwise, someone using your library will have to write customization points to be used with std::empty() and std::size().

If you would like to use these functions in a const-context (const Stack<T>), then specify them as const. They can also be specified as noexcept.

 void push(const T& theData);
 void push(T&& theData);

No emplace(Args&&... args)?

 void show(std::ostream &str) const;

Is show() supposed to be publicly accessible? Speaking of access, how do you access the top element of the stack?

template <class T>
Stack<T>::Stack(Stack const& value) : top(nullptr) 
 for(Node* loop = value->data; loop != nullptr; loop = loop->next) 
 push(loop->data);
 

That for loop looks like a good candidate to abstract for reuse.

template <class T>
Stack<T>::Stack(Stack<T>&& move) noexcept : top(nullptr) 
 move.swap(*this);


template <class T>
Stack<T>& Stack<T>::operator=(Stack<T> &&move) noexcept 
 move.swap(*this);
 return *this;

You could just call swap(move);.

template <class T>
Stack<T>::~Stack() 
 while(top != nullptr) 
 pop();
 

During destruction, the null check is done twice. What you really want to call is the unchecked part of pop(). Consider abstracting it into its own function and have both the destructor and pop() call that unchecked operation after each does its own check.

Stack<T>::~Stack() 
 while (top) 
 do_unchecked_pop();
 


void Stack<T>::pop() 
 if (top) throw ... 
 do_unchecked_pop();


void Stack<T>::do_unchecked_pop() 
 Node* tmp = top->next;
 delete top;
 top = tmp;

From here, you can abstract the while loop into a clear() member function and call that from the destructor.

template <class T>
bool Stack<T>::isEmpty() 
 if(top == nullptr) 
 return true;
 
 else 
 return false;
 

How about return top; for the body? top is a pointer and when converted to bool will return false when pointing at nullptr. It's redundant to compare to nullptr.

template <class T>
int Stack<T>::getSize() 
 int size = 0;
 Node* current = top;
 while(current != nullptr) 
 size++;
 current = current->next;
 
 return size;

You traverse the link list every time you call for the size. That is expensive for large lists. Have you considered keeping a count data member that changes on inserts and deletions?

template <class T>
void Stack<T>::push(const T &theData) 
 Node* newNode = new Node;
 newNode->data = theData;
 newNode->next = nullptr;

 if(top != nullptr) 
 newNode->next = top;
 
 top = newNode;


template <class T>
void Stack<T>::push(T&& theData) 
 Node* newNode = new Node;
 newNode->data = std::move(theData);
 newNode->next = nullptr;

 if(top != nullptr) 
 newNode->next = top;
 
 top = newNode;

You can remove some duplication here with adding a node to the front.

template <class T>
void Stack<T>::pop() 
 Node* temp;
 if(top == nullptr) 
 throw std::invalid_argument("The list is already empty, nothing to pop.");
 
 temp = top;
 top = top->next;
 delete temp;

Declare variables as you need them and initialize them with a value.

See Container Requirements and Stack for what you are missing in regards to typedefs and operations.

As for your test file, use a testing framework (Catch2, GoogleTest, BoostTest). You shouldn't have to concern yourself with what is being returned but did it return what you expect. Reduce the cognitive load.

Also, follow the Beyonce Rule. If you want it, put a test on it. Every member should have a test.

I share most of hoffmale's review, but I want to insist on some points, including Memory Management, and the smart pointers.

General points