C++ Stack using template

Question

I'm learning C++, so I wrote a stack with the help of templates. I'm wondering if there is anything I can improve or if I did something vastly wrong.

Stack.h

#pragma once
#include <ostream>
template <class Type>
struct Node {
 Node(Type data, Node<Type>* next) 
 : data(data), next(next) {}
 Node* next;
 Type data;
};
template <class Type>
class Stack
{
public:
 Stack() : length(0), topNode(NULL) {
 }
 ~Stack() {
 while (!isEmpty()) {
 pop();
 }
 }
 void push(Type data) {
 Node<Type>* newNode = new Node<Type>(data, topNode);
 topNode = newNode;
 ++length;
 }
 Type pop() {
 if (!isEmpty()) {
 Node<Type>* popped = topNode;
 Type poppedData = popped->data;
 topNode = popped->next;
 --length;
 delete popped;
 return poppedData;
 }
 throw new std::exception("Stack underflow!");
 }
 bool isEmpty() {
 return length == 0;
 }
 void print() const {
 Node<Type>* tempTop = topNode;
 while (tempTop != NULL) {
 std::cout << tempTop->data << endl;
 tempTop = tempTop->next;
 }
 }
 int count() const {
 return length;
 }
private:
 Node<Type>* topNode;
 int length;
};

Main.cpp

#include <iostream>
#include "Stack.h"
using namespace std;
int main() {
 Stack<int> myStack;
 // Push some values
 myStack.push(2);
 myStack.push(4);
 myStack.push(8);
 myStack.push(16);
 myStack.push(32);
 // We pop the 32
 myStack.pop(); 
 // Display count after the pop
 int lastPopped = myStack.pop();
 cout << "Popped value: " << lastPopped << ", Count: " << myStack.count() << endl; 
 // Print whole stack
 cout << endl << "Stack print: " << endl;
 myStack.print(); 
 // Exit program when the 'any' key is pressed.
 system("PAUSE");
 return 0;
}

Answer 1

If you provide a destructor you should handle copying and assigning. In other words follow the Rule of 3 (or 5 if you care about move semantics). You can also disallow them but then there should be move constructor and assignment.

Otherwise you will get in trouble with double freeing when calling a function void foo(Stack<int> s).

---

empty() doesn't change the stack. So it should also be const.

Consider adding a peek() method that returns a reference to the top value of the stack (with const and non-const version).

T& peek()
{
 return topNode->data;
}
const T& peek() const
{
 return topNode->data;
}

The reason for using the reference is to avoid a unnecessary copy.

---

Having a print method interacting with the console is not a good idea. What if you want to show the contents in a gui instead?

Instead add iterators to be able to inspect what is on the stack without having to capture the output that print() generates.

• Synxis: I guess you mean T& (and const T&) instead of &T (and const &T) ?

Answer 2

Include guards

Rather than relying on #pragma once, you should use an include guard in your Stack.h file instead, like this:

#ifndef STACK_TYPE_H_
#define STACK_TYPE_H_
// Original code for Stack.h goes here.
#endif

While #pragma once is supported across many compilers, there's always the chance that there is one that doesn't support it because it still isn't standard. If you feel the need to use both #pragma once and include guards, just do something like this:

#ifndef STACK_H_
#define STACK_H_
#pragma once
// Original code for Stack.h goes here.
#endif

---

Passing by const reference

If you never modify the value of an argument when you pass it, like in the push function:

void push(Type data) {
 ...
}

Rather than passing the value normally, you should pass it by const reference, like this:

void push(const Type& data) 
{
 ...
}

While this is a micro-optimization for "small" types, like int, or bool, when you start dealing with "bigger" types, like std::string, or a user-defined type, doing this becomes a little more important.

---

Nitpicks

While your test file containing main isn't such a huge deal, there are still a few bad things I want to point out about it.

First off, this line:

using namespace std;

Is as really bad habit to get into. It can also result in many bad things happening, especially if you're using Boost, which provides alternatives to some of the functions in std. Some of the bad things that can happen can be found here.

This line here should be removed as well:

system("PAUSE");

Preferably if you need to display output for the user to see, you should use something like this instead:

std::cin.get();

system("PAUSE"); is bad, for the following reasons:

• It's slow and un-optimal.
• It's insecure.
• It's very platform-dependent.

Preferably, as it is the C++ style, you should define you class and it's function/constructor signatures inside Stack.h, and then create a file named Stack.cpp where you implement the function/constructors.

Finally, your isEmpty function should be const, since it isn't modifying anything. That means that this:

bool isEmpty() {
 return length == 0;
}

Should become this:

bool isEmpty() const {
 return length == 0;
}

• Caresi: Thanks for your suggestions! The curly braces seem very subjective to me as the community do 50/50. Also Why is System("Pause") bad? And I wrote everything in the header file because I couldn't get Templates to work with it.
• KRyan: #pragma once offers so many advantages over guards that I strongly disagree that guards should be used in the general case. The choice between #pragma once is one that deserves some consideration, not just "use guards because they always work!" (because they don’t, in the far-more-likely case of name conflicts).
• Morwenn: @KRyan #pragma once does not offer so many advantages. Name conflicts are orthogonal. That means that you didn't use namespaces properly and you should feel bad about it :( Also, from a speed point of view, GCC at least recognizes include guards and is able to make proper optimizations too.
• KRyan: @Morwenn The preprocessor does not have any notion of namespaces, and if you have two files that use #ifndef STACK_H_ #define STACK_H_ in the same compilation, one of them is not going to be included (or, at least, nothing between the guards will be). Keeping track of all of the guard names in your compilation (including those of any third-party libraries that are being included) to avoid this is a large burden, one that should be taken on only when truly necessary (i.e. you really do need this to be compilable on those few compilers that don’t support #pragma once).
• Morwenn: @KRyan No, seriously, a longer name reduces it as much as a namespace does, so you generally just have to check that there isn't a library with the same name as yours (a quick search in a search engine and you're done). I've never heard of two serious libraries with conflicting header guard names. There isn't any plan to standardize #pragma once because there is work to standardize modules, but it probably won't be finished for the next revision of the standard. Also, having a consistent naming scheme should be something to strive for anyway.

Answer 3

This is my first code review, anyway.

1. struct Node

   I would have put in namespace detail or made this class a private nested class in your Stack

2. void push(Type data)

   Is your Stack only for int or for user defined types also? This push is OK for ints and doubles but for user defined types I would have written:

   void push(const Type& data)
   

3. Type pop()

   Since copying an instance of Type might throw I would have created

   Type& front();
   void pop();
   

4. throw new std::exception("Stack underflow!");

   If I am correct std::exception has no constructor std::exception(const char*), so use std::runtime_exception.

5. throw new std::exception("Stack underflow!");

   Do not use new, just write

   throw std::runtime_exception("Stack underflow!");
   

   http://ptgmedia.pearsoncmg.com/images/0321113586/items/sutter_item73.pdf

6. You should provided copy constructor and the assignment operator for Stack. If it is C++11 then also move constructor and move assigment

7. Since your pop() returns a value you can clear your stack in ~Stack() in more lightweight way

• Caresi: Hello! Thank you for your intressting details! 1 and 5 is pretty forward however I'm very curious on how #2 and #3 will benefit and why the C++ version matters?
• Caresi: Also why should I provide a copy constructor and assigment?
• SuperBiasedMan: Aside from Caresi's questions, it's generally good practice to explain the benefits of the changes you're suggesting. Just telling someone to change their code doesn't teach them a lot.