C++ Stack Implementation Using Templates and Linked List

Question

I have a simple stack class. It uses a linked list for its data structure and it is of type template so any datatype (including pointers) can be passed in. It can be initialized on the stack or on the heap. It does only what a stack should do and nothing more.

It is constructed entirely in the header file to avoid compiler errors for missing types(I believe that's standard procedure for template). I created it with Xcode on a mac and have not tested it on Linux or Windows yet for compiler errors. The code is well commented and warns the caller they are responsible for deletion of heap allocated objects(just like a C++ vector would be). I want to discuss this topic in a blog or something so I want to make sure it is correct. Please review my code for completeness and correctness

My Stack:

#ifndef TStack_h
#define TStack_h
#include <iostream>
#include <stdexcept>
template <class T> class TStack{
public:
//####################################
// Constructor.
//####################################
TStack();
//####################################
// Destructor.
//####################################
~TStack();
//####################################
// Class methods.
//####################################
/**
 * Adds an item to the stack.
 * <b>Notes:</b><br>
 * &nbsp; N/A <br>
 * ------<br>
 * <b>Arguments:</b><br>
 * &nbsp; template<class T>: the type of the class.<br>
 * ------<br>
 * <b>Return:</b><br>
 * &nbsp; N/A<br>
 * ------<br>
 * <b>Throws</b><br>
 * &nbsp; N/A<br>
 */
void push(T elem);
/**
 * Removes the data item at the beginning of the stack.
 * <b>Notes:</b><br>
 * &nbsp; Caller is responsible for releasing objects that are popped from the stack.<br>
 * ------<br>
 * <b>Arguments:</b><br>
 * &nbsp; N/A <br>
 * ------<br>
 * <b>Return:</b><br>
 * &nbsp;dataType T: the type<br>
 * ------<br>
 * <b>Throws</b><br>
 * &nbsp; out_of_range exception for an empty stack.<br>
 */
T pop();
/**
 * The size of the stack.
 * <b>Notes:</b><br>
 * &nbsp;N/A<br>
 * ------<br>
 * <b>Arguments:</b><br>
 * &nbsp; N/A <br>
 * ------<br>
 * <b>Return:</b><br>
 * &nbsp;int : The size of the stack.<br>
 * ------<br>
 * <b>Throws</b><br>
 * &nbsp; N/A<br>
 */
int getSize();
/**
 * Reports if the stack is empty.
 * <b>Notes:</b><br>
 * &nbsp;N/A<br>
 * ------<br>
 * <b>Arguments:</b><br>
 * &nbsp; N/A <br>
 * ------<br>
 * <b>Return:</b><br>
 * &nbsp;int : Whether the stack is empty of not.<br>
 * ------<br>
 * <b>Throws</b><br>
 * &nbsp; N/A<br>
 */
bool isEmpty();
//####################################
// End - Class methods.
//####################################
private:
/**
 * A linked list node struct.
 * <b>Notes:</b><br>
 * &nbsp;N/A<br>
 **/
struct Node{
 T data_;
 Node* next_;
};
/**
 * The size of the stack.
 * <b>Notes:</b><br>
 * &nbsp;N/A<br>
 **/
int size_;
/**
 * The head of the linked list(stack).
 * <b>Notes:</b><br>
 * &nbsp;N/A<br>
 **/
Node *head_;
};
//####################################
// Constructor.
//####################################
template <class T> TStack <T>::TStack(){
 this->size_ = 0;
 this->head_ = NULL;
}
//####################################
// Destructor.
//####################################
template <class T> TStack <T>::~TStack(){
 // Nothing to tear down.
}
//####################################
// Class TStack Methods.
//####################################
template<class T> void TStack< T >::push(T elem){
 Node * newNode = new Node();
 newNode->data_ = elem;
 newNode->next_ = NULL;
 // If the head is NULL just assign it to newNode();
 if(this->head_ == NULL){
 this->head_= newNode;
 }else{
 newNode->next_ = this->head_;
 this->head_ = newNode;
 }
 this->size_ += 1;
}
template<class T> T TStack< T >::pop(){
// Suppress compile error for "Control reaches end
// of statement". We will throw an exception if the
// stack is empty.
#pragma GCC diagnostic ignored "-Wreturn-type"
 try{
 if(this->isEmpty() == false){
 Node *temp = this->head_;
 this->head_ = this->head_->next_;
 this->size_ --;
 return temp->data_;
 // If we just popped the last node, set head to NULL.
 if(this->isEmpty() == true)
 this->head_ = NULL;
 }else{
 throw std::out_of_range("The Stack Is Empty!");
 }
 }catch (const std::out_of_range& e) {
 std::cerr <<e.what() <<std::endl;
 }
}
template<class T> int TStack<T>::getSize(){
 return this->size_;
}
template<class T> bool TStack<T>::isEmpty(){
 if(this->size_ > 0)
 return false;
 return true;
}
//####################################
// End Class TStack Methods.
//####################################
//####################################
// End Class TStack.
//####################################
#endif

Example main.cpp:

#include <iostream>
#include "TStack.h"
int main(int argc, const char * argv[]) {
 int* one = new int(34);
 int* two = new int(68);
 int* three = new int(72);
 TStack<int*> myStack;
 myStack.push(one);
 myStack.push(two);
 myStack.push(three);
 while(myStack.getSize() > 0){
 int* ans = myStack.pop();
 std::cout<<"Value: "<<*ans<<std::endl;
 delete ans;
 }
 // Throws and catches exception gracefully and logs the stack is empty.
 int* ans = myStack.pop();
 return 0;
}

• Dan Mašek: Both getSize() and isEmpty() ought to be const. isEmpty() is unnecessarily complicated, return size_ == 0; would do. And what's up with all those this-> everywhere? Also, perhaps smart pointers for the nodes, to avoid potential leaks?
• pinkfloydx33: There are two statements after the return in pop, am I missing something?
• Loki Astari: The accepted answer is not good enough. It does not even mention the most important point. You missed the "Rule of Five (Three)". The answer by @ratchet freak at least covers this issue.
• Loki Astari: Your code can be highly simplified by using the Sentinel concept.
• Alex Reinking: The name TStack implies that it's a template variable. Should just be Stack.

Answer 1

Your code is pretty nifty, yet I have some comments:

Advice 1

In your destructor you should deallocate all the stack nodes, or, otherwise, you leak memory. Something like this:

template <class T> TStack <T>::~TStack(){
 Node* node = head_;
 Node* next;
 while (node)
 {
 next = node->next_;
 delete node;
 node = next;
 }
}

Advice 2

In you pop method, you effectively print a message to the standard output if the stack is empty. The better idea would be just throwing an exception and let the user catch it. Something like this:

template<class T> T TStack< T >::pop(){
 if (isEmpty())
 {
 throw std::runtime_error{"The stack is empty."};
 }
 T ret = head_->data_;
 Node* remove_node = head_;
 head_ = head_->next_;
 size_--;
 delete remove_node; // DON'T FORGET TO DELETE THE STACK NODE!
 return ret;
}

Advice 3

Also, consider providing the top method that just returns the topmost element without removing it.

• Miek: Perfect on Advice 2, then I don't have to worry about suppressing that compile error. Yep Top method is a good thought too. Thanks a bunch.
• CompuChip: Important detail: you silently added the delete which is missing in the OP to the pop function in your answer. May be worth expanding Advice 1 to include any destruction of nodes, not just the bulk action in the destructor.
• coderodde: @CompuChip Thanks! Added a nasty all-caps comment to the delete statement.
• Loki Astari: @Miek: The standard containers use a T& top() and void pop() because it is hard (impossible) to implement an exception safe T& pop(). Thus they split the operation into two methods. The first being exception safe.

Answer 2

If you have a destructor you should also define the copy constructor and copy assign + the move variants. Otherwise the compiler will generate its own (incorrect) copy and move facilities which will lead to dangling pointers and double frees.

When pushing the element is copied. You should also provide a move variant of push:

template<class T> void TStack< T >::push(T&& elem){
 Node * newNode = new Node();
 newNode->data_ = std::move(elem);
 newNode->next_ = NULL;
 // If the head is NULL just assign it to newNode();
 if(this->head_ == NULL){
 this->head_= newNode;
 }else{
 newNode->next_ = this->head_;
 this->head_ = newNode;
 }
 this->size_ += 1;
}

As an aesthetic point you can be a bit more frugal with the whitespace. Too much whitespace spreads out the relevant details too much which can make it harder to read.

• Felix Dombek: +1 Can't stress this enough! The code is really only complete when the Rule of 5 is implemented.
• Miek: Yes. Copy constructor. That's actually something I knew and forgot.

Answer 3

Your class looks nice in general. Still, here are some suggestions:

Advice 1

As pinkfloydx33 mentioned in the comments, in pop() you have two lines after the return, which are important and which are currently not reachable.

Advice 2

You should add a constructor to the Node struct which takes a T parameter, and then pass elem into the constructor in your new Node() call. The constructor would then initialize the Node::data member:

struct Node{
 Node (const T& elem)
 : data_(elem),
 next_(NULL)
 { }
 const T data_;
 Node* next_;
};

...

template<class T> void TStack< T >::push(T elem){
 Node * newNode = new Node(elem);

This has several advantages:

• you can use your stack class also for types that have no default constructor. With your current code this would cause a compile error.
• you save a call to the default constructor and to the assignment operator of T. Depending on T this can be a noticeable performance improvement.
• you can mark Node::data as const, so that you cannot accidentally change it somewhere else in your code
• you can be sure that Node::data and Node::next are initialized (you cannot forget to initialize it)

Advice 3

size_ should not be a signed int, since that type might not be large enough. Eg. on Linux x86_64 systems an int is only 4 bytes, so if you have more than 2³¹ elements on your stack the size_ member will overflow. Use something like size_t instead (and change the type of getsize() as well, of course).

Advice 4

In push() you use this->size_ += 1; but in pop() you use this->size_ --;. For consistency reasons you could change the push() method to use this->size_ ++;.

• Miek: Oops, (Advice 1) I move that from the else statement last minute and didn't catch that.

Answer 4

First thing's first, you have some major issues with your pop method.

• You correctly replace head with the next node in the chain but you never delete the previous node, leading to a memory leak.
• The method returns before you set the head to null on the empty condition.
• Less sever but you're comparing to true and false, which is a redundancy very commonly found in beginner code.

This should be rectified like so:

 if(!this->isEmpty()) // !true = false, !false = true
 {
 T data = std::move(temp->head->data); // Move the data out of the node
 Node *temp = this->head_;
 this->head_ = this->head_->next_;
 this->size_ --;
 delete temp; // Delete the node so it doesn't leak
 if(this->isEmpty()) // == true comparison was redundant
 this->head_ = nullptr; // Use nullptr, not NULL
 return data;
 }
 else
 {
 throw std::out_of_range("The Stack Is Empty!");
 }

More about std::move.

More about not using == true.

More about new and delete

---

Advice 1: Const Correctness

This is probably less important than other answers but you should try to make your code const-correct.

isEmpty and getSize should be marked const.

This means you'll be able to use them from a const reference to an instance of TStack.

Advice 2: nullptr

If you're using a modern (C++11 onwards) compiler, user nullptr instead of the archaic NULL.

Extra suggestion:

Add a const T& peek() const method so you can examine the top of the stack without removing it. This isn't completely necessary but if I were one of the people using your stack object I'd expect the peek operation to be available.

Answer 5

Follow the rule of zero.

That means your code shouldn't have a copy constructor, destructor, move constructor, or assignment operators.

To do this we write smart resource management types.

value_ptr is a smart pointer that can copy. It looks something like this:

template<class T>
struct value_ptr:std::unique_ptr<T> {
 using std::unique_ptr<T>::unique_ptr;
 value_ptr( value_ptr && ) = default;
 value_ptr() = default;
 value_ptr( value_ptr const& o ):
 value_ptr( bool(o)?value_ptr(new T(*o.get())):value_ptr() )
 {}
 value_ptr& operator=(value_ptr&&)=default;
 value_ptr& operator=(value_ptr const& o) {
 auto tmp = o;
 reset( tmp.release() );
 return *this;
 }
 ~value_ptr()=default;
};
template<class T, class...Args>
value_ptr<T> make_value_ptr( Args&&...args ) {
 return value_ptr<T>{ std::forward<Args>(args)... };
}

This is a value pointer. It is a smart pointer that has value semantics.

With this, we can follow the rule of 0 -- don't implement copy/move assign/construct or destructors.

We also want to keep track of a count. However, it is tied to the above value, and the above value gets zeroed when moved-from. So we need a counter that zeros when you move out of it:

template<class T>
struct zero_on_move {
 T t = {};
 zero_on_move(zero_on_move&&o):t(std::move(o).t){ o.t = T(); }
 zero_on_move& operator=(zero_on_move&&o){
 t = std::move(o).t;
 o.t = T();
 return *this;
 }
 zero_on_move(zero_on_move const&)=default;
 zero_on_move& operator=(zero_on_move const&)=default;
 ~zero_on_move()=default;
 zero_on_move(T&& tin):t(std::move(tin)){}
 zero_on_move(T const& tin):t(tin){}
 operator T&()&{return t;}
 operator T const&()const&{return t;}
 operator T()&&{return std::move(t);}
};

now we do:

struct Node{
 T data;
 value_ptr<Node> next;
};

we may have to ~Node(); and Node::~Node()=default;, if you get a strange error do that (and other =default), as we have a smart pointer to T within T.

Now our TStack becomes:

TStack()=default;
~TStack()=default;
TStack(TStack&&)=default;
TStack(TStack const&)=default;
TStack& operator=(TStack&&)=default;
TStack& operator=(TStack const&)=default;

make them explicitly default. Because.

The methods look like:

void push(T elem){
 auto next = make_value_ptr<T>(std::move(elem));
 using std::swap;
 swap(next, head);
 head->next = std::move(next);
 ++count.t;
}
T pop(){
 if (!head) throw std::out_of_range("ouch");
 auto next = std::move(head->next);
 using std::swap;
 swap(head, next);
 --count.t;
 return std::move(head.data);
}
T const& top() const {
 if (!head) throw std::out_of_range("ouch");
 return head->data;
}
T& top() {
 if (!head) throw std::out_of_range("ouch");
 return head->data;
}
int getSize()const{
 return count.t;
}
bool isEmpty()const{
 return !count.t;
}

and data fields in TStack of:

zero_on_move<int> count;
value_ptr<Node> head;

Here I use the style of doing things-that-throw in locals, modifying non-local (object) state in no-throwing operations, and bailing out on error early.