#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 withStack definition.<iostream> and<vector> are redundant here.#include <cstdlib> is sufficient forstd::malloc andstd::free.

Preferclass overstruct 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 withprivate access specifier.Stack is such data structure.Its data members must be accessed only through carefully designedpublic methods to maintain constraints that should be initially established by class constructors. In general, if a class has a constructor, one should probably useclass.

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 thatInsertStatus is not a scopedenum. 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 scopevoid foo() {   std::string OK{"-1"}; // hides InsertStatus::OK   cout << OK; // prints -1}

Use scopedenum

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

or simply putenum 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 testmalloc return value

std::malloc returns null pointer if it fails to acquire a block of memory of required size, e.g. ifMAX_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 andreinterpret_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 andarray 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 usesstackTop method fails to compile becausestackTop attempts to assign a value to theconst variablet.It compiles though ifstackTop 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}

• \$\begingroup\$Welcome to Code Review and thanks for this great first answer - I hope to see more from you in future!\$\endgroup\$

  Toby Speight

  – Toby Speight

  2022-07-30 08:42:45 +00:00

  CommentedJul 30, 2022 at 8:42
• \$\begingroup\$I made some small improvements - hope that's okay.\$\endgroup\$

  Toby Speight

  – Toby Speight

  2022-07-30 08:59:00 +00:00

  CommentedJul 30, 2022 at 8:59

C is not C++

You are mixing C with C++ and I'm not sure why. The question is taggedc++ butmalloc andfree are clearlyc. 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 seeyou're not usingusing namespace std;. C works in C++, but that doesn't mean it should be used. Instead usenew anddelete ornew[] anddelete[]. But even then, there is rarely use for it. Instead use smart pointers, orstd::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 thelinux 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 usingconst& 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 usesmart pointers.

In short a smart pointer manages its memory automatically, so no need to call new/delete (or even malloc/free). The helper structStack_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, westd::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 toconst& and remove thestd::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!

• \$\begingroup\$The use ofmalloc() andfree() is not only unidiomatic C++, but it's also broken: missing#include <cstdlib> andusing std::malloc; using std::free;.\$\endgroup\$

  Toby Speight

  – Toby Speight

  2022-07-30 08:45:17 +00:00

  CommentedJul 30, 2022 at 8:45

• c++
• stack