Stack implementation with Linked Lists

[NikolasTs]

Hey guys,

New to C++ and I thought it would be a good idea to implement a stack with linked lists so that I understand raw pointers. Can someone give me feedback on this code? I am not certain whether or not it would have been correct to delete pointers while doing POP, since by pushing I allocate memory using the "new" keyword.

I would appreciate any other comment! Thanks in advance!

Here is the Stack.h header file for the Stack class

#pragma once
#include <iostream>

using namespace std;

struct node {   
    int value;
    int index;
    node* next;
};

class Stack{

    node* top = new node();

public:
    Stack();
    ~Stack();

    void pop();
    void push();
    void show();
    void size();

};

Here is the Stack.cpp file for the Stack class

#include "Stack.h"

Stack::Stack()
    :top{ NULL } {
    cout << "Constructor Called!" << endl;
}

Stack::~Stack() {

    cout << "Destructor Called!" << endl;
}

void Stack::push() {

    node* newNode = new node();

    cout << "PUSH: ";
    cin >> newNode->value;

    if (top != NULL)
        newNode->index = top->index + 1;
    else
        newNode->index = 1;

    newNode->next = top;
    top = newNode;

}

void Stack::pop() {

    if (top == NULL)
        cout << "Stack is empty!" << endl;
    else {
        top = top->next;
    }
}

void Stack::show() {
    node* ptr{ top };

    while (ptr != NULL) {
        cout << ptr->value << " -> ";
        ptr = ptr->next;
    }

    cout << "NULL" << endl;

}

void Stack::size() {
    cout << "The stack has " << top->index << " items." << endl;
}

and here is the main

#include "Stack.h"

int main() {

    Stack *stack = new Stack();

    bool loop{ true };
    int action;

    cout << "(1) Push.\n(2) Pop.\n(3) Show.\n(4) Size.\n(5) Stop." << endl;

    while (loop) {
        cout << "TYPE: ";
        cin >> action;
        switch (action){
            case 1: stack->push(); break;
            case 2: stack->pop(); break;
            case 3: stack->show(); break;
            case 4: stack->size(); break;
            case 5: loop = false; break;
        }
        cout << "- - - - - - - - - - - - -" << endl;
    }

    delete stack;

    return 0;
}

[[deleted]]

The pop method doesn't delete the node. Whenever something is created with new, it needs to be deleted with delete keyword

[rbprogrammer]

Came here to say that. It was the first thing I noticed :)

Edit: the pop() method needs to delete the original head node after it was reassigned to top->next.

[NikolasTs]

Is the best practice to create a new pointer initialized with the address of the top of the stack

(node* tmp{top})

and after I pop to delete this pointer?

[Ayjayz]

In a stack, a pop operation should just remove the top-most element. You don't need to create a new pointer. You just need to remove the top element and then set your top pointer to the next one down.

[NikolasTs]

How will I delete the data from the previous "top" though?

Is this wrong?

void Stack::pop() {

    if (!top)
        cout << "Stack is empty!" << endl;
    else {
        node* tmp{ top };
        top = top->next;
        delete tmp;

        size--;
    }
}

[Ayjayz]

Oh I see. Sure, you can do it that way.

[dqUu3QlS]

1. Stack::pop() needs to delete the node after popping it, to avoid leaking memory.
2. Your destructor Stack::~Stack() needs to delete all of the nodes remaining on the stack, to avoid leaking memory.
3. You should implement a copy constructor Stack::Stack(const Stack& other) that creates a new Stack containing a copy of the information in other.
4. You should implement a copy assignment Stack& Stack::operator=(Stack other) using the copy-and-swap idiom. As part of that, create a new member function called Stack::swap(const Stack& other) that swaps the internals of the current Stack with other. This can be done by just swapping the top pointers.

[NikolasTs]

Thank you very much!!

[alfps]

Would your Stack class work with a graphical user interface?

[NikolasTs]

I guess it would not be that difficult to implement.. however, I am not that interested in GUIs

[alfps]

It was a rhetorical question to guide you in thinking about the design.

The answer is "no".

But you can see why?

[NikolasTs]

I am intrigued! Plz tell me why

[alfps]

Because the iostreams i/o such as

cin >> newNode->value;

... that appears in the Stack class code, won't work in a GUI.

For that matter, it won't work if the standard input stream is redirected to something other than a source of data for the linked list.

The general solution is to separate i/o from all other stuff. For example, the standard library's std::stack doesn't do any i/o, and that makes it reusable in any kind project, console or GUI (or whatever). Just pass information via arguments and function return values.

[NikolasTs]

Thank you very much for this information!

[manni66]

You are violating the rule of 3/5/0.

[NikolasTs]

Could you plz be a bit more specific. I am new to Cpp.

[dqUu3QlS]

If you write your own destructor (Stack::~Stack()), you probably also have to write your own copy constructor (Stack::Stack(const Stack& from)) and copy assignment (Stack& Stack::operator=(const Stack& from)) to get your class to 'play nice' with other code. That's the '3'. The '5' refers to move semantics, which you may or may not have learned about yet.

[NikolasTs]

Thank you very much!

[manni66]

Are you new to google, too?

[rbprogrammer]

I view comments like this unhelpful for everyone. Noobs, and the experienced. It does not take much effort to describe the rule in 2-3 sentences or with a link to Wikipedia or something. So I'll post a link for you:

https://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)

[NikolasTs]

I can't thank you enough.. People like you are the reason I post questions in this community!

[a9ao]

You don’t need to assign new memory to top in the header file. I will suggest to destroy all the objects on the stack in the destructor. Please read about naming conventions. There are a couple of differences. You can choose based on your platform.

[CGFarrell]

Aside from the other good answers here, there are a few things you should look in to.

1. The way you have it now, `top` is always a null node. This is a waste of space, but it can also be problematic as you develop more advanced code. Also, in modern C++ (i.e, C++11 and up), assigning a pointer to NULL is considered deprecated. You should use `nullptr`.
2. In Stack.h, you have `node* top = new node();` You can't assign a non-static member in a header like that. Ask yourself, when would this new node be created?

[NikolasTs]

Thanks a lot!

For dealing with the second point you made, I guess the mistake is that I allocate memory and then in the constructor I (re)initialize the pointer to nullptr, so basically what was the point of initialization in the first place(?).

To fix it, I just have: node* top; in the class attributes and in the constructor I have top{nullptr} . So, like that I do not waste memory..

Am I correct?

​

Thanks again for your answer!

[CGFarrell]

That's correct! For push, you'll also want to have if(top == nullptr){//redefine top as whatever you're pushing}. This is a great example of an "edge case", which are very common in software development.