implementing stacks using dynamic arrays

Boyko Bantchev Boyko_member at pathlink.com
Sun Apr 9 14:49:49 PDT 2006


In article <e1bbeq$2o6o$1 at digitaldaemon.com>, Mike Capp says...
>
>In article <e1b0dn$28vl$1 at digitaldaemon.com>, Boyko Bantchev says...
>>
>>int[] a;
>>int t;
>>..
>>a ~= t;
>>which makes a beautiful generic push operation for stacks.
>
>Maybe beautifully generic, but horrendously inefficient. It gives you linear
>complexity for each push, which is really not what you're looking for in a Stack
>implementation.
>
>cheers
>Mike

Does it really have to be so?  E.g., the stack might be based on a slice
of some other (sufficiently large) array, so that it can be resized without
actually reallocating and copying.  Should a push not be performed in
constant time then?
And should a `pop' operation (which was what I have been proposing in my
previous post) not cause even less trouble in terms of efficiency?

My point is, stack is too important a structure not to support it
smoothly in a language that already has the necessary instrumentation for that.

Cheers,
Boyko





More information about the Digitalmars-d mailing list