Stack implementation with a linked list

Question

Could anyone provide any constructive criticism? I'm trying to get a jump on data structures before classes start.

One thing is that I should add a copy constructor and assignment operator. Changes made: got rid of using namespace std.

As the code allows users to specify a cap, if they wish, for their stack any ideas of how I could signal that that particular stack is full? Currently I'm outputting a message from within the method but I don't like it when method handle output. What about a method that returns whether the stack is full?

#include <iostream>
using namespace std; // TESTING
template <typename T>
class Stack
{
public:
 Stack()
 : head(nullptr), capacity(0), currSize(0), sized(false) 
 {}
 Stack(int cap)
 : head(nullptr), capacity(cap), currSize(0), sized(true) 
 {}
 ~Stack();
 void push(T val);
 void pop();
 bool isEmpty() const { return head == nullptr; }
 int size() const;
 T top() const;
private:
 template <typename T>
 struct StackNode
 {
 StackNode() 
 :data(0), next(nullptr) 
 {}
 StackNode(T val, StackNode *ptr = nullptr) 
 :data(val), next(ptr) 
 {}
 T data;
 StackNode *next;
 };
 StackNode<T> *head;
 int capacity;
 int currSize;
 const bool sized;
};
template <typename T>
Stack<T>::~Stack()
{
 while (head != nullptr)
 {
 StackNode<T> *tmp = head->next;
 delete head;
 head = tmp;
 }
}
template <typename T>
void Stack<T>::push(T val)
{
 if (sized == false || currSize != capacity)
 {
 head = new StackNode<T>(val, head);
 ++currSize;
 }
 else cout << "stack full" << endl; //delete
}
template <typename T>
void Stack<T>::pop()
{
 if (head != nullptr)
 {
 StackNode<T> *tmp = head;
 head = head->next;
 delete tmp;
 --currSize;
 }
}
template <typename T>
int Stack<T>::size() const
{
 return currSize;
}
template <typename T>
T Stack<T>::top() const
{
 if (head != nullptr)
 {
 return head->data;
 }
 else return NULL;
}
int main()
{
 Stack<char> myStack(3);
 cout << "is isEmpty: " << myStack.isEmpty() << endl;
 cout << "push: "; myStack.push('H'); cout << myStack.top() << endl;
 cout << "push: "; myStack.push('G'); cout << myStack.top() << endl;
 cout << "push: "; myStack.push('B'); cout << myStack.top() << endl;
 cout << "push: "; myStack.push('D'); cout << myStack.top() << endl;
 myStack.pop();
 cout << "push: "; myStack.push('D'); cout << myStack.top() << endl;
 cout << "Size: " << myStack.size() << endl;
 cout << "Destroyed" << endl; myStack.~Stack();
 cout << endl << endl;
 system("pause"); // TESTING
 return 0;
}

• Simon Forsberg: Any reason you commented using namespace std; with // TESTING ?
• user3392999: So I don't get burned for using it lol
• Mast: @user3392999 Oh, you'll get burned for that anyway :-) Don't worry though, it isn't personal.
• user3392999: haha! True! Once I'm happy with it I'll change it, then again it's only for my own personal use in the house as I learn, but then again it's not good to get in bad habits :)

Answer 1

using namespace std; // TESTING

Judging by your comment, I'm guessing you're aware about the problems of exposing namespace members in the global scope. But did you know that you can using namespace inside scopes other than the global? It is fine if in your unit tests you want to expose the std stuff to make the code less verbose, but do that in the shortest possible scope then, in this case, inside main():

int main()
{
 // Make an exception since this is a unit test and expose
 // the whole Standard Library inside main(), so we don't have 
 // to std:: qualify everything.
 using namespace std;
 // same as before ...
}

---

 cout << "Destroyed" << endl; myStack.~Stack();

Very unusual for you to be calling the destructor for myStack. A destructor is called automatically when an object goes out of scope or is deleteed. There are very few cases where a programmer would manually call a destructor, those are not present here. If you just wan't to ensure the object is destroyed before the end of main(), to log some stuff, wrap its declaration inside a new scope. E.g.:

int main()
{
 {
 Stack<char> myStack(3);
 ...
 } // <== ~myStack() called here
}

This way you won't risk ending with a half destroyed object in your hands.

---

template <typename T>
T Stack<T>::top() const
{
 if (head != nullptr)
 {
 return head->data;
 }
 else return NULL;
 // ^^^^ problem here!
}

That will not work for a T type that is not a pointer or integer. NULL can be assigned to integers because it is usually implemented as #define for 0. That's one of the reasons why you should use nullptr whenever possible (C++11). If you had used nullptr, your test with T=char would have failed and you would have noticed this problem.

The usual convention for a generic stack is to throw an exception if you try to access the top for an empty stack. Returning a "default" value is less generic and also makes it harder for the caller to detect errors. Returning a default also requires the type T to be default constructible, so don't do it.

Same goes for popping on an empty stack. Right now you are not generating any errors. You should consider throwing and exception. Deriving a StackUnderflow exception type from std::runtime_error might be a good idea. Then you can extend the concept to a StackOverflow error when trying to push to the bounded stack. Granted that you can do with a simple std::runtime_error, but defining custom exception classes is a nice exercise if that's your point for writing this implementation.

---

cout << "push: "; myStack.push('H'); cout << myStack.top() << endl;

Don't pack that many statements in a single line. People read shorter columns of text much faster. But not just that, mixing several statements together makes it a lot easier for a quick read to miss some important part of it. Put each statement in its own line.

cout << "push: "; 
myStack.push('H'); 
cout << myStack.top() << endl;

---

Not a huge thing, but usually this kind of data structures uses std::size_t for things like size and capacity. That's an unsigned integer, which makes sense since the stack size is not meant to be negative, however, there is some discussion about avoiding unsigned integers, so that's up to you to decide if it is worth it.

---

Last thing is a bit of a big subject, which was introduced with C++11, called move semantics. Your code does some unnecessary copying of data on push and StackNode's constructor, which might affect performance when T is something other that a native type or pointer. I'll leave you with a couple references you can read to further learn about this:

• SO: What are move semantics?

• cppreference.com: Move constructors.

• user3392999: That's great thanks! One question - I used the destructor just go see if it did clear the stack, if I wanted a function to clear the stack should I just wrap the destructor in a method called clear() ?
• glampert: @user3392999, Sure! Having a public clear() is a good idea. That allows you to implement the destructor by simply calling the clear function.

Answer 2

You've quite correctly marked the Stack full printout with a delete comment, however you must give an indication that push failed. An easiest way is to make it return bool.

It is unclear why do you want to restrict stack capacity. The only reason of implementing stack via a linked list (as opposed to fixed-size array) is to have a virtually unlimited capacity.

StackNode default constructor is never used (and never shall be used), so I recommend to make sure it is never called. In any case it should initialize data as data(T(0)).

• user3392999: Won't the default constructor be called if I don't specify a value? Such as Stack<int> myStack ?
• glampert: @user3392999, vnp meant the default constructor you've written for StackNode. Which is not useful because you only crate stack nodes with new StackNode<T>(val, head);. To prevent misuse of StackNode, you could either make the default constructor private or delete it altogether with StackNode() = delete; in the declaration.