Best way to implement a dynamic stack type? or Am i abusing realloc?

Question

I'm using an obscure language that doesn't have a native stack type so I've implemented my own. Now, reading on the net i've found a few different approaches to do this.

This is my implementation (psuedo code)

//push method
function Push(int)
{
    Increase (realloc) stack by 4 bytes;
    Push int into the new memory area;
}

//pop method
function Pop()
{
    collect int from the top of the stack;
    reallocate (realloc) the stack to shrink it by 4 bytes;
    return int;
}

Now some people say that using a realloc() call to resize the stack after popping a value is bad for performance so i have a few questions:

1. Is it best to just grow the stack using malloc then free it at program end?
2. To resize the stack (push) is it best to increase by 4 bytes or more?
3. Is it best practise to increase the stack by doubling the memory allocated when it's filled?
4. What are your thoughts of the above code?

Answer 1

The standard technique is to only grow the size by factor of 2, and to shrink it only when the effective memory use is less than quarter.

This way you can be sure that you never use more than O(the memory you need), and you can also prove that the stack is amortized constant time.

(look at it this way: You pay three cents for each item entering or exiting the stack. Two of them will be used during the next copying that will occur.)

Link to wikipedia article explaining in more details