Segmentation fault when reading from stack

Question

This is my first time creating stacks. I'm quite clear at what I must do, but am quite discouraged by the code not working.

It runs fine till I try to retrieve any data from the root, which immediately results in a segfault.

Here's my program:

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

struct stackNode
{
    char letter;
    struct stackNode * next;    
};

int size=0;
int capacity=10;

struct stackNode * root=NULL;

void push(char data, struct stackNode * root)
{
    if(size==capacity)
    {
        printf("Error: Stack Overflow\n");
        return;
    }

    struct stackNode * new=(struct stackNode *)malloc(sizeof(struct stackNode *));
    new->letter=data;
    new->next=root;
    printf("%c,%u", new->letter, new->next);
    root=new;
    printf("%c,%u", new->letter, new->next);
    size++;
}

char pop(struct stackNode ** root)
{
    if(size==0)
    {
        printf("Error: Stack is Empty\n");
        return '\0';
    }

    printf("\npop*\n");

    char temp;
    printf("\n*\n");
    struct stackNode * tempad;
    printf("\n*\n");
    temp=(*root)->letter;
    printf("\n*\n");
    tempad=*root;
    printf("\n*\n");
    *root=(*root)->next;
    printf("\n*\n");
    free(tempad);
    printf("\n*\n");
    size--;
    return temp;
}

int main()
{
    push('c', root);
    push('v', root);
    push('n', root);

    printf("%c %c %c", pop(&root), pop(&root), pop(&root));
}

Here's the output:

pop*

*

*
Segmentation fault

Could someone point out the mistake?

Answer 1

The main issue is usage of unnecessary global variables which seem to be causing confusion. In push, the parameter is of type struct stackNode * yet it's being manipulated as if it referred to the global root. But root = new is purely local and has no impact on the global root. However, size++ does impact the global scope. This corrupts the stack's logical state, and your error handler at the beginning of pop thinks that size == 3 and doesn't complain. The function then dutifully dereferences root, crashing the program.

A correct stack class should not use global data. It should encapsulate all necessary state in structs. This makes it reusable, enabling creation of multiple stacks (a property I'd want in most classes I'm using).

A few other suggestions:

• Avoid side effects where possible. Prints are OK for temporary debugging purposes but should be completely separated from program logic otherwise.
• If you are planning on writing error handlers, print to stderr and avoid magic values like return '\0'; that might be mistaken for actual node data.
• Don't cast the result of malloc. This can suppress errors and is visually noisy.
• Hardcoding capacity feels pretty arbitrary. I'm not sure there's any point to having this (but if there is, add it to the struct). If there's too much metadata about the stack inside each node (ideally, there should be none), create a Stack struct to contain this metadata and point it to the actual stackNode chain.
• Another stack design point: malloc/free are slow. For character data, a simple array with a top pointer will be faster and simpler to implement. You can amortize allocation calls with periodic doubling the array when top >= capacity and contracting when top < capacity / 2.

Here's a quick re-write (without the suggestion for the Stack wrapper struct or the array):

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

struct stackNode {
    char letter;
    struct stackNode *next;
    int size;
};

void push(char data, struct stackNode **root) {
    struct stackNode *new = malloc(sizeof(*new));
    new->size = *root ? (*root)->size + 1 : 1;
    new->letter = data;
    new->next = *root;
    *root = new;
}

char pop(struct stackNode **root) {
    if (!*root || !(*root)->size) {
        fprintf(stderr, "pop from empty stack\n");
        exit(1);
    }

    char popped = (*root)->letter;
    struct stackNode *cull = *root;
    *root = (*root)->next;
    free(cull);
    return popped;
}

int main() {  
    struct stackNode *root = NULL;
    push('c', &root);
    push('v', &root);
    push('n', &root);

    while (root) {
        printf("%c ", pop(&root));
    }

    puts("");
    return 0;
}

Answer 2

This is really confusingly written code (i.e globals with the same name as variables in the local scope). I'm just going to rewrite it, untested and on mobile but should be fine. You can diff to see the issue(s). For one thing though you're setting local variable root to the newest allocation rather than global root.

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

struct stackNode
{
    char letter;
    struct stackNode* prev;    
};

stackNode* kTailStack = NULL;

void push(char data)
{
    stackNode* p=(stackNode *)malloc(sizeof(stackNode));
    p->letter=data;
    p->prev=kTailStack;
    kTailStack = p;
}

char pop()
{
    stackNode* prev_tail = kTailStack;
    char n = 0;

    if (prev_tail != NULL)
    {
        n = prev_tail->letter;
        kTailStack = prev_tail->prev;
        free(prev_tail);
    }

    return n;
}

int main()
{
    push('c', kTailStack);
    push('v', kTailStack);
    push('n', kTailStack);

    printf("%c %c %c", pop(kTailStack), pop(kTailStack), pop(kTailStack));
}