I am implementing a stack using linked list in C, and I stumbled upon two issues:

1. I need the stack_pop function to return a valid value temp, that is the temporary node/cell, and therefore, I can't free it. So, 1) Do you think freeing each node for every pop function call is better than until the end using the stack_destroy() 2) How can I achieve both, free(temp) and return it at the same time in stack_pop?

2. How bad my implementation becomes not using exit(1) in both stack_push and stack_pop functions?

This is the implementation:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
//#include "stack.h"

#define STRESS_TEST_ITERATIONS (100)
#define STACK_EMPTY (-1)

//// Stack

// Linked list
typedef struct {
    int data;
    Cell* next;
} Cell;

struct stack_l {
    size_t count;
    Cell *top;
};
typedef struct stack_l *Stack;

Stack stack_create(void) {
    Stack stackL;
    stackL->count = 0;
    stackL->top = NULL;
    return stackL;
}

void stack_push(Stack stack, int elm) {
    Cell *temp = malloc(sizeof(Cell));
    if (!temp) {
        printf("Overflow\n");
        /*exit(1);*/
    }
    stack->count  ;
    temp->data = elm;
    temp->next = stack->top;
    stack->top = temp;
}

int stack_pop(Stack stack) {
    Cell* temp;
    if (stack_isempty(stack)) {
        printf("Underflow\n");
        return STACK_EMPTY;
        //exit(1);
    }
    else {
        temp == stack->top;
        stack->top = stack->top->next;
        temp->next = NULL;
        stack->count--;
        return temp;
        /*free(temp);*/
    }
}

int stack_isempty(Stack stack) {
    return stack->top == NULL;
}

void stack_destroy(Stack stack) {
    Cell *temp;
    while (!stack_isempty(stack)) {
        temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
    }
}

CodePudding user response：

You've got stack_pop declared to return an int, but you're attempting to return a Cell * which doesn't make sense.

Copy the value in the popped cell to a local variable, free the popped cell, then return the value.

    temp = stack->top;
    stack->top = stack->top->next;
    temp->next = NULL;
    stack->count--;
    int val = temp.data;
    free(temp)
    return val;

Also, it makes no sense to call exit in either stack_push or stack_pop as that ends the program.

CodePudding user response：

I think it is a bit overcomplicated. You only need to remember the previous stack pointer. Nothing else

#define STACK_EMPTY -1

typedef struct stack
{
    int data;
    struct stack *prev;
}stack;


stack *push(stack *sp, int data)
{
    stack *new = malloc(sizeof(*new));
    if(new)
    {
        new -> prev = sp;
        new -> data = data;
    }
    return new;
}

int pop(stack **sp)
{
    stack *new;
    int result = STACK_EMPTY;
    if(sp && *sp)
    {
        result = (*sp) -> data;
        new = (*sp) -> prev;
        free(*sp);
        *sp = new;
    }
    return result;
}

int main(void)
{
    stack *stack_pointer = NULL;
    int result;

    stack_pointer = push(stack_pointer, 1);
    stack_pointer = push(stack_pointer, 2);
    stack_pointer = push(stack_pointer, 3);

    do
    {
        result = pop(&stack_pointer);
        printf(result == STACK_EMPTY ? "STACK_EMPTY\n" : "%d\n", result);
    }while(result != STACK_EMPTY)   ;
}

https://godbolt.org/z/eT86os9GY

or a bit more consistent (no need to reserve special data for stack empty):

typedef struct stack
{
    int data;
    struct stack *prev;
}stack;


stack *push(stack **sp, int data)
{
    stack *new = malloc(sizeof(*new));
    if(new)
    {
        new -> prev = *sp;
        new -> data = data;
        *sp = new;
    }
    return new;
}

int pop(stack **sp)
{
    stack *new;
    int result = 0;
    if(sp && *sp)
    {
        result = (*sp) -> data;
        new = (*sp) -> prev;
        free(*sp);
        *sp = new;
    }
    return result;
}

int main(void)
{
    stack *stack_pointer = NULL;
    int result;

    push(&stack_pointer, 1);
    push(&stack_pointer, 2);
    push(&stack_pointer, 3);

    do
    {
        result = pop(&stack_pointer);
        printf("%d\n", result);
    }while(stack_pointer)   ;
    printf("Stack was empty so the loop has exited\n");
}