How Can I Know If This Program Works As i Intended( Dynamic stack )

Question

enter code herei was watching a video in data structures in C , and when i understand the abstract view of the concept i go try implementing it without watching the implementation in the video , and what i implement wasn't in the video, the video was affording stack(static array and linked list). so i thought maybe i try my own that is using (dynamic array), and the program did work but i'm still in doubt if it 100% work without any side effect .it's just that i can't believe the program works. this program is intended to solve the overflow when pushing new value in the stack and without wasting memory space

(my doubts are : if it reallocate memory each time i push a new value correctly )

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


int *ptr;
int top = -1;
int size = sizeof(int) ;

void Push(int x);
void Pop();
int Top();
char isEmpty();

int main(){

    Push(1);
    Push(2);
    printf("%d\n", *(ptr+top));
    Pop();
    printf("%d\n", *(ptr+top));
    printf("top = %d, is empty : %c", Top(), isEmpty());


    return 0;
}

void Push(int x){
    if(top == -1){
        ptr = (int* )malloc(size);
        *ptr = x;
        top++;
    }
    else{
        realloc(ptr, size * (top + 1));
        *(ptr+top+1) = x;
        top++;
    }

}

void Pop(){
    if(top == -1){
        return;
    }
    free(ptr+top);
    realloc(ptr, size * top - 1);
    top--;
}

int Top(){
    if(top != -1){
    return *(ptr+top);
    }
    printf("Empty Stack\n");
    return 0;
}

char isEmpty(){
    if(top == -1){
        return 'T';
    }
    return 'F';
}

"My doubts are : if it reallocate memory each time i push a new value correctly", and the answer to that is ***no***. There's no guarantee that the [`realloc`](https://en.cppreference.com/w/c/memory/realloc) function can reuse the existing memory, it might need to allocate new memory and copy the current contents to that new memory. Then just like `malloc` it *returns* the pointer to the new memory. — Some programmer dude, Apr 30 '23 at 07:40
Also note that if `realloc` fails it will return a `NULL` pointer, but the original memory will be left remaining. So you should never reassign directly back to the pointer variable you use in the call. So `ptr = realloc(ptr, ...)` could lead you to lose the original and still valid memory. — Some programmer dude, Apr 30 '23 at 07:40
How to use `realloc` : See https://stackoverflow.com/questions/21006707/proper-usage-of-realloc — Support Ukraine, Apr 30 '23 at 07:52
OT: `isEmpty` is very unusual... Returning a character `T` or `F` for True/False is rather special (strange). If you don't want to use a bool type, the normal C way would be to return an `int` and use zero for False and a non-zero value (typically one) for True — Support Ukraine, Apr 30 '23 at 07:56
@SupportUkraine it's not a big deal i just wanted to see if the function works or not , and you're right . maybe i can return an integer or bool ( and use if to print true or false) — Az_T, Apr 30 '23 at 08:05
This looks like something for [codereview.se]. And the [question title](https://meta.stackexchange.com/a/388112/620615) is terrible. — user3840170, Apr 30 '23 at 08:19
@user3840170 Sorry i'm new here , and this is my first question. And Thanks , i will keep in mind how to question properly and use Code Review — Az_T, Apr 30 '23 at 08:30

Vlad from Moscow · Accepted Answer · 2023-04-30T08:41:09.357

Your program incorrectly manages memory.

For example in the function Push the address of the reallocated memory is lost

realloc(ptr, size * (top + 1));

So this statement

*(ptr+top+1) = x;

in general results in undefined behavior.

Moreover in this call of realloc

realloc(ptr, size * (top + 1));

the expression (top + 1) yields an incorrect number of allocated elements.

In the function Pop there is the same problem

realloc(ptr, size * top - 1);

and again the used expression size * top - 1 within the function is invalid.

Also there is used an incorrect pointer expression to free memory

free(ptr+top);

You have to pass to the function free a pointer that was returned by allocation function malloc, calloc or realloc.

The function Top does not check whether the stack is empty that again can invoke undefined behavior.

Pay attention to that it is not a good design when functions depend on global variables. It would be better to declare a structure that will specify properties of the stack. For example

struct Stack
{
    int *base;
    size_t top;
};

Then in main you could write

int main( void )
{
    Stack stack = { .base = NULL, .top = 0 };
    //...

The function isEmpty could look the following way

int isEmpty( const struct Stack *stack )
{
    return stack->top == 0;
}

and be called for example like

if ( isEmpty( &stack ) ) puts( "The stack is empty." );

The function Push could look the following way

int Push( struct Stack *stack, int item )
{
    int *tmp = realloc( stack->base, ( top + 1 ) * sizeof( *base ) );
    int success = tmp != NULL;

    if ( success )
    {
        stack->base = tmp;
        stack->base[top++] = item;
    }

    return success;
}

The function Top can look like

int Top( const struct Stack *stack, int *item )
{
    if ( stack->top != 0 )
    {
        *item = stack->base[top - 1];
    }

    return stack->top != 0;
}

and be called like for example

int item;

if ( Top( &stack, &item ) )
{
    printf( "top = %d\n", item );
}
else
{
    puts( "The stack is empty." );
}

How Can I Know If This Program Works As i Intended( Dynamic stack )

1 Answers1