Very simple stack in C

Question

I'm starting to learn C and thought it would be a good idea to try and implement some data structures. I started with a very simple stack and would like to hear some opinions.

Stack.c

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
struct Node {
 int element;
 struct Node* next;
};
struct Node* head;
int size;
int stack_init() {
 struct Node* dummy = malloc(sizeof(struct Node));
 if(dummy == NULL) {
 return -1;
 }
 head = dummy;
 return 0;
}
int push(int value) {
 struct Node* tmp = malloc(sizeof(struct Node));
 if (tmp == NULL) {
 return -1;
 }
 tmp->element = value;
 tmp->next = head;
 head = tmp;
 size++;
 return 0;
}
int pop() {
 if(size == 0) {
 printf("Stack is empty\n");
 }else {
 printf("Element #%d ->value: %d has been removed\n", size, head->element);
 free(head);
 head = head->next;
 size--;
 }
 return 0;
}
void print_stack() {
 struct Node* tmp = head;
 printf("Stacksize: %d\n", size);
 for(int i = 0;i < size;i++) {
 printf("Element %d -> %d\n",i,tmp->element);
 tmp = tmp->next;
 }
 printf("#####################\n");
}
int get_size() {
 return size;
}

Stack.h

#ifndef STACK_H
#define STACK_H
int stack_init();
int push(int value);
int pop();
void print_stack();
#endif

• forsvarir: Your pop has a bug (you access head after you have freed it), which while it might work is as likely to crash with a different compiler.
• bw0248: Oh, you are right. How can I fix this? Maybe store the head in a temp variable first, then assign head = head.next and after that free the temp variable?
• Oskar Skog: One tiny little thing you could do is to write if (NULL == foo) instead of (foo == NULL). This way you will get compiler errors if you mistype == to =.
• ilkkachu: @OskarSkog or use a proper compiler that knows how to warn about usually mistakes like an assignment inside an if condition

Answer 1

I see a number of things that may help you improve your code.

Use a stack pointer as a parameter

Right now, one can only have one stack at a time. Worse, if one calls stack_init after some items have already been pushed onto the stack, there will be a memory leak. An alternative scheme would be to have stack_init() return a pointer to a Stack and then use that as a parameter for all other calls. That way, one could have multiple stacks simultaneously, making it that much more useful.

Initialize all values before use

In the stack_init routine, the head variable is initialized, but neither head->element nor head->next are initialized. It's also probably a good idea to explicitly zero the size. Although it's already zeroed at the moment because it's a file scope variable, if you follow the other advice on this list, you'll have to initialize it yourself.

Provide a way to free memory

Right now, the only way to free memory is to repeatedly call pop(). Unfortunately, the calling program has no way to know how many items are on the stack or to know when the stack is empty, so it's not going to be able to know how many times to do so. I'd suggest providing at least an explicit isEmpty() call.

Provide a complete interface

At the moment, there isn't any way to actually use the stack except to call print_stack() which limits its usefulness in the extreme. I'd suggest that adding a means of examining the top of the stack, as with a call to top() that returns the value for that item might be a good idea.

Don't access freed memory

These lines have a problem:

free(head);
head = head->next;

The problem is that after you've freed head, you dereference it to get the next pointer. This is undefined behavior -- anything could happen and it probably won't be good! Better would be to save a copy of the pointer, do your housekeeping and then free the copy like this:

struct Node* temp = head;
head = head->next;
free(temp);

Separate printing from data manipulation

There is no way at the moment to use pop without it printing something. In a real program that use such a stack, that's unlikely to be the desired effect. Better would be to have pop() just do what it needs to do and leave printing to the calling program.

Return something useful from functions

Most of your non-void functions return something useful, but pop always returns 0 which isn't very useful.

Encapsulate related data in a structure

The size and head elements are closely related items. For that reason (and to accomodate suggestion #1 on this list), I'd recommend combining them into a struct instead like this:

struct Stack {
 struct Node* head;
 int size;
};

Use a typedef to simplify your code

If you use a typedef like this:

typedef struct {
 struct Node* head;
 int size;
} Stack;

the code can refer to simply Stack instead of struct Stack. It's not necessary, but it does tend to make things a little easier to write and to read.

• bw0248: Wow this is amazing. Thank you so much for this detailed review. I think I understand and agree with all of your points. One thing that I don't totally get is the "provide a complete interface point". Why is there currently no way to use the stack? It is possible to call push() and pop(). I absolutely agree that there should be a top() function though. With "Provide a way to free memory" you basically mean some sort of a destroy_stack() function, right?
• Edward: @c_student: Yes, you've got most of it. As for a complete interface, consider that you might be writing an application that can't print like that (such as a GUI application or an embedded system). For such uses, the current interface is incomplete.
• underscore_d: This will become moot when, as advised, you make this properly 'object oriented' by passing pointers to stacks as parameters to all stack_*() functions - thereby making it an actual reusable thing, rather than a singleton, where the latter probably isn't what you really want. But more generally, in situations where you legitimately have variables to be shared by various functions within one compilation unit - like your original setup - then you should declare those variables as static. This signals intent, avoids potential symbol conflicts in non-trivial projects, and may aid optimisation.

Answer 2

From a memory management point of view, your implementation is a linked list, that is, all items are allocated separately, and the next item is found by following a pointer. As the theoretical advantages of linked lists lie in insertions and deletions from the middle, they don't make for a very good implementation of a stack, where you only really care about adding and removing from one end.

Especially here, when you're only storing a single number, the pointer to the next item is likely to be at least as large as the data stored, and that's not counting the space overhead of malloc. (Let alone the time spent on updating malloc's internal bookkeeping.)

I would suggest storing the values in a single array, and resizing it with realloc() as necessary. Something to the direction of this quick mock-up:

struct stack_head {
 int *data;
 unsigned allocated;
 unsigned used;
}
struct stack_head *stack_init(unsigned size)
{
 struct stack_head *sh = malloc(sizeof(stack_head));
 sh->data = calloc(size, sizeof(int));
 sh->used = 0;
 sh->allocated = size;
 return sh;
}
stack_push(struct stack_head *sh, int value)
{
 if (sh->used < sh->allocated) {
 /* just add to the end of sh->data[] */
 } else {
 /* need to realloc() the data area */
 }
}

• Edward: This answer raises an important point. Not only would this use less memory, it would also likely be much faster than the existing linked list.
• bw0248: Great points, but what I don't understand is why the theoretical advantages of linked lists are inserting and deleting in the middle? Isn't inserting and deleting at the head of a linked list O(1) whereas inserting and deleting in the middle would be O(n)?
• ilkkachu: @c_student, you can delete from the middle of a doubly-linked list in constant time, if you have a pointer to the item to be removed and don't need to search for it. Same for adding if you somehow know the position to add to. But in all cases you don't and searching through the list gets expensive because caches make linear access much faster than random access around dynamically allocated objects.