Dynamic data structures

I've learned a strategy to resize the size of a data structure to
implement a dynamic data structure as follows:

E.g. for a stack:

- If the stack if full, create a new one with double of the old size.

before insertion operation it looks like:
|xxxxxxxxxx|
after insertion operation:
|xxxxxxxxxx|x |


- If number of elements in the stack gets below a quarter of the size
of the stack, create a new one of half the old size.

before deletion operation:
|xxxxx| |
after deletion operation:
|xxxx | |



With such a strategy (doubling if full and halving if count gets below 25%),
an amortized worst case analysis shows that the average cost per operation is
constant.



Are there better strategies?

Thanks a lot.
.

Relevant Pages

  • Re: Yet Another Spinoza Challenge
    ... It's obviously a very, very sensible choice, but it is not the only ... Any searchable dynamic data structure will do. ... In what sense are you using the word "stack" in the above paragraph? ... The push operation ...
    (comp.lang.c)
  • Re: Is there a clean, simple way to do this stack change?
    ... doing that is for setting up a special data structure. ... and second cleanest ways I can see to do this use return stack ... Once everything is ready on the stack, ... word wraps it all up by moving everything above the left marker into ...
    (comp.lang.forth)
  • Re: CFileDialog: "My Computer" not shows files and dirs
    ... CFileDialog, the dialog and the programm crashes! ... invalid instruction exception caused by a stack clobber, ... the data structure is actually longer and a memory overwrite occurs. ... You can install ...
    (microsoft.public.vc.mfc)
  • Controlled types and exception safety
    ... I can classify the stack's operations by assigning them any of the above four levels, so that I know what can be expected when an exception is thrown for any reason (like inability to allocate more memory, or alike). ... For example, if the Push method of the stack gives me the strong guarantee, then I *know* that by calling this method either the new element will be appended to the stack, or the stack will remain unchanged, so that even if the exception is thrown, I don't have to worry about the stack's internal consistency. ... Since stack can be a dynamic data structure, assigning one stack object to another may involve destroying one existing data structure *and* creating a new one in its place. ...
    (comp.lang.ada)
  • Re: Encrypt/ Decrypt in NdisIM with Ethernet
    ... That again could be because stack gets corrupted. ... write to an array or initialize a data structure? ... when I break the debug to enter some ... >>> A fatal system error has occurred. ...
    (microsoft.public.development.device.drivers)