Basic Stack Operations using Linked List in C

Question

I have made a few functions for some basic stack operations using linked lists. Please review my code and suggest some ways to increase its readability. I would also love to hear ideas on how to make my code more compact and simple.

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

struct node
{
    int data;
    struct node *next;
};

void Traversal(struct node *ptr)
{
    do
    {
        printf("The element is : %d\n", ptr->data);
        ptr = ptr->next;
    } while (ptr->next != NULL);
}

int isEmpty(struct node *top)
{
    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isFull(struct node *top)
{
    struct node *n = malloc(sizeof(struct node *));
    if (n == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
    free(n);
}

struct node *push(struct node *top, int x)
{
    if (isFull(top))
    {
        printf("Stack Overflow\n");
    }
    else
    {
        struct node *n = malloc(sizeof(struct node));
        n->data = x;
        n->next = top;
        top = n;
    }
    return top;
}

struct node *pop(struct node *top)
{
    if (isEmpty(top))
    {
        printf("Stack Underflow\n");
    }
    else
    {
        struct node *n = top;
        top = top->next;
        free(n);
    }
    return top;
}

struct node *peek(struct node *top, int atPosition)  // To view the value stored at a specific postion
{
    struct node *ptr = top;
    if (atPosition < 0)
    {
        printf("Invalid Index\n");
    }
    else
    {
        for (int i = 1; i < atPosition && ptr->next != NULL; i++)
        {
            ptr = ptr->next;
        }
        printf("The data at index %d is %d\n", atPosition, ptr->data);
    }
    free(ptr);
    return top;
}

struct node *stackTop(struct node *top)
{
    printf("The data stored in stack top is %d\n", top->data);
    return top;
}

struct node *stackBottom(struct node *top)
{
    struct node *ptr = top;
    while (ptr->next != NULL)
    {
        ptr = ptr->next;
    }
    printf("The data stored in stack bottom is %d\n", ptr->data);
    free(ptr);
    return top;
}

Answer 1

push() has undefined behaviour any time its malloc() returns a null pointer.

isFull() leaks memory (because the matching free() call is unreachable). Also, whether or not an allocation is successful tells us nothing about future allocations.

Instead of the broken and unreliable isFull(), work on the principle of attempting the action and taking appropriate recovery steps when it fails (sometimes described as easier to ask for forgiveness than permission, or EAFP):

struct node *push(struct node *top, int x)
{
    struct node *n = malloc(sizeof *n);
    if (!n) { return n; }  /* failure */
    n->data = x;
    n->next = top;
    top = n;
    return top;
}

It's usually a bad idea for low-level library functions to generate output (especially to stdout) - you might want to use the code in a GUI program, and report errors via a status bar or pop-up window, for example. I would make it the caller's responsibility to examine the result and report it appropriately:

if (!push(top, x) {
    fputs("Out of memory\n", stderr); /* Not "stack overflow" - that's misleading! */
}

Answer 2

• isEmpty is anti-idiomatic:

    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
  

  is a very long way to say

    return top == NULL;
  

• isFull is very dubious. Why call malloc twice? push is very well capable to detect the malloc failure.

  BTW, once malloc fails, it is unsafe to call printf.

• The utility library shall not print anything. Returning a success/failure indication is enough; let the caller take an appropriate recovery action.

  In any case, error messages shall go to stderr, not stdout.

• Why peek frees the ptr? Consider what happens on atPosition being 1. You have stack corruption, and a memory leak right away.

  Also, if atPosition is larger than the stack size, peek reports incorrect results (there is no such position, yet it prints something).

• stackBottom should test that the stack is not empty. Otherwise, ptr->next dereferences a null pointer.

  And again, it should not free anything.