## c't-Projekte - Mailinglisten

[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

### Re: [ct-bot] Erweiterung Posstack als FIFO-Queue

Absender: Timo Sandmann
Datum: Fr, 26.09.2008 14:20:42
In-reply-to: <000001c91f45$9f5e9470$0200a8c0@mexpnew>
References: <000001c91f45$9f5e9470$0200a8c0@mexpnew>

    Hi,

    Am 25.09.2008 um 21:33 schrieb Frank Menzel:

>     Hallo,
>     habe den Positionsstack etwas erweitert, um diesen als FIFO-Queue
>     verwenden zu können. Also damit gibt es nicht mehr nur die

> `Stackfunktionen POP und PUSH sondern auch QUEUE und DEQUEUE um (wie` `bei`

>     Push) eine Koordinate hinten anzufügen und vorn wieder zu entnehmen.

    das klingt sehr sinnvoll.

`Aber warum werden bei der Entnahme eines Elements aus der FIFO alle` `anderen darin um eine Position verschoben? Das ist ja sehr` `ineffizient. Ich würde eine Datenstruktur mit zwei Zeigern (Indizes)` `vorschlagen, einer auf das erste und einer auf das letzte Element, die` `dann nur erhöht / erniedrigt werden müssen. Am besten fasst man das` `Array dabei als Ring auf, am "Ende" angekommen, springt der jeweilige` `Index wieder auf 0. Ist die Arraygröße eine 2er-Potenz, ist diese` `Modulo-Operation sehr effizient.`

`Ich wäre außerdem dafür, keine neue Option "#ifdef POS_QUEUE_FIFO"` `einzuführen, sondern wenn der Positionsstack aktiviert ist, dann ist` `auch immer die FIFO-Version mit aktiv, das erspart komplizierte` `Abhängigkeiten und der Overhead ist minimal.`

    Grüße,
    Timo

- Antworten:
  - AW: [ct-bot] Erweiterung Posstack als FIFO-Queue
    - From: Frank Menzel

- Referenzen:
  - [ct-bot] Erweiterung Posstack als FIFO-Queue
    - From: Frank Menzel

- Voriger (Datum): [ct-bot] Erweiterung Posstack als FIFO-Queue, Frank Menzel
- Nächster (Datum): AW: [ct-bot] Erweiterung Posstack als FIFO-Queue, Frank Menzel
- Voriger (Thread): [ct-bot] Erweiterung Posstack als FIFO-Queue, Frank Menzel
- Nächster (Thread): AW: [ct-bot] Erweiterung Posstack als FIFO-Queue, Frank Menzel
- Indizes:
  - Datum
  - Thread