What is the best way of implementing a dynamically resizing stack in C?

What is the best correct way of implementing a dynamically resizing stack in C?

For example, i want to allocate an amount of memory to a stack but when that stack gets full, the memory allocated is doubled to accomodate new data, etc.

I have a stack implemented at the minute using a simple array of void pointers, this way i can store pointers of all types so it's quite reusable. When i try to implement this using malloc()/realloc() i run into errors while doing pointer math due to void pointers not having a size assigned.

What is the best correct way to implement a dynamically resizable stack in C?

EDIT:

I was trying something like this code (error checking removed) but i now understand that i can not interact with void pointers like this. So i'm just having a think how to do something like this legally. This is a big learning exercise for me as i've never really been exposed to C.

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

#include "stack.h"

static int index = 0;

void* CreateStack(void)
{
    void *stack = malloc(INITIAL_STACK_SIZE);
    return stack;
}

void* Pop(void *stack)
{
    return stack + index--;
}

void Push(void *stack, void *value)
{
    *(stack + index) = value;
}

v开发者_如何学Pythonoid FreeStack(void *stack)
{
    free(stack);
}

---

I think the problem is you're using the wrong size in your calls. You don't want the size of the pointee - you want the size of the pointer itself.

---

sounds like you are doing

malloc(n * sizeof(void)) 

directly or indirectly, you need

malloc(n * sizeof(void*))

of course the real answer is std::stack (in c++)

---

One method is to use an array for the stack. Keep track of the array capacity. If the array becomes full, allocate a new array, copy old elements to new array, then delete the old array.

Another option is to use a linked-list as the foundation for the stack. This allows dynamic allocation on every new element.

---

I've answered this before, as a subset of a previous question:

https://stackoverflow.com/questions/2006726/which-would-you-prefer-to-have-to-maintain/2007647#2007647

You'd have to adapt things slightly - replace char* with void* throughout, rename "addString" to "push" and write a "pop" function. Oh, and add error-checking on the calls to malloc and realloc, which was omitted in that answer because it was omitted in the questioner's code.

Like Neil says, though "best" is very subjective. A growing array is only one way to implement a stack. Depending on the usage pattern and your requirements on code complexity, speed and memory use, you might want a linked list, or you might want a hybrid list/array strategy similar to the std::deque class in C++.

---

Use Dave Hanson's code from C Interfaces and Implementations. It's a great book, and you'll see just how to do the dynamic-array trick. Elegant and efficient, and highly reusable! The code is free to download.