FIFO stack

[Christophe]

"Nick Sabalausky" , dans le message (digitalmars.D.learn:30309), a
 écrit :
> "Dominic Jones" <dominic.jones at qmul.ac.uk> wrote in message 
> news:j89arh$2ua3$1 at digitalmars.com...
>>> Also an plain array is a good stack. :)
>>
>> I'd rather not use a plain array because (I assume) that when I push
>> or pop using arrays, a swap array is created to resize the original.
>> If this is not the case, then an array will certainly do.
>> -Dominic
> 
> The matter of using D's arrays as a LIFO is discussed the other branch of 
> this thread (ie, you can do it, but it's slow because a "pop then push" will 
> reallocate and copy), but as far as a FIFO: That may actually be reasonable 
> to do as an array:
> 
> Decreasing the length of an array (from either end) is a trivial matter that 
> never allocates or copies. Appending to the end *usually* doesn't involve 
> allocating. So the only issue I see it that the FIFO will "march" across 
> memory. I guess that's probably not a problem as long as the GC knows it can 
> reclaim the stuff you've popped off (Does it do that? Ie, if you do "x = 
> x[10..$];" and there's no other references, is the GC smart enough to 
> reclaim those first ten spots? I guess I would assume so.) 
> 
> 

As far as I understand, if there is a pointer to an allocated memory 
block, the GC keeps the whole memory block. So the data at the beginning 
of x will be kept as long as x is not reallocated (but x will be 
reallocated at some point, because it can't walk across memory 
indefinitely, unless the GC is particularly efficient at avoiding 
reallocation).

AFAIC, if I had to design a FIFO, I would use a circular array to avoid 
constant growing and reallocation of the array.