8
\$\begingroup\$

I've recently started teaching myself basic C++ and decided to implement a simple stack with pointers.

#include <iostream>

using namespace std;

struct StackElement {
    char value;
    StackElement* next;

    StackElement(char value, StackElement* next) : value(value), next(next) {}
};

struct Stack {
    StackElement* top = NULL;

    bool isEmpty() { return top == NULL; }

    void push(char value) {
        StackElement* newElement = new StackElement(value, top);

        top = newElement;
    }

    StackElement pop() {
        StackElement* toBeDeleted = top;
        StackElement toBeReturned = *top;

        top = top->next;
        delete toBeDeleted;
        return toBeReturned;
    }
};

int main() {
    Stack* stack = new Stack();
    cout << "Created a stack at " << &stack << endl;

    int number_of_inputs;
    cout << "Enter the number of elements you want to push at the stack: ";
    cin >> number_of_inputs;

    for (int i = 0; i < number_of_inputs; i++) {
        char input;
        cin >> input;
        stack->push(input);
    }

    cout << "- - - - - - - - - - - - - - - - " << endl;
    cout << "Displaying content of the stack: " << endl;

    while (!stack->isEmpty()) {
        cout << stack->pop().value << endl;
    }

    return 0;
}

My questions are: - what could be generally done better here? - is the pop() method written correctly? Does it create any memory leaks? Is there a way to write it shorter?

Thank you in advance! (And forgive use of using namespace std)

\$\endgroup\$
  • 4
    \$\begingroup\$ In std stack is implemented via std::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\$ – ALX23z May 14 at 9:58
  • 2
    \$\begingroup\$ Just a quick comment about writing a class like this. Start with behaviors. What do you want this to do? What do you want this to NOT do? Verify behavior with unit tests. Make sure to test both the things you want it to do and what you don't want it to do. The first thing I would ask someone new to do is to write a test that pushes once, but then pops twice. What behavior would you expect? What actually happens. \$\endgroup\$ – Ben May 14 at 15:49
  • 2
    \$\begingroup\$ It's unusual for pop() to return an internal data object. Shouldn't it return the value? \$\endgroup\$ – Pete Becker May 14 at 21:47
20
\$\begingroup\$

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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I highly appreciate your detailed explanation. Thank you. However, if I wanted to use STL, I'd just #include <stack> and that'd be it. I'm doing this to learn myself a bit about dynamic data structures in CPP and want to do it using raw pointers and not those "cool" shared and unique ones. \$\endgroup\$ – Bartek Pacia May 14 at 12:51
  • 4
    \$\begingroup\$ @Baftek: Then my advice is Separation of Responsibility. The Stack class is already managing the stack logic, it should not also fiddle with low-level new/delete. Instead, you should create a Box, Ptr, unique_ptr class that handles those low-level details correctly, and then implement Stack on top. Box will handle the technical details of managing a resource (memory, here), and Stack will handle the functional details of implementing a stack. This means you can test Box in isolation, and in Stack you don't have to worry about those details any longer. \$\endgroup\$ – Matthieu M. May 14 at 14:41
  • 3
    \$\begingroup\$ @hc_dev: Please don't take the "blame" personally, it's your answer I warn against, not you. As for C++ books, and online tutorials, unfortunately most are terrible or terribly outdated. A curated list of known good books is maintained on Stack Overflow, and even helpfully "sorts" the books for various levels of expertise. If you have the choice, pick one of those. \$\endgroup\$ – Matthieu M. May 14 at 16:25
  • 1
    \$\begingroup\$ @Emily Surely, for logging, you should be using an unbuffered stream, like std::clog? \$\endgroup\$ – Cody Gray May 15 at 4:57
  • 3
    \$\begingroup\$ @PeterCordes Pass by reference-to-const is only faster if the function doesn't need to copy or mutate the referenced object. If it does, then you're stuck always doing a full copy and never a move. Pass by value allows the caller the flexibility to have the object be copied or moved as appropriate. The alternative is to have two overloads: one that accepts its parameter by reference-to-const and one that accepts its parameter by rvalue-reference. \$\endgroup\$ – Miles Budnek May 15 at 21:39
5
\$\begingroup\$

1) You can use templates to extend the functionality of your stack class to other types.

2) Use nullptr instead of NULL.

3) Implement Stack as a class instead of struct, since the former has private access specifier as default. You don't want users of this library to be manually able to access top.

4) pop() should return the value stored, not StackElement.

5) Your solution leaks memory. Your current way of releasing memory is assuming that the user will pop() on all elements; more of than that, it will not be the case. Consider this:

int main()
{
 {
   Stack st;
   for(auto i = 0; i < 10; i++)
   {
      st.push(static_cast<char>(i));
   }
  }
}

No pop() is called, and st object is deleted. All the allocations aren't deallocated, and you're leaking memory. The C++ way to solve this is RAII - delete all the elements in the destructor.

6) using namespace std is generally frowned upon.

7) Wrap your code inside a namespace.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ All valid points, except that the OP explicitly asked to be absolved from the sin of using namespace std. \$\endgroup\$ – Peter - Reinstate Monica May 14 at 9:18
  • 3
    \$\begingroup\$ @Peter-ReinstateMonica: Just because they ask not to be reprimanded for something doesn't mean answerers are not allowed to, as they are allowed to comment on any and all aspects of the code. However, for something minor as this I agree. In addition, I edited your edit to remove the tracking of your user ID from the link. Not sure what the policy is for this, but it felt weird for you to get the referrals on a link in somebody else's answer. \$\endgroup\$ – Graipher May 14 at 9:23
  • 1
    \$\begingroup\$ @Graipher (UID): Oh, I was not aware of that! I simply clicked "share" and copied the URL. Right, it mentions that in the accompanying text. So it's better to copy from the URL in the address field... funny. \$\endgroup\$ – Peter - Reinstate Monica May 14 at 10:02
3
\$\begingroup\$

In addition to Rish's good answer, here are some software engineering (rather than coding) remarks.

  • Show us that you organized the code properly by factoring out what you actually are presenting: The "library" part, consisting of two files: The header and the implementation, unless you decide to keep all functions inline which seems defensible in this case.

    The code containing the test/usage demonstration should be in a separate file. This separation is relevant because neither the stack header nor the implementation would, for example, include <iostream>.

  • Use doxygen style comments to document your code. Good documentation focuses on the non-obvious. A function with a speaking name (e.g., pop()) does not need a general explanation. But you should document non-obvious parameters and return values, invariants, non-obvious side effects and generally any peculiarities. In short, establish context. E.g. leave information about where an (internal) function is used or called from.

    It is generally good practice to write at least a short description for every class.

  • For anything but a toy project I would also really appreciate a module test. Such a test is essential for a library like this stack which will be used by "third parties" (perhaps yourself in a different role). A comprehensive test takes on the role of a specification: As long as the users don't do anything that does not occur in the test, they can expect that a library upgrade does not introduce bugs into their software. If the test is comprehensive it will prevent most errors from reaching the users.

    For open source projects tests are typically deployed together with the source code, so users can run them after they built their version.

    Typically there is limited time or interest for writing tests, so it should focus on problems. The following questions can help to identify spots worth testing:

    • Which part did I find difficult to implement/where am I least confident?
    • Which part is the hardest to understand when I look at the code? (And: Should I rework that to be simpler?)
    • What are the border conditions (empty/any max element number)?
    • What are the failure modes: Your empty stack aborts with a null pointer exception upon pop(), wouldn't it be nice to throw a custom exception? What about an out-of-memory condition?
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is the first time I ever hear of doxygen - I think the claim it's the quasi-standard of documentation (on it's homepage) is wildly exaggerated, and I don't think it's that great a recommendation to give. \$\endgroup\$ – Aganju May 16 at 3:59
  • \$\begingroup\$ @Aganju It is surely mandatory to document your work in a professional environment, and the general idea to do so in the source code is surely superior to separate documents: It is closer to to the subject of documentation and hence less likely to be wrong, and it avoids creating a parallel tree of files which must be maintained. Doxygen has the added bonus to be machine readable so that it can be checked for miss-spelled or undocumented parameters etc. This is supported by IDEs like MS VS. What have you used in your professional projects instead? What would you recommend instead? \$\endgroup\$ – Peter - Reinstate Monica May 16 at 4:59
  • \$\begingroup\$ My point was not about the merits of doxygen, but about the claim of it being 'the quasi standard', which is at best wishful thinking. - i have used many different concepts, for 38 years, changing ever so often, and basically all homegrown. I think there simply is no accepted 'typical' way to document in the software world, just general concepts and ideas, and a million implementations of them. \$\endgroup\$ – Aganju May 16 at 5:25
  • \$\begingroup\$ @Aganju If you have 10 homegrown systems and one 3rd party solution that is used frequently in the field by multiple players, the 1 is the de-facto standard. The other ones are proprietary solutions. I'm astonished that you never came across doxygen in 38 years. What is (or was) your field of software expertise/occupation? (I have seen doxygen in automotive (infotainment) and transportation.) \$\endgroup\$ – Peter - Reinstate Monica May 16 at 5:39
0
\$\begingroup\$

Your linked-list implementation of a stack is well written in respect to you're being a learner.

Observations

.. from a foreign Software Developer's perspective (experienced in Java) that never coded in C++:

  • Stack could be implemented as class, instead of struct (benefit: information hiding)
  • pop() should return a value (e.g. char instead of a node or StackElement)
  • there's no method size() which returns the stack's size as int

See Robert Sedgwick's book Algorithms in C++, 3rd ed., where he writes about Stack Implementations. Beware it's from 1999 but includes following example C++ Stack class to derive some encapsulation advice (private VS public):

template <class Item>

class STACK {

  private:

    struct node {
      Item item;
      node * next;
      node(Item x, node * t) {
        item = x;
        next = t;
      }
    };

    typedef node * link;
    link head;

  public:

    STACK(int) {
      head = 0;
    }

    int empty() const {
      return head == 0;
    }

    void push(Item x) {
      head = new node(x, head);
    }

    Item pop() {
      Item v = head - > item;
      link t = head - > next;
      delete head;
      head = t;
      return v;
    }
};

Incompleteness Warning

Since I am a "native" Java developer, I can better judge on the or similar Java Implementation of a Stack using generics. Thus I will miss some points that other experienced C++ developers may answer for sure.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ The difference between struct and class is only default visibility of members \$\endgroup\$ – Caleth May 14 at 16:53
  • \$\begingroup\$ Why would pop() return a char value, instead of the actual item (node) that was popped from the stack? \$\endgroup\$ – Cody Gray May 14 at 21:22
  • 1
    \$\begingroup\$ You're leaking memory of the stack goes out of scope when not empty. \$\endgroup\$ – Emily L. May 14 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.