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! */
}

• Ultimate: Could you elaborate more on how to write a more reliable isFull() function applying the EAFP principle
• Toby Speight: As I demonstrate, isFull() isn't necessary. Instead, where it's used (e.g. in push(), attempt the allocation, and take alternative action if it fails. There's no reliable way to know in advance whether allocation will succeed. "Container is full" is only meaningful for a container with a predetermined capacity.

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.

• Ultimate: In peek and stackBottom , I used free() because the main utility of these functions was only to print the required values to the user. Is there any specific reason why I should not use free() in these functions?
• Toby Speight: Why do you say it's unsafe to call printf() after a malloc() failure? That seems reasonable to me.