Another stack implementation (in C)

Question

I just started learning C and the online book contained the exercise 'implement a stack'. So I did, but thought I'd put it here, because I still don't feel comfortable with pointers.

So here it is:

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

struct StackItem {
    struct StackItem *previous;
    int value;
};

void stack_push(struct StackItem **current, int value) {
    struct StackItem *tmp = malloc(sizeof(struct StackItem));
    tmp->previous = *current;
    tmp->value = value;
    *current = tmp;
}

void stack_pop(struct StackItem **current) {
    if ((*current)->previous != NULL) {
        struct StackItem *tmp = (*current)->previous;
        free(*current);
        *current = tmp;
    } else printf("%s\n", "Previous is NULL");
}

void stack_print(struct StackItem *current) {
    printf("%d\n", current->value);
    while (current->previous != NULL) {
        current = current->previous;
        printf("%d\n", current->value);
    }
}

int main(int argc, char **argv) {
    struct StackItem *current = malloc(sizeof(struct StackItem));
    current->value = 2147483647;
    current->previous = NULL;
    char input[10];
    int i = 0;
    while (i < 10) {
        puts("Enter integer value to add to the stack:");
        gets(input);
        char *end;
        int newVal = (int)strtol(input, &end, 10);
        if (*end != '\0') { puts("That was no integer value."); --i; }
        else stack_push(&current, newVal);
        ++i;
    }

    stack_print(current);
    puts("Stack printed once.");

    i = 0;
    while (i < 10) {
        stack_pop(&current);
        i++;
    }

    stack_print(current);
    puts("Stack printed twice.");

    return 0;
}

Is there anything wrong/not good (I mean two different things here) with this?

Answer 1

It's good overall, but I do have a few suggestions.

(Looks like William Morris beat me to a few of these, but there's a few different ones too :p.)

---

Rather than using the top node as the container, I'd be tempted to make a Stack that then contains StackItem.

struct Stack
{
    StackItem* top;
    size_t size; /* example of meta-data */
};

This would allow passing around a structure and letting functions modify it rather than passing an item by double reference and having the function modify your pointer.

Also, you get the added bonus of stack-related meta data. For example, suppose you wanted to generalize this stack. You would need to store data about how big each element is. With this structure, that's simple. You just throw in another field (and of course put handling for it in the initialization and whatnot). In the StackItem** version, you're suddenly stuck repeating that information in every instance of StackItem.

Oh, this also means your sentinel node is no longer required, which can be kind of nice (though it can also complicate some algorithms).

---

Your methods should return error codes. What if malloc fails in stack_push? What if (*current)->previous is NULL in stack_pop?

Printing errors in non-user interaction code tends to be bad. Printing communicates with the user, not the code. Your code has no idea stack_pop failed, only your user does. If you pass an error message to the calling code, that code can then choose what to do. It might silently ignore the error, it might alert the user, or it might decide to have a forced freak out. Who knows. The point though is that the calling code needs to be able to decide for itself what to do. Sometimes just alerting the user isn't sufficient.

---

Other than fully printing or manually handling the struct traversal, how do you get the top element of the stack? Either stack_pop should handle this, or there should be a stack_top.

(int stack_pop(struct StackItem* current, int* popped); for example.)

---

There's a some problems with your IO in main.

First, an int can be 10 characters. This means your input buffer needs to be 11 characters (10 + '\0').

More importantly though, gets should be avoided. What if instead of a wellformed int or a string <= 10 characters, I decide to put in aaaaaaaaaaaaaa. Best case, a segfault just happened. Worst case, the stack frame just got modified in a very odd (and potentially insecure) way. (On modern operating systems, the segfault option is almost certainly going to happen, but this should still be avoided at all costs.)

Anyway, I would replace gets with fgets. That way you get the safety of specifying buffer size.

---

It's way overkill in this situation, but if you decide to go the library-esque route, I would encapsulate your data in a way that the calling code never has to know what's in the struct behind the scene. (This is called an opaque data type). This way your calling code just has to know how to use the exposed API, not the nitty-gritty details.

This explains it pretty well.

All in all, if you decide to go the opaque route, I would have an API similar to:

int stack_init(Stack* s);
int stack_destroy(Stack* s);
int stack_push(Stack* s, int val);
int stack_pop(Stack* s, int* val);
size_t stack_size(void); /* so you can alloc Stacks -- Stack* s = malloc(stack_size()); */
int stack_top(const Stack* s, int* val); /* optional */

Answer 2

Your code looks nice and compiles cleanly - good signs. Some comments, nevertheless:

• all functions except main should be declared static

• the opening brace { for a function should be in column 0

• stack_print should take a const parameter, as you are not modifying the stack:

   void stack_print(const struct StackItem *current)
  

• the stack variable name current would be better as (for example) stack

• you define the stack current by allocating a StackItem but never use this item. It would be better to define the stack using just a pointer:

   struct StackItem *current = NULL;
  

  this involves some changes to other functions because the 'empty stack' condition is no longer (*current)->previous == NULL but simply *current == NULL. This affects stack_pop and stack_print. The latter becomes:

  void stack_print(const struct StackItem *current)
  {
      while (current != NULL) {
          printf("%d\n", current->value);
          current = current->previous;
      }
  }
  

• for-loops are often better than while loops - eg when you are counting through a range. And the loop variable is best declared in the loop where possible:

  for (int i = 0; i < 10; ++i) {
      stack_pop(&current);
  }
  

• using constants in the code like 10 is often a bad idea. Some are fine (eg the 10 in the strtol call, but the loops would be better having a #defined limit

  #define N_VALUES  10
  
  for (int i = 0; i < N_VALUES; ++i) {...}
  

  Such #defines go at the top of the file after the #includes

• gets is not safe and should not be used. Using gets with a buffer of 10 bytes, if the user types in more than 10 characters the buffer overflows and overwrites the call stack (not your stack but the process stack). Use fgets instead:

  fgets(input, (int) sizeof input, stdin);
  

• there is no error handling, but that is ok for an exercise. In a real program, you would want to check that malloc does not fail (using perror to print an error message if it does - an then you have to decide what to do about the failure) and you might want to return success or failure from the push/pop functions.