Dynamically resizing a stack, in C.

[Stremik]

Hi everybody. I have trouble dynamically growing a stack.
Any help will be appreciated.

So, I have...

#define CAPACITY 128

typedef double ElemType;
typedef struct stack_struct *StackPtr;
typedef struct stack_struct StackStruct;

struct stack_struct{
    ElemType items[CAPACITY];
    int top;
};

than..., at a runtime a stack is being created dynamically.

StackPtr stk_create(){
    StackPtr s = malloc(sizeof(struct stack_struct));
    s->top = -1;
    return s;
}

Now..., when the stack is full,I want to allocate a new chank of space and copy
the old stack in there. Problem is, I'm not shure how to do that.
If I do it the same way it is done in stk_create(use malloc and sizeof old stack
times 2), than won't it copy the whole struct with the array and int top in it?
Won't I have than a new struct with two int tops in it?

I was also thinking about just creating a new array two times the size of the
old one and than just point s->items to it, but than again, my professor told
me to make sure and free() every occurance of memory allocation done with malloc.
But I used malloc to allocate memory for the whole struct(with array and int in it).
What would I be freeing than if I will only resize the array inside the struct?

Thank you.

[fluppe]

Hi,

maybe it would be best to resize the "items" - Array, right ?
The procedure to do so might be to use a linked list, (or, c++ has such things ready, a "list").
Anyway, the memory will not be in one piece and operating on a linked list might be slower than operating on an array.

You could do like this

#define CAPACITY 128 // obsolete then ... see below

typedef double ElemType;
typedef struct stack_struct *StackPtr;
typedef struct stack_struct StackStruct;

struct stack_struct{
    ElemType *items;
    int top;
    int len; // to hold the length of your array
};

and then

void stk_create(int len, StackPtr s){
    
    s->items  = malloc(sizeof(ElemType)*len);
    s->len = len; 
    s->top = -1;

}

The input must be a reference to an existing StackStruct though, but it might be handled with a return value as well.

What you need now is a function to resize the array in your StackStruct.
Is that what you intend ? So to say a struct with a dynamic field "items" ?


What you need then is a function to extend your Array, like (briefly)

void extend_struct(int add_len, StackPtr s, Stack_Ptr add_s){ // StackPtr add_s can of course be replaced by a pointer to the 
                                                                              //     Elements.
// some inits... left out

rep = malloc(sizeof(ElemType)*(s->len + add_len));
// write all data in the desired order to "rep" ... left out

free(s->items);
s->items = rep;

}

Maybe this is what you intend ??

Greets,

p.s. : forgot about that:

you'll have to free the field "items" before quitting your application. Therefore you should write another function ...

[Catfish666]

If you're in C and use malloc(), then you can use realloc() which seems to be exactly what you want.

http://www.cplusplus.com/reference/cstdlib/realloc/

[fluppe]

Hi,
@catfish
i didn't know "realloc()" also copies the values ( beginer, you see ...)

But if not, it would be quiet a useless function anyway i guess ...
thanks for that information.