typedef struct elt Stack; why is there a here

Question

This is the full code of an implementation of Stack using Linked Lists. It's from Data Structures notes for Yale University by James Aspnes(is it any good?)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct elt {
    struct elt *next;
    int value;
};

/* 
 * We could make a struct for this,
 * but it would have only one component,
 * so this is quicker.
 */
typedef struct elt *Stack;

#define STACK_EMPTY (0)

/* push a new value onto top of stack */
void
stackPush(Stack *s, int value)
{
    struct elt *e;

    e = malloc(sizeof(struct elt));
    assert(e);

    e->value = value;
    e->next = *s;
    *s = e;
}

int
stackEmpty(const Stack *s)
{
    return (*s == 0);
}

int
stackPop(Stack *s)
{
    int ret;
    struct elt *e;

    assert(!stackEmpty(s));

    ret = (*s)->value;

    /* patch out first element */
    e = *s;
    *s = e->next;

    free(e);

    return ret;
}

/* print contents of stack on a single line */
void
stackPrint(const Stack *s)
{
    struct elt *e;

    for(e = *s; e != 0; e = e->next) {
        printf("%d ", e->value);
    }

    putchar('\n');
}

int
main(int argc, char **argv)
{
    int i;
    Stack s;

    s = STACK_EMPTY;

    for(i = 0; i < 5; i++) {
        printf("push %d\n", i);
        stackPush(&s, i);
        stackPrint(&s);
    }

    while(!stackEmpty(&s)) {
        printf("pop gets %d\n", stackPop(&s));
        stackPrint(&s);
    }

    return 0;
}

I can understand most of the code. But I can't wrap my head around this part typedef struct elt *Stack;

Why is there a * before Stack and what does it mean?

I'm finding a concepts of pointers, especially in return types of functions hard to grasp. Thanks in advance.

This is not a tutoring site. The concept of pointers is pretty broad and should be studied using dedicated resources. — Eugene Sh., Jun 30 '16 at 17:18
This is `C` code, not C++. This line: `e = malloc(sizeof(struct elt));` would not compile as C++. — PaulMcKenzie, Jun 30 '16 at 17:18
@PaulMcKenzie: What in the code prevents the code from being compiled as C++? — Thomas Matthews, Jun 30 '16 at 17:19
@ThomasMatthews The return value of `malloc` not being casted. A cast is required for C++. — PaulMcKenzie, Jun 30 '16 at 17:20
@PaulMcKenzie I know it's C. I tagged both since both are similar. My bad. — user3600999, Jun 30 '16 at 17:41

score 5 · Accepted Answer · edited May 23 '17 at 10:29

5

I can understand most of the code. But I can't wrap my head around this part typedef struct elt *Stack;

That is using typedef*. That just means when you write

Stack x;

in your code it means:

struct elt * x;

If you however use

Stack *s;

in your code it will mean:

struct elt ** s;

I'm finding a concepts of pointers, especially in return types of functions hard to grasp. Thanks in advance.

Then I recommend you first understand pointers and pointers to pointers well before proceeding with that code.

*_{I think there are some subtle differences with typedefs in C and C++: see here}

edited May 23 '17 at 10:29

Community

1
1

answered Jun 30 '16 at 17:17

Giorgi Moniava

27,046
9
53
90

Thanks man. Can you tell me if there's a difference between int *foo & int *(foo)? – user3600999 Jun 30 '16 at 17:27
@user3600999 Is foo a variable there? No there should be not: https://ideone.com/mgjfPW – Giorgi Moniava Jun 30 '16 at 17:29
No. A function. Sorry, I wasn't clear on that. BTW, why does he use a `struct elt *e;` instead of just `Stack e` inside StackPush and other functions – user3600999 Jun 30 '16 at 17:34
@user3600999 He just uses for comfort to type less ** stars. you need to show full code snippet of those function definitions – Giorgi Moniava Jun 30 '16 at 17:37

score 1 · Answer 2 · answered Jun 30 '16 at 18:32

I'm finding a concepts of pointers, especially in return types of functions hard to grasp. Thanks in advance.

That's a bit more than can be covered here; find yourself a good tutorial (if such a thing exists) and work from there. However, here are some things to remember:

In a pointer declaration, the * operator is always bound to the declarator, not the type specifier. For example, the declaration
```
int* x, y, z;
```
is parsed as
```
int (*x), y, z;
```
IOW, only x is declared as a pointer. If you want to declare y and z as pointers as well, you would have to write
```
int *x, *y, *z;
```

The unary * and & operators have lower precedence than postfix operators like [], (), and member selection operators, so:

T *x[N];   // declares x as an N-element array of pointers to T
T (*x)[N]; // declares x as a pointer to an N-element array of T
T *f();    // declares f as a function returning pointer to T
T (*f)();  // declares f as a pointer to a function returning T

*a.b  == *(a.b)    // dereferences a.b
*a->b == *(a->b)   // dereferences a->b
&a.b  == &(a.b)    // takes the address of a.b
&a->b == &(a->b)   // takes the address of a->b
a->b  == (*a).b    // dereferences a, then accesses b

There is no single pointer type; instead, there are many different pointer types, and most are not compatible with each other; if a function is expecting an argument of type int *, it will complain if you pass it something of type int ** (or int (*)[N], or int **, or float *, etc.) The void * type is a "generic" pointer type, but you cannot work with it directly (you can't dereference a void *, nor can you do pointer arithmetic on it). In C, you can assign void * values to any pointer object and vice versa without a cast; C++ requires a cast for all pointer type conversions.
ARRAYS ARE NOT POINTERS. The array subscript operation is defined in terms of pointer arithmetic:
```
a[i] == *(a + i);
```
We offset i elements (not bytes) from the address a and dereference the result. But, if arrays are not pointers, how does this work? Unless it is the operand of the sizeof or unary & operators, or is a string literal being used to initialize another array in a declaration, an expression of type "N-element array of T" will be converted ("decay") to an expression of type "pointer to T" and the value of the expression will be the address of the first element of the array. Thus, when we write a[i], the array expression a is converted to a pointer type, and we offset from that pointer. Note that the object a is not converted; it is always an array object.

typedef struct elt *Stack; why is there a * here

2 Answers2

typedef struct elt Stack; why is there a here