Why do I need to use & to pass a pointer to a struct in this stack implementation

Question

In the following program I need to pass an argument to a function using the &-operator although I expect it to be a pointer and the function is expecting a pointer. Why do I need to do this?

The program implements a simple stack using linked lists and incomplete types in C. Here are the three necessary files:

stack.h

#ifndef STACK_H
#define STACK_H

#include <stdbool.h>

struct Stack {
        int number;
        struct Stack *next;
};

/*
 * We declare a pointer to a Stack structure thereby making use of incomplete
 * types. Clients that pull in stack.h will be able to declare variables of type
 * pstack which are pointers to Stack structures. */
typedef struct Stack *pstack;

bool is_empty(pstack *s);
void make_empty(pstack *s);
void push(pstack *s, int new_num);
int pop(pstack *s);

#endif /* STACK_H */

stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

bool is_empty(pstack *s)
{
        return !s;
}

void make_empty(pstack *s)
{
        if (!is_empty(s))
                pop(s);
}

int pop(pstack *s)
{
        struct Stack *tmp;
        int i;

        if (is_empty(s)) {
                exit(EXIT_FAILURE);
        }
        tmp = *s;
        i = (*s)->number;
        *s = (*s)->next;
        free(tmp);
        return i;
}

void push(pstack *s, int new_num)
{
        struct Stack *new_node = malloc(sizeof(struct Stack));
        if (!new_node) {
                exit(EXIT_FAILURE);
        }
        new_node->number = new_num;
        new_node->next = *s;
        *s = new_node;
}

stackclient.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

int main(void)
{
  pstack s1;
  int n;

  push(&s1, 1);
  push(&s1, 2);

  n = pop(&s1);
  printf("Popped %d from s1\n", n);
  n = pop(&s1);
  printf("Popped %d from s1\n", n);

  exit(EXIT_SUCCESS);
}

Again, I thought that by using

typedef struct Stack *pstack;

and later on in main()

pstack s1;

I'm declaring a pointer to the linked list Stack and hence it would be fine to simply pass s1 to say push() by just using

push(s1, 1);

but I actually need to use

push (&s1, 1);

Why?

That's because you need to update the content of `s` and keep a `new_node` to it with `*s = new_node` in the `push` function implementation, so you need `push(&s1,1);` rather than `push(s1,1)` — Eric Tsui, Jul 09 '15 at 00:49
I did not do it. Actually I'd like to up vote this question. Because It is a classic question for implementing a linked node ----To use a s->next to link the new_node, or return new_node by *s. So, I just provided my answer below to try to give some tips. — Eric Tsui, Jul 09 '15 at 07:03

MooseBoys · Accepted Answer · 2015-07-09T00:40:35.117

4

Your functions are all declared to take pstack* as an argument, which is actually a pointer to a pointer to a Stack struct. Just use pstack. You'll also need to replace the instances of (*s) with just s in the implementations of those functions.

Edit: As was pointed out in the comments, you actually write to (*s) in the function implementations and rely on this behavior for correctness, so you need to keep the argument as pstack*. Conceptually, this is because the stack variable (s1) is literally the top of the stack itself, and so must be modified by push and pop.

edited Jul 09 '15 at 00:40

answered Jul 08 '15 at 23:55

MooseBoys

6,641
1
19
43

Consider that the `push` function needs to modify `s1` in `main`. – user3386109 Jul 09 '15 at 00:05
Thanks, meanwhile I figured it out myself. Could you expand on the pointer to pointer explanation a little more as this is the crux of the matter. It will be clearer when you consider that I could also declare the functions with `struct Stack **s`. E.g. `void push(struct Stack **s, int new_num)`. – lord.garbage Jul 09 '15 at 00:09

Eric Tsui · Answer 2 · 2015-07-09T05:45:09.767

You need to use pstack *s ( pointer to pstack ) in void push(pstack *s, int new_num), according to your implementation code, if to use pstack s( pstack ), the new_node will not be returned correctly.

Two possible ways to insert a Node in push():

if insert to head, it should be *s = new_node
if insert to tail, it could be s->next = new_node

Back to the code, if to use push(s1, 1); such as,

 //If only use pstack s, the new_node can not be pushed.
 void push(pstack s, int new_num) //it is a wrong implementation for demo
 {
        struct Stack *new_node = malloc(sizeof(struct Stack));
        if (!new_node) {
                exit(EXIT_FAILURE);
        }
        new_node->number = new_num;
        new_node->next = s;
        s = new_node;// WRONG! here, the new_node cannot be kept by s
                     // two typical node insert ways:
                     // 1)if insert to head, it should be *s = new_node
                     // 2)if insert to tail, it could be s->next = new_node
                     //Now, Your code applied the #1 way, so need *s 
 }

So, it should be inputed pstack *s, and call with push (&s1, 1);

 void push(pstack *s, int new_num)//it is the correct version the same as your post
 {
        struct Stack *new_node = malloc(sizeof(struct Stack));
        if (!new_node) {
                exit(EXIT_FAILURE);
        }
        new_node->number = new_num;
        new_node->next = *s;
        *s = new_node;//here, the new_node could be kept by *s
 }

Why do I need to use & to pass a pointer to a struct in this stack implementation

2 Answers2