Stack using linked list in C

 A stack data structure is used on cases where the last-in-first-out (LIFO) is needed. For example, Undo is implemented using stack, ie., the most recently made change is undone first. The article explains a sample implementation of the stack using linked list in C.

Environment

• Operating System - Windows 11
• MSYS2 MinGW - MinGW version MINGW64_NT-10.0-22000
• Compiler - GCC 10.2.0

The implementation in the article uses a linked list, and the first structure used for the code is the entry structure, which holds the data, in this case a single integer variable, and a pointer to the same structure. The integer value can be replaced by a void pointer for a more generic implementation of the stack, but in this article an integer data is used throughout. The second structure is the stack itself, which has a pointer to an entry structure, instead of the structure a single pointer could also be used, but a structure is chosen for better clarity and encapsulation. The two structures are defined as follows,

typedef struct entry {
    int data;
    struct entry *next;
} entry;

typedef struct stack {
    entry *top;
} stack;

Then comes the a list of operations that can be performed on the stack,

• add a value to the top of stack, also known as push operation
• remove the value from the top of stack, also known as pop operation
• get the value at the top of the stack (without removal), also known as peek operation
• check if the stack is empty
• initialize a new stack
• print all elements in the stack

Initializing the stack

The stack has only one pointer called top, assigning the pointer to NULL is the only operation done as part of stack initialization. Initializing the stack is a required step,  otherwise the poniter will have garabage value and de-referencing the poniter will cause segmentation fault at runtime.

void init_stack(stack *s)
{
    s->top = NULL;
}

Checking empty stack

The initial state of the stack is known now, so checking for an empty stack is just checking whether the top pointer is NULL. The function returns a 0 or 1 (can be interpreted to false and true respectively) by the callers.

int empty(stack *s)
{
    return s->top == NULL;
}

Add a value to stack

Adding a new value is little complicated, since linked list is being used. For every new entry, the correspoding memory has to be allocated, and failures during memory allocation also needs to be handled. Once memory is sucessfully allocated, the input data is added to the structure and it will be linked to the existing list pointed by top. Once linked, the new entry will act as the new top as stack follows LIFO model.

int push(stack *s, int data)
{
    entry *e = malloc(sizeof(*e));
    if (e == NULL) {
        fprintf(stderr, "Unable to allocate memory.");
        return -1;
    }
    e->data = data;
    e->next = s->top;
    s->top = e;
    return 0;
}

Get the value at top of stack

While getting the value at the top is rather simple, the stack needs to be checked whether it is empty. So, the function checks for an empty stack before returning the value at top of the stack.

int peek(stack *s, int *data)
{
    if (empty(s)) {
        return -1;
    }
    *data = s->top->data;
    return 0;
}

Remove entry from the top of stack

Again, an entry can not removed from an empty stack. So, the first check during removal is to check for an empty stack. If not empty, the current top is referenced using a variable and will be set to the next element in the list. The data from the old top is returned, and the memory for the entry at old top is freed.

int pop(stack *s, int *data)
{
    entry *temp;

    if (empty(s)) {
        return -1;
    }
    temp = s->top;
    *data = temp->data;
    s->top = temp->next;
    free(temp);
    return 0;
}

Printing the elements in the stack

For printing the elements, start from the top print the data if available, and move to the next. Since the top should not be adjusted for printing, a temporary pointer is used to traverse the list.

void dump_stack(stack *s)
{
    entry *e = s->top;
    while (e != NULL) {
        printf("%d -> ", e->data);
        e = e->next;
    }
    printf("\n");
}

Cleaning up the stack

While the operating system cleans up any allocated memory by an application that exited, it is a good practice to clean up all the allocated memory for the program before exiting. So to achieve this, the entries are popped one by one till the stack is empty as a cleanup procedure.

void cleanup_stack(stack *s)
{
    int data;
    while (!empty(s)) {
        pop(s, &data);
    }
}

Unit testing

The code is testing using a set of tests which covers most of the code and branches. The various test methods that were used are,

• Push test - push a value to stack, peek and check if the value is same
• Empty stack test - test if stack is empty
• Empty stack pop test - failure branch case, expected to return error during pop
• Pop test - pop a value, and verify it to be the same as expected data
• Stack cleanup test - cleanup stack and verify it is empty

void push_entry_test(stack *s, int in_data)
{
    int ret;
    int out_data;

    printf("Push entry (%d) in stack test - ", in_data);
    ret = push(s, in_data);
    assert(ret == 0);
    ret = peek(s, &out_data);
    assert(ret == 0);
    assert(out_data == in_data);
    printf("[PASS]\n");
}

void empty_stack_test(stack *s)
{
    int ret = empty(s);
    assert(ret == 1);
}

void empty_stack_pop_test(stack *s)
{
    int ret;
    int data;

    empty_stack_test(s);

    printf("Pop empty stack test - ");
    ret = pop(s, &data);
    assert(ret == -1);
    printf("[PASS]\n");
}

void pop_entry_test(stack *s, int verify_data)
{
    int ret;
    int data;

    printf("Pop entry (%d) in stack test - ", verify_data);
    ret = pop(s, &data);
    assert(ret == 0);
    assert(data == verify_data);
    printf("[PASS]\n");
}

void stack_cleanup_test(stack *s)
{
    printf("Stack cleanup test - ");
    cleanup_stack(s);
    empty_stack_test(s);
    printf("[PASS]\n");
}

void run_unit_tests()
{
    stack s;

    init_stack(&s);

    empty_stack_pop_test(&s);
    push_entry_test(&s, 5);
    pop_entry_test(&s, 5);
    push_entry_test(&s, 7);
    push_entry_test(&s, 8);
    push_entry_test(&s, 9);
    dump_stack(&s);
    stack_cleanup_test(&s);

    empty_stack_pop_test(&s);
    push_entry_test(&s, 2);
    push_entry_test(&s, 3);
    push_entry_test(&s, 4);
    pop_entry_test(&s, 4);
    pop_entry_test(&s, 3);
    dump_stack(&s);
    push_entry_test(&s, 8);
    pop_entry_test(&s, 8);
    pop_entry_test(&s, 2);
    stack_cleanup_test(&s);
}

After running the test code, the following output is generated on the MinGW terminal.

$ ./a.exe
Pop empty stack test - [PASS]
Push entry (5) in stack test - [PASS]
Pop entry (5) in stack test - [PASS]
Push entry (7) in stack test - [PASS]
Push entry (8) in stack test - [PASS]
Push entry (9) in stack test - [PASS]
9 -> 8 -> 7 ->
Stack cleanup test - [PASS]
Pop empty stack test - [PASS]
Push entry (2) in stack test - [PASS]
Push entry (3) in stack test - [PASS]
Push entry (4) in stack test - [PASS]
Pop entry (4) in stack test - [PASS]
Pop entry (3) in stack test - [PASS]
2 ->
Push entry (8) in stack test - [PASS]
Pop entry (8) in stack test - [PASS]
Pop entry (2) in stack test - [PASS]
Stack cleanup test - [PASS]

Thanks for reading, please leave suggestions/comments if any.