implementing stacks using dynamic arrays

[Derek Parnell]

On Sun, 09 Apr 2006 17:32:20 -0700, Walter Bright wrote:

> Mike Capp wrote:
>> 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.
> 
> No, it is rather efficient. It does't realloc/copy for each push, as it 
> uses a power of 2 algorithm to resize the array.

And also, I believe, that popping an element does not involve a memory
reallocation either. The empty space is not reclaimed and is available for
the next 'push' operation.

For example ...

   int Pop(int[] pStack)
   {
       int l_Item;
       if (pStack.length > 0)
       {
           // Grab last item
           l_Item = a[$-1];
           // Remove it from the stack list.
           pStack.length = pStack.length - 1;
       }
       else
       {
           throw new Exception("Pop: Stack is empty");
       }

       return l_Item;
   }



-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocracy!"
10/04/2006 12:01:04 PM