Is it possible to implement stack with only pointer to structure (no data type)?

Question

Suppose I have the following structure

typedef struct _Stack {
   struct _Stack *next;
} Stack;

Note in above there is no data type for storage, only *next pointer to structure. So, my question is will it be possible that the following function is valid.

void stackPush(Stack **stackP, void *dataP) {
    Stack *data = (Stack*)dataP;

    data->next = *stackP;
    *stackP = data;
}

I saw this function in glib library in the file gtrashstack.c. But when I compiled above, I got a warning : In data->next : assignment from incompatible pointer type.

I know that, I can rewrite the structure with generic pointer. But I only want to know, why the above will not work?

Update: My mistake, here I write typedef struct _Stack but in my program, I missed _Stack.

Your question is based on a false premise. It's valid and it will work. Though data->next = *stackP should probably be written data->next = &(stackP->next); or data->next = (struct _Stack *) *stackP;. — David Schwartz
– David Schwartz, Commented Jan 16, 2014 at 6:02
Because data->next is of type struct _Stack *, not Stack *. — David Schwartz
– David Schwartz, Commented Jan 16, 2014 at 6:09
@David data->next = (Stack*)*stackP` also work. It's my mistake, I forget to add _Stack in typedef struct in my original program — Ashish Rawat
– Ashish Rawat, Commented Jan 16, 2014 at 6:13

Marian · Accepted Answer · 2014-01-16 06:59:00Z

2

This function is valid. Probably it is used for different structures like:

 typedef struct my_Stack {
   struct my_Stack *next;
   sometype1 somename1;
   ...
   sometypen somenamen;
 } MyStack;

i.e. for the lists where the pointer to the next elem is placed as the first field of the structure. It is the same trick as when classes are built via simple inheritance in C++. For such a structure you can call:

x = malloc(sizeof(struct my_Stack));
x->somename1 = aaa; ...
stackPush(&mylist, x);

I am not sure if this style of programming is supported by the C standard. It's not a good style for novices. It is for developers who know what they are doing in C.

edited Jan 16, 2014 at 6:59

answered Jan 16, 2014 at 6:12

Marian

7,4922 gold badges24 silver badges36 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Ashish Rawat Over a year ago

So it means, we can also implement linked list with only pointer to structure and no data type.

Marian Over a year ago

It is the same thing.

Apiwat Chantawibul Over a year ago

it's better said that it's just a trick. the data IS there right next to the next pointer. But in the context of stackPush it didn't need to care how big the data was. so it just received *dataP as void pointer; interpret it as having a 'next' pointer at that address (not caring that there might also be data in the following address); then just do stackPush

Apiwat Chantawibul Over a year ago

So it's just a way to implement stackPush for any type of linked-list node, independent of what the data type is. as long as the linked-list node declare next pointer as the first variable in the struct.

moeCake Over a year ago

@ashish2expert Check keyword: Intrusive list, there is an implemention in kernel.

Dabo · Accepted Answer · 2014-01-16 06:39:13Z

1

The answer is yes, it is possible to implement stack with only pointer to structure (no data type). See implementation of generic list or queue in c in Linux (don't know if it is implemented in windows also). See how it is implemented Linux Kernel Linked List Explained

answered Jan 16, 2014 at 6:39

Dabo

2,3832 gold badges21 silver badges30 bronze badges

2 Comments

Ashish Rawat Over a year ago

Thanks for the answer, I really want this

Dabo Over a year ago

@ashish2expert Pay attention to the list_entry macro which returns pointer to the actual data struct given absolute memory address of inner filed list( this will be stack in your case)

Collectives™ on Stack Overflow

Is it possible to implement stack with only pointer to structure (no data type)?

2 Answers 2

5 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related