Hi everyone,

I have the implementation for a linked-list based Stack. I believe the entire code is correct, but only the way I call the push and pop function mighe be wrong. Any idea how they should be called? Mine returns garbage:

#include <iostream>

using namespace std;

typedef struct Elements {
    struct Elements *next;
    void *data;
} Elements;

bool push(Elements **Stack, void **data);
bool pop(Elements **Stack, void **data);
bool createStack(Elements **stack);
bool deleteStack(Elements **Stack);


int main()
{
    Elements **myStack;
    if (!createStack(myStack))
        cout << "Something happend!" << endl;
    cout << "Stack created." << endl;

    int i = 10, j = 20, k;
    if (push(myStack, (void**)&i))
        cout << "Data added successfully!" << endl;
    if (push(myStack, (void**)&j))
        cout << "Data added successfully!" << endl;

    if (pop(myStack, (void**)&k))
        cout << "Data returned: " << k << endl;

}

bool createStack(Elements **Stack)
{
    *Stack = NULL;
    return true;
}

bool deleteStack(Elements **Stack)
{
    Elements *next;
    while (*Stack)
    {
        next = (*Stack) -> next;
        delete *Stack;
        *Stack = next;
    }
    return true;
}

bool push(Elements **Stack, void **data)
{
    Elements *elem = new Elements;
    if (!elem)
        return false;
    elem -> data = data;
    elem -> next = *Stack;
    *Stack = elem;
    return true;
}


bool pop(Elements **Stack, void **data)
{
    Elements *elem;
    if (!(elem = *Stack))
        return false;
    *data = elem -> data;
    *Stack = elem -> next;
    delete elem;
    return true;
}

Thank you.

there should be only one star for data in function parameters, like this
bool push(Elements **Stack, void *data);

Two stars means pointer to pointer, which is not what you want

bool push(Elements **Stack, void *data)
{
    Elements *elem = new Elements;
    if (!elem)
        return false;
    elem -> data = data;
    elem -> next = *Stack;
    *Stack = elem;
    return true;
}

Now you call the above like this:

char* somedata = "Something";
Elements* head = 0;
push(&head,somedata);

I believe the entire code is correct, but only the way I call the push and pop function mighe be wrong.

Actually, a lot of the code is incorrect, but subtly so. The way you're using void* isn't quite right (note that void** doesn't do what you probably think it does), and when popping a generic item, you essentially can't use assignment. You'll need to copy the bytes in a generic manner:

bool pop(Elements **Stack, void *data, size_t size)
{
    Elements *elem;
    if (!(elem = *Stack))
        return false;
    memcpy((unsigned char*)data, elem->data, size);
    *Stack = elem -> next;
    delete elem;
    return true;
}

However, this opens up potential issues because you're assuming that the type of the stored data can be safely punned into a sequence of bytes. That's not necessarily true, and it's even less true in C++ when you start to use complex classes.

Finally, you have aliasing problems. For example, if the value of j changes then the value stored in the stack will change. If j goes out of scope, the stack will have a dangling pointer. You should probably store the value on the stack and not a pointer to the value. That way the stack owns what it stores. This can be done in a similar manner as copying the bytes for the pop operation.

Ignoring the punning problem, you can make things work like this:

#include <iostream>
#include <cstring>

using namespace std;

typedef struct Elements {
    struct Elements *next;
    void *data;
} Elements;

bool push(Elements **Stack, void *data, size_t size);
bool pop(Elements **Stack, void *data, size_t size);
bool createStack(Elements **stack);
bool deleteStack(Elements **Stack);

int main()
{
    Elements *myStack;

    if (!createStack(&myStack))
        cout << "Something happend!" << endl;

    cout << "Stack created." << endl;

    int i = 10, j = 20, k;

    if (push(&myStack, &i, sizeof i))
        cout << "Data added successfully!" << endl;

    if (push(&myStack, &j, sizeof j))
        cout << "Data added successfully!" << endl;

    if (pop(&myStack, &k, sizeof k))
        cout << "Data returned: " << k << endl;

    deleteStack(&myStack);
}

bool createStack(Elements **Stack)
{
    *Stack = NULL;
    return true;
}

bool deleteStack(Elements **Stack)
{
    Elements *next;
    while (*Stack)
    {
        next = (*Stack) -> next;
        delete[] (*Stack) -> data;
        delete *Stack;
        *Stack = next;
    }
    return true;
}

bool push(Elements **Stack, void *data, size_t size)
{
    Elements *elem = new Elements;
    if (!elem)
        return false;
    elem -> data = new unsigned char[size];
    memcpy(elem -> data, data, size);
    elem -> next = *Stack;
    *Stack = elem;
    return true;
}

bool pop(Elements **Stack, void *data, size_t size)
{
    Elements *elem;
    if (!(elem = *Stack))
        return false;
    memcpy((unsigned char*)data, elem->data, size);
    *Stack = elem -> next;
    delete[] elem -> data;
    delete elem;
    return true;
}

But this method is very much not recommended in C++. It's okay for C, but there are too many gotchas in C++'s class structure for this design to be truly useful. A template class would be much safer.

This article has been dead for over six months. Start a new discussion instead.