Fully Generic C++ Stack Implementation Without Lists, Arrays, or Vectors

Question

I'm trying to write a fully generic Stack in C++. I'm not sure if this is the best way to do this.

Right now I know that the Pop method needs improvement since if T is a value type, returning a nullptr will cause a compiler error. Also, I'm pretty sure that this can be optimized in a few ways, but I don't see any obvious areas at the moment. Are there any other specific ways this can be improved?

Any and all feedback is appreciated.

#ifndef STACK_H
#define STACK_H
template <class T>
class Stack
{
public:
 Stack();
 Stack(T& data);
 ~Stack();
 // Public Stack operations
 void Push(T& data);
 T Pop();
 void Clear();
 // Accessors
 const T& Top() const { return m_top->m_data; }
 const T& Bottom() const { return m_bottom->m_data; }
 bool IsEmpty() const { return m_size == 0; }
 int Size() const { return m_size; }
private:
 template <class T> struct StackNode
 {
 StackNode(T& data)
 {
 m_data = data;
 m_nextNode = nullptr;
 }
 T m_data;
 StackNode<T>* m_nextNode;
 };
 int m_size;
 StackNode<T>* m_top;
 StackNode<T>* m_bottom;
};
template <class T> Stack<T>::Stack()
{
 m_top = nullptr;
 m_bottom = nullptr;
 m_size = 0;
}
template <class T> Stack<T>::Stack(T& data)
{
 m_top = m_bottom = new StackNode<T>(data);
 m_size = 1;
}
template <class T> Stack<T>::~Stack()
{
 Clear();
}
template <class T> void Stack<T>::Push(T& data)
{
 StackNode<T>* newNode = new StackNode<T>(data);
 newNode->m_nextNode = m_top;
 m_top = newNode;
 ++m_size;
}
template <class T> T Stack<T>::Pop()
{
 if (!IsEmpty())
 {
 T returnData = m_top->m_data;
 StackNode<T>* temp = m_top->m_nextNode;
 delete m_top;
 m_top = temp;
 --m_size;
 return returnData;
 }
 // there is an issue here because if T is a value type, this will cause an error
 //return nullptr;
}
template <class T> void Stack<T>::Clear()
{
 if (!IsEmpty())
 {
 StackNode<T>* next = nullptr;
 do
 {
 next = m_top->m_nextNode;
 delete m_top;
 m_top = next;
 --m_size;
 } while (m_top != nullptr);
 m_top = m_bottom = nullptr;
 }
}
#endif

Answer 1

The best thing to do if the caller tries to Pop when the stack is empty is to throw an exception. You're right, there's no return value that makes sense.

You have a bug in void Stack<T>::Push(T& data). If the stack is initially empty, the m_top and m_bottom pointers are nullptr, but if an item is pushed onto an empty stack, the m_bottom pointer is never set.

There's no reason for Stack<T>::Clear() to decrement m_size within the loop. Just set it to 0 at any time. (Though, the compiler may be smart enough to notice this)

• Denmark: Thanks for catching that bug, I definitely fix that. I'm also going to add the exception to the Pop function as well as the accessors. I actually like decrementing the m_size variable, at least for now, since it makes stepping through while debugging a lot easier (I tested this with 21 elements).
• Denmark: Thanks for catching that bug, I definitely fix that. I'm also going to add the exception to the Pop function as well as the accessors. I actually like decrementing the m_size variable, at least for now, since it makes stepping through while debugging a lot easier (I tested this with 21 elements).