Error while implementing stack using linkedlist in C

Question

I am getting wrong output while trying to push data in the stack using this program. Even though the stack size is 5, printing the stack elements is running into infinite loop while giving wrong values. What is the error?

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

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

struct node *top = NULL;   

int count = 0;

void push(int num) {
    struct node *newNode = (struct node*)malloc(sizeof(int));
    newNode->data = num;
    newNode->next = NULL;

    if (top == NULL) {
        top = newNode;
    } else {
        struct node *temp = (struct node*)malloc(sizeof(int));
        temp = top;
        top = newNode;
        top->next = temp;
        free(temp);
    }
    count++;
}

int pop() {
    if (top == NULL) {
        printf("\nUnderflow- Stack is empty!");
        return -1;
    }
    struct node *temp = (struct node*)malloc(sizeof(int));
    temp = top;
    top = top->next;
    return temp->data;
}

int stackTop() {
    if (top == NULL) {
        printf("\nStack is empty");
        return -1;
    }
    return top->data;
}

void printStack() {
    if (top == NULL) {
        printf("\nStack is empty. Nothing to print");
    }
    printf("\n");
    while (top !=  NULL) {
        printf("%d ", top->data);
        top = top->next;
    }
}

/* Count stack elements */
void stack_count() {
    printf("\n No. of elements in stack : %d", count);
}

int main(void) {
    int poppedValue, topValue;
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);

    stack_count();

    printStack();

    poppedValue = pop();
    topValue = stackTop();

    printf("\nPop item : %d", poppedValue);
    printf("\nTop Value: %d", topValue);

    return 0;
}

Output:

 No. of elements in stack : 5
5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 ....

Answer 1

You don't need to use a temp node inside your push() function.You are just wasting memory by using it.

Following is the improved code and it runs successfully.

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

struct node{
    int data;
    struct node* next;
};
struct node* top = NULL;   

int count = 0;

void push(int num){
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = num;
    newNode->next =top;
    top=newNode;
    count++;
}

int pop(){
    if(top == NULL){
        printf("\nUnderflow- Stack is empty!");
        return -1;
    }

   int ans=top->data;
   struct node *temp = top;
    top = top->next;
    free(temp);
    count--;
    return ans;
}

int stackTop(){
    if(top == NULL){
        printf("\nStack is empty");
        return -1;
    }
    return top->data;
}


void printStack(){
    struct node *t=top;
    if(t == NULL){
        printf("\nStack is empty. Nothing to print");
    }
    printf("\n");
    while(t !=  NULL){
        printf("%d ",t->data);
        t=t->next;
    }
}

/* Count stack elements */
    void stack_count()
    {
        printf("\n No. of elements in stack : %d", count);
    }

int main(void) {

    int poppedValue, topValue;
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);

    stack_count();


    printStack();

    poppedValue = pop();
    topValue = stackTop();

    printf("\nPop item : %d", poppedValue);
    printf("\nTop Value: %d", topValue);

    return 0;
}

OUTPUT

 No. of elements in stack : 5
5 4 3 2 1
Pop item : 5
Top Value: 4

Answer 2

Your program has multiple problems:

• you allocate the node structures with the wrong size: sizeof(int). Casting the return value of malloc() is not needed in C and considered bad style. You should use this method that guarantees the correct size:

  struct node *newNode = malloc(sizeof(*newNode));
  

  This problem alone causes undefined behavior, which could explain the observed problem.

• You print newlines in front of your messages, this is not a bug but leads to confusing output. You should put the newline at the end of your messages.

• The push function allocates memory for temp but does not use it. temp is immediately overwritten with another value, which you free prematurely, leading to potential multiple calls to free for the same object. This is definitely a bug leading to undefined behavior.

• The pop function also messes the stack up and does not free the top node.

• you forget to decrement count when popping elements from the stack.

• Function printStack() modifies the stack top, memory is no longer accessible. You should use a temp variable.

Here is a modified version:

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

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

struct node *top = NULL;   
int count = 0;

void push(int num) {
    struct node *newNode = malloc(sizeof(*newNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = num;
    newNode->next = top;
    top = newNode;
    count++;
}

int pop(void) {
    if (top == NULL) {
        printf("Underflow. Stack is empty!\n");
        return -1;
    } else {
        int data = top->data;
        struct node *temp = top;
        top = top->next;
        free(temp);
        count--;
        return data;
    }
}

int stackTop(void) {
    if (top == NULL) {
        printf("Stack is empty\n");
        return -1;
    }
    return top->data;
}

void printStack(void) {
    if (top == NULL) {
        printf("Stack is empty. Nothing to print\n");
        return;
    }
    struct node *temp = top;
    while (temp !=  NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

/* Count stack elements */
void stack_count(void) {
    printf("No. of elements in stack: %d\n", count);
}

int main(void) {
    int poppedValue, topValue;

    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    stack_count();
    printStack();
    poppedValue = pop();
    topValue = stackTop();
    printf("Popped item: %d\n", poppedValue);
    printf("Top Value: %d\n", topValue);

    return 0;
}

Output:

No. of elements in stack: 5
5 4 3 2 1
Popped item: 5
Top Value: 4