Your stack implementation is terrible, and so is @hc_dev: neither handles memory correctly.
Resource Handling
It is generally frowned upon to call new
and delete
directly, simply because doing it correctly is hard.
Proper resource handling requires:
- Thinking about moves.
- Thinking about copies.
- Thinking about destruction.
This used to be called the Rule of 3 in C++03 (Copy Constructor, Copy Assignment Operator and Destructor) and is called the Rule of 5 since C++11 (+Move Constructor, +Move Assignment Operator).
Your current Stack implements neither of those 5 operations correctly -- it doesn't implement them at all, and the default generated operations are buggy due to your use of a raw pointer.
The best advice for resource handling, though, is to use the Rule of Zero: just delegate it to something that works!
In your case, look into std::unique_ptr
and std::make_unique
!
Corrected resource management:
struct StackElement {
char value;
std::unique_ptr<StackElement> next;
StackElement(char value, std::unique_ptr<StackElement> next) :
value(value), next(std::move(next)) {}
};
struct Stack {
std::unique_ptr<StackElement> top = nullptr;
bool isEmpty() { return top == nullptr; }
void push(char value) {
top = std::make_unique<StackElement>(value, std::move(top));
}
char pop() {
assert(!isEmpty());
char toBeReturned = top->value;
top = std::move(top->next);
return toBeReturned;
}
};
This struct
is no longer copiable, as std::unique_ptr
is not copiable.
Limited stack depth.
The previous rewrite is good, but its destructor suffers from stack overflow (!).
That is, when the destructor is executed, you get:
- Call destructor of
Stack
- Call destructor of
Stack::top
- Call destructor of
StackElement
(stack->top
)
- Call destructor of
StackElement::next
.
- Call destructor of
StackElement
(stack->top->next
)
- ...
To handle this, create a clear
method, and manually write the destructor.
struct Stack {
// ...
Stack(Stack&&) = default; // automatic generation is disabled when
// the destructor is explicit, so explicitly
// ask for it.
Stack& operator=(Stack&&) = default; // automatic generation...
~Stack() { clear(); }
void clear() {
while (!isEmpty()) {
pop();
}
}
};
General
Once you have the memory part correct, further improvements:
- Encapsulation: do not expose your privates.
- Generalization: make it work for any type.
This yields:
// No need for a class here, it's internal.
template <typename T>
struct StackElement {
StackElement(T value, std::unique_ptr<StackElement> next):
value(std::move(value)), next(std::move(next)) {}
T value;
std::unique_ptr<StackElement<T>> next;
};
template <typename T>
class Stack {
public:
~Stack() { this->clear(); }
Stack() = default;
Stack(Stack&&) = default;
Stack& operator=(Stack&&) = default;
bool isEmpty() const { return this->head == nullptr; }
T const& top() const {
assert(!this->isEmpty());
return this->head->value;
}
void clear() {
while (!isEmpty()) {
this->pop();
}
}
void push(T value) {
// Create empty node first, in case moving `value` throws an exception.
auto neo = std::make_unique<StackElement<T>>(std::move(value), nullptr);
neo->next = std::move(this->head);
this->head = std::move(neo);
}
T pop() {
assert(!isEmpty());
// Pop top first, in case moving `current->value` throws an exception.
auto current = std::move(this->head);
this->head = std::move(current->next);
return std::move(current->value);
}
private:
std::unique_ptr<StackElement<T>> head;
};
Miscellaneous
There are few nits in your main
:
- There is no need to allocate
Stack
on the heap, just Stack stack;
works.
- Don't use
std::endl
, just use '\n'
or "\n"
.
std::endl
both appends \n
and calls flush
, the latter kills all performance benefit of internally buffering.
With that in mind, the rewritten main
is:
int main() {
Stack<char> stack;
std::cout << "Created a stack at " << &stack << "\n";
int number_of_inputs;
std::cout << "Enter the number of elements you want to push at the stack: ";
std::cin >> number_of_inputs;
for (int i = 0; i < number_of_inputs; i++) {
char input;
std::cin >> input;
stack.push(input);
}
std::cout << "- - - - - - - - - - - - - - - - " << "\n";
std::cout << "Displaying content of the stack: " << "\n";
while (!stack.isEmpty()) {
std::cout << stack.pop() << "\n";
}
return 0;
}
std
stack is implemented viastd::vector
by default. The thing is linked list is slow as allocating new item per push is too much.std::vector
stores data contiguously allowing much better performance on all fronts. \$\endgroup\$pop()
to return an internal data object. Shouldn't it return the value? \$\endgroup\$