Stack array based implementation in C++

Question

I wrote my implementation to Stack array based. And I need a review for it to improve it and improve my coding skill. I also will but this implementation on my GitHub account.

One more thing: I am not sure why my stack works after I clear it. I used free which will free the allocated array from the heap memory and I then pushed to it after clearing it and it still work as the array didn't deallocate after calling the free

//======================================================
// Author : Omar_Hafez
// Created : 08 July 2022 (Friday) 2:45:23 PM
//======================================================
 
#include <iostream> 
#include <vector>
enum InsertStatus {FailedStackEmpty = -1, FailedStackFull = -2, OK = 0};
template<class T> struct Stack {
 int top = 0;
 int MAX_SIZE;
 T* array;
 Stack(int MAX_SIZE) {
 this -> MAX_SIZE = MAX_SIZE;
 array = (T*) malloc(MAX_SIZE*sizeof(T));
 }
 bool isEmpty() {
 return top <= 0;
 }
 bool isFull() {
 return top >= MAX_SIZE;
 }
 int stackSize() {
 return top;
 }
 InsertStatus push(T const& t) {
 if(isFull()) return FailedStackFull;
 array[top++] = t; 
 return OK;
 }
 InsertStatus pop() {
 if(isEmpty()) return FailedStackEmpty;
 top--;
 return OK;
 }
 void stackTop(T const& t) {
 t = array[top-1];
 }
 void clearStack() {
 top = 0;
 free(array);
 }
 void traverseStack(void (*function) (T& t)) {
 for(int i = 0; i < top; i++) {
 (*function) (array[i]);
 }
 }
};

• infinitezero: Thanks for accepting, but you should wait at least 24h, so you don't discourage other people from posting. There are a lot of people on here, that are far more proficient than I am :)
• Omar_Hafez: @infinitezero I see and thanks a lot for your great answer. This really helps me.
• Toby Speight: "I am not sure why my stack works after I clear it" - that's because you're into undefined behaviour, which means the program can do absolutely anything, including appearing to "work" some of the time. Your implementation of free() probably just makes the memory available for future allocations, but you could link against a debugging free() that overwrites, or run your program with Valgrind to help detect such errors.

Answer 1

#include only necessary headers

Reduce compilation time. Stack being a template class should be defined in a header file. Thus, irrelevant headers would needlessly get inside translation units along with Stack definition. <iostream> and <vector> are redundant here. #include <cstdlib> is sufficient for std::malloc and std::free.

Prefer class over struct for complex data structures

struct is useful for aggregate data structures that do not impose constraints on data. Internal data is exposed to users, and values of mutable members may be independently changed in unpredictable ways.

Data structures featured with user defined implementation constraints (e.g. invariants) must hide implementation details with private access specifier. Stack is such data structure. Its data members must be accessed only through carefully designed public methods to maintain constraints that should be initially established by class constructors. In general, if a class has a constructor, one should probably use class.

class Stack {
 public:
 /* user available methods */
 private:
 /* hidden implementation details */
 int top = 0;
 int MAX_SIZE;
 T* array;
};

Use simple and meaningful names

Don't repeat yourself.

template<typename T>
class Stack {
 public:
 /*...*/
 int size() const { /* ... */ }
 T& top() { /* ... */ }
 void clear() { /* ... */ }
 /*...*/
}; 

Restrict names visibility

Note that InsertStatus is not a scoped enum. Placed in global scope of a header file, it may cause name ambiguity problems.

#include "Stack.h"
/* enum InsertStatus { ..., OK = 0 } is available */
/* and OK is accessible as is */ 
static int OK = -1; // error, can't redefine in global scope
void foo() {
 std::string OK{"-1"}; // hides InsertStatus::OK
 cout << OK; // prints -1
}

Use scoped enum

enum class InsertStatus { /* ... */ } // separate type
/* ... */
class Stack {
 /* ... */
 InsertStatus pop() {
 /* ... */
 return InsertStatus::OK; // OK is accessible only when fully qualified
 }
};

or simply put enum in the class scope.

/* ... */
class Stack {
 public:
 enum InsertStatus { /* ... */ }
 /* ... */
 private:
 /* ... */
};
/* ... */
Stack<int> st(3);
if (st.pop() == Stack::FailedStackEmpty) { /* ... */ }

Stack also should be placed in a namespace to avoid possible name clash.

Use member initializer lists

Use member initializer lists in constructors to avoid redundant in-class member initialization.

class Sentence {
 public:
 Sentence(const std::string& s) {
 /* text was default initialized */
 text = s; // initial value is discarded
 }
 private:
 std::string text;
}; 

With member initializer list, constructor looks like this.

Sentence(const std::string& s)
 : text{s} // directly initialize text
{ }

Always test malloc return value

std::malloc returns null pointer if it fails to acquire a block of memory of required size, e.g. if MAX_SIZE is too big.

array = (T*)std::malloc(/* ... */);
if (array == nullptr)
 throw std::bad_alloc("Not enough memory");

Report the problem as soon as possible.

Avoid using C-style casts

static_cast, dynamic_cast and reinterpret_cast are conspicuous and functionally limited to prevent cast-related undefined behavior.

array = static_cast<T *>std::malloc(/* ... */);

Establish constraints in constructors

Prevent using invalid objects. Here, MAX_SIZE must be positive and array must not be null.

Stack(int capacity)
 : MAX_SIZE{capacity}
{
 assert(MAX_SIZE > 0);
 /* ... */ 
 assert(array != nullptr);
}

If throwing exception is not an option, invalid objects may be flagged accordingly.

class Stack {
public:
 Stack(int capacity)
 : MAX_SIZE{capacity}
 {
 /* ... */
 isValid = array != nullptr;
 }
 /* ... */
 bool valid() const {
 return isValid;
 }
private:
 bool isValid = false;
 /* ... */
};

Test your code extensively

Code that uses stackTop method fails to compile because stackTop attempts to assign a value to the const variable t. It compiles though if stackTop is not used because compiler instantiates only used template methods.

For classes owning resources, define (copy/move) constructors, (copy/move) assignment operators and destructor

Otherwise, some of them (maybe all) will be implicitly generated by the compiler and perform trivial behavior. Compiler generated (copy/move) constructors and (copy/move) assignment operators do simple memberwise value copy, and destructor does nothing. Such behavior causes resource (here memory) leaks.

Throughout its lifetime, an object should maintain a valid and comprehensible state

#include "Stack.h"
int main() {
 Stack<int> st(3);
 st.clearStack();
 // st is invalid because memory was freed
 st.push(5) // error, undefined behavior
 return 0; // st is destructed at the end of lifetime
}

• Toby Speight: Welcome to Code Review and thanks for this great first answer - I hope to see more from you in future!
• Toby Speight: I made some small improvements - hope that's okay.

Answer 2

C is not C++

You are mixing C with C++ and I'm not sure why. The question is tagged c++ but malloc and free are clearly c. Unfortunately, a lot of free coding tutorials online routinely give bad advice that mixes C and C++ or recommends some other highly discouraged practice. I'm glad to see you're not using using namespace std;. C works in C++, but that doesn't mean it should be used. Instead use new and delete or new[] and delete[]. But even then, there is rarely use for it. Instead use smart pointers, or std::vector for a dynamically allocated array. Speaking of the latter, you actually include vector, but never use it.

A stack is not an array

By definition, only the top element of a stack can be accessed. Yet you offer a function to traverse the stack. This is characteristic for a list or an array, which you use for your implementation, but really, a stack should not be implemented as an array, because then you can just use the array itself. This is similar to taking a car, sawing it in half and somehow claiming it's a motorcycle because it has two wheels.

free

As mentioned above, this should never appear in C++ code in the first place. Quoting from the linux man page

Any use of a pointer that refers to freed space results in undefined behavior.

free does not delete anything. It just tells the operating system, that you no longer want to use the memory at that location, and that it can be allocated by another (or the same) program. Accessing it is undefined behaviour and as long as it is not overwritten, the data might be still there and it can be still possible to access it.

const

You're already using const& if you want to avoid copying, that's good! You should also mark your functions const, if they do not modify your class/struct, e.g.

int stackSize() const{
 return top;
 }

How to actually implement a stack

I will use a class, not a struct, but this is my personal preference.

Instead of using C-style pointers or manually allocating memory, we will use smart pointers.

In short a smart pointer manages its memory automatically, so no need to call new/delete (or even malloc/free). The helper struct Stack_Elem contains the data and a pointer to the next data. So in a way, this is a linked list, except that it only offers access to the top element.

I chose to take the arguments as copy by value, not by reference, because we will need to do a copy anyway, to store in in the stack. After the initial copy in the push function, we std::move it, so no further copying happens. This of course requires any object you want to store in your stack to be movable. If you do not like that, you can change it back to const& and remove the std::move. Notice, that unique_ptrs can not be copied, only moved, because they are unique (a copy would make them non-unique, by definition).

#include <iostream>
#include <memory>
template<typename T>
class Stack{
 struct Stack_Elem{
 T data;
 std::unique_ptr<Stack_Elem> next;
 Stack_Elem(T data, std::unique_ptr<Stack_Elem>&& ptr)
 : data(std::move(data))
 , next(std::move(ptr))
 {}
 };
 std::unique_ptr<Stack_Elem> top;
 public:
 void push(T data){
 top = std::make_unique<Stack_Elem>(std::move(data), std::move(top)); 
 }
 T pop(){
 auto elem = top->data;
 top = std::move(top->next);
 return elem;
 }
 T const& peek() const{
 return top->data;
 }
 void clear(){
 top = nullptr;
 }
 bool is_empty() const{
 return !static_cast<bool>(top);
 }
};
int main(){
 Stack<int> stack;
 stack.push(1);
 std::cout << "top: " << stack.peek() << "\n";
 stack.push(2);
 std::cout << "top: " << stack.peek() << "\n";
 stack.push(3);
 std::cout << "top: " << stack.peek() << "\n";
 while( !stack.is_empty() ){
 std::cout << "popped: " << stack.pop() << "\n";
 }
 stack.push(1);
 stack.push(2);
 stack.push(3);
 stack.clear();
 while( !stack.is_empty() ){
 std::cout << "popped: " << stack.pop() << "\n";
 }
}

You can run it online!

• Toby Speight: The use of malloc() and free() is not only unidiomatic C++, but it's also broken: missing #include <cstdlib> and using std::malloc; using std::free;.