# Abstract Data Type: Stack implementation in C++

While trying to get better at C++ I tried my hand at making a stack implementation. This is the result:

#include<iostream>

template<typename T>
struct Node {
T data;
Node *next;
Node(T data, Node *next) : data(data), next(next) {}
};

template<typename T>
class Stack {
public:
Stack() : top(nullptr), level(0), max_size(10) {}
Stack(int max_size) : top(nullptr), level(0), max_size(max_size) {};
void push(T data);
T pop();
void display();
bool isEmpty() { return level == 0; }
bool isFull() { return level == max_size; }
int geLevel() { return level; }
int getMaxSize() { return max_size; }

private:
Node<T> *top;
int level, max_size;
};

template<typename T>
void Stack<T>::push(T data) {
if(!isFull()) {
Node<T> *newNode = new Node<T>(data, top);
top = newNode;
level++;
} else {
std::cerr << "stack overflow";
}

}

template<typename T>
T Stack<T>::pop() {
if(!isEmpty()) {
Node<T> *temp = top;
T data = temp->data;
top = top->next;
level--;
delete temp;
return data;
}

std::cerr << "stack underflow";

}

template<typename T>
void Stack<T>::display() {
Node<T> *curr = top;
while(curr != nullptr) {
std::cout << curr->data << std::endl;
curr = curr->next;
}
}


Any help would be appreciated to make this code mor C++'ish.

• There is a standard stack. std::stack if you want to implement it you may want to model your interface after it. The reason that pop() in the standard version returns void is that a pop that returns a value can not be made exception safe. So instead they use two methods top() this retrieves a reference to the top value and pop() simply removes the top value. – Martin York Jun 25 '18 at 15:41
• @MartinYork: It can be made conditionally exception-safe though, depending on the move-ctor of T. – Deduplicator Jun 26 '18 at 8:18

It seems a stack is the HelloWorld of C++ classes and memory management :).

First, your class has no destructors. It means that when your instance will be destroyed, it will only deallocate the stack attributes : top, level and max_size. Notice that it deallocate the pointer top, but not the object pointed by top ! You must define a destructor : ~Stack(), which will likely consists in a loop executing pop() while the stack is not empty.

Remember that when you are encapsulating pointers, you must respect the Rule of Three (known also as Rule of Five) : it is a simple but accurate rule which can be interpreted as :

If you need to specify one of destructor/Copy Constructor/Copy Assignment Op; then you probably have to define all three.

Here, it applies because you are holding a pointer, whose value is deleted in the destructor. So if you do the default copy, for instance Stack<T> s2 = s1;, it will copy the data members of s1 into s2. It means that s2.top == s1.top. So when one get destroyed, for instance s1, it will delete s1.top, but then s2.top points to deleted memory : ERROR.

While you are defining copy-constructor and copy-assignment, you may want to define move-constructor Stack(Stack&& other) and move-assignment Stack& operator=(Stack&& other). T&& means "Movable T" and signifies "This value is temporary, so there is no problem if it is altered". For example, here, it means you can only swap other.top and this->top, so you do not need to copy each node of the stack.
Both move-constructor and move-assignment are parts of the Rule of Five, which is an extent of the Rule of Three above.

You use std::cerr to showing errors. It is not the right way to do this : for example, if push() results in an error, the code calling push has no way to know it. The program will continue to run as usual.

C++ has a specific way to handle errors : exceptions. I will not detail here but follow the link and give it a try.

Moreover, in your pop() function, there is a problem. If the stack is empty, there is no return value ! Your compiler should at least warn you (if not yelling at you) that one conditional-branch has no return value. Instead, you should throw an exception, or, if it is intended, use std::optional<T>. std::optional can represent two states : empty, or full. If it is full, you can access to T value.

Do you know the keyword const in method declaration ? It means it will not modify the object during its execution. Examples :

bool method_A() const; //declaration
int method_B() const { /* definition */ }


You need the keyword const in both declaration and definition. Currently, the functions which can be marked const are display(), isEmpty(), isFull(), getLevel() and getMaxSize().

One of the purpose is the const-ref argument. For example :

template<typename T>
void printLevel(Stack<T> const& stack) {
std::cout << "Nb levels = " << stack.getLevel() << std::endl;
}


The argument type is a const-ref (one & means reference). It means that, because it is a reference, the argument is not copied, but you can not modify it : "read-only" (because of const). Having a const-ref variable means you can only access to const methods.

Also, you can optimize memory management by using smart pointers. I will not explain this here, but please check out my answer to another stack implementation, which details how can smart pointers be used.

Something you should do is defining max_size constant :

public:
const int max_size;


Notice that this is ok to set max_size public, because it is a constant and it won't be modified by external code.

• I disagree with the comments on pop. There is no need to throw an exception if you pop a non existent value. As there is a isEmpty() method that allows the caller to check if they should call pop(). Now if you want to have a checked version then you should provide both a checked and unchecked version. Remember (a massive C++ principle) I should not need to pay for checks I don't need just because there are beginners that need to have checks in place. – Martin York Jun 25 '18 at 16:55
• Can you add comments on Move Semantics and const methods. Then I don't need to write anything. – Martin York Jun 25 '18 at 16:56
• @MartinYork, so that is why I rarely see your answers lately :) I don't know if it is a good or bad thing for CR. – Incomputable Jun 25 '18 at 17:22
• @MartinYork Done, I didn't thought of const methods, but it clearly deserves a comment. Move semantics are not something I am comfortable with so feel free to correct me if I say something wrong – Julien Vernay Jun 25 '18 at 18:06
• Typo: copy assignment operator== has one too many equal signs. – Cris Luengo Jun 26 '18 at 0:53
#include<iostream>


Avoid <iostream> in headers unless you absolutely need it. Static constructors are transparently injected into every translation unit that includes <iostream>, which also means every translation unit that includes your header. If you want to provide IO utilities, separate those IO functions from your data structure.

Where is the header guard to prevent guard against multiple inclusion?

template<typename T>
struct Node {
T data;
Node *next;
Node(T data, Node *next) : data(data), next(next) {}
};


Hide implementation details from the users of your library.

Is aggregate initialization not good enough? Do you need a default constructor?

        Stack() : top(nullptr), level(0), max_size(10) {}
Stack(int max_size) : top(nullptr), level(0), max_size(max_size) {};
...
private:
Node<T> *top;
int level, max_size;


When initializing data members with constant initializers, prefer in-class member initializers.

        Stack() = default;
Stack(int max_size) noexcept : max_size(max_size) {};
...
private:
Node<T>* top{nullptr};
int level{0};
int max_size{10};


        void push(T data);


For arguments are cheap to copy, prefer to pass by value. When arguments are expensive or unknown, prefer to pass by reference to const. There are exceptions, like arguments that are consumed, but in general, the two above rules cover most cases.

        bool isEmpty() { return level == 0; }
bool isFull() { return level == max_size; }
int geLevel() { return level; }
int getMaxSize() { return max_size; }


None of these functions modify the stack and should be accessible in a const context. You should specify these member functions with const.

Prefer following standard naming conventions so your stack can be used with existing library solutions. isEmpty() should be empty(), geLevel() should be size(). getMaxSize() should be max_size(), or even capacity().

The built-in types are convertible to bool. For int types, any non-zero value is true.

        bool empty() const { return !full(); }
bool full() const { return level; }
int size() const { return level; }
int max_size() const { return max_size; }


    private:
Node<T> *top;
int level, max_size;


Only one variable declaration per line.

template<typename T>
void Stack<T>::push(T data) {
if(!isFull()) {
Node<T> *newNode = new Node<T>(data, top);
top = newNode;
level++;
} else {
std::cerr << "stack overflow";
}
}


If you are checking for overflow, you should do something to notify the caller that the operation failed besides logging to the console.

template<typename T>
T Stack<T>::pop() {
if(!isEmpty()) {
Node<T> *temp = top;
T data = temp->data;
top = top->next;
level--;
delete temp;
return data;
}

std::cerr << "stack underflow";
}


What is the responsibility of pop()? The function tells me its removing the top element. What does making a copy of the data and returning it have to do with removing the top element? If someone wants the top element, then there should use the accessor for it (peek()?).

Focusing on design, what exactly makes this stack an abstract data type? Where is the abstraction? I would expect a stack that defined certain operations over any type of container that maintained insertion order and allowed access, insertion, and deletion from the same end. A queue is similar, except insertion is done on the opposite end from access and deletion. Read up on the adaptor pattern.

Is stack an appropriate name? Because it doesn't support growth beyond a fixed size, perhaps you should call it a Fixed Stack?

Because your Stack is managing a responsibility, a resource (specifically the lifetime management of dynamically allocated nodes), you should consider how the five special member functions behave in that context.

~Stack() = default;                       // Doesn't delete allocated nodes
Stack(Stack const&) = default;            // Doesn't deep copy
Stack(Stack &&) = default;                // Does deep move
Stack& operator=(Stack const&) = default; // Doesn't deep copy
Stack& operator=(Stack &&) = default;     // Does deep move


Since C++11, move operations became standardized. Consider supporting them (move construction, move assignment, move-based swap/push/emplace).

If you would like your containers to work with standard facilities, consider looking at the requirements outlined by the standard.

http://eel.is/c++draft/container.requirements.general

http://eel.is/c++draft/stack

• The STL has taught all C++ programmers that pop is supposed to remove the top element. But the only reason it does this in the STL is for exception safety. The classical POP operation extracts the top element (i.e. removes it from the stack and returns it to the caller). You other comments I like. :) – Cris Luengo Jun 26 '18 at 0:59

Well, it's a good start, but there's much to improve or fix:

1. Don't interact with the user unless explicitly requested. Report errors to the caller with exceptions or error-codes, only take it into your own hands when you detect a violation of the programs invariants which necessitate an abort.

2. If you provide a way to print something, follow C++ conventions by allowing the caller to specify the target, and overloading operator<< to do it.

3. Following the two points above allows you to move from including <iostream> to just <iosfwd>. Minimal includes reduce compile-times, and <iostream> is special in that including it initializes C++ streams, extra work which is probably wasted.

4. Generally take a look at the standard library for naming conventions. Following them allows you to use standard algorithms, and significantly reduces the mental overhead of using your code.

5. Node<T> is an implementation-detail of Stack<T>, and should thus be hidden as a private member.

6. Consider using aggregate initialization for Node. Doing so allows you to easily allow for emplacing a new value, which might be far more efficient.

7. Using the above pushing a const T& or T&& is trivially implemented by delegation.

8. As a matter of preference, and to simplify adding an iterator-interface if wanted, I prefer putting the linking-pointers first in the node. Something to consider.

9. Use in-class-initializers for the members, and you can simplify your ctors.

10. Follow one of the rule of zero (meaning the members manage all resources), the rule of three (ctor, op-assign and dtor as the class is responsible for some resource) or the rule of five (same as rule of three, but extended to C++11 move-semantics).
Currently, you have custom ctors, but keep the ill-fitting automatic assignment and dtor.

11. Mark any unary ctor as explicit unless you really want it used for implicit conversions.

12. Look whether you can mark a ctor constexpr so a stack can be initialized statically.

13. Use move-semantics where they make sense. Doing so is potentially more efficient, or even possible at all.

14. Consider separating retrieval / inspection of the top-value from removing it. Doing that allows for more efficient code.

15. When I see a != nullptr, a != 0, a != false or the like, I always wonder why don't you add another comparison. And another one on top of that. a by itself is quite sufficient, or !!a if you need a bolean value immediately.

16. Mark member-functions const when they don't modify the object. Const-correctness helps write correct code.

17. Mark functions noexcept if they cannot ever throw an exception. Doing so allows more efficiency, and eases the writing of exception-safe code.