## c't-Projekte - Mailinglisten

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

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

Absender: Frank Menzel
Datum: Fr, 26.09.2008 19:30:37
In-reply-to: <A6D9C09A-11AE-4EE7-99D9-D53087213B87@xxxxxxxxxxxxxxx>

    Hallo Timo,
    stimmt natürlich wieder alles. Habe eben "bloß" den vorhandenen Stack,
    der mittels Array implementiert ist, angepasst um genannte Funktion ohne
    die Datenstruktur an sich zu ändern. Mittels Zeiger ist natürlich alles
    viel besser, schöner und effizienter. Das Define kann sicher auch
    wegfallen, wollte bloß die Trennung verdeutlicht lassen zwischen Stack
    und Queue und damit Lifo bzw. Fifo.
    Ist übrigens alles nebenbei angefallen, weil ich das Stackverhalten
    benutzen wollte aber eben die Daten genau andersrum vorliegen. Also
    entweder Daten via Push rein und von vorn auslesen und abfahren oder
    vorn reinschieben und via Pop abfahren. Letzteres hätte den Vorteil,
    dass das Stackverhalten gleich bleiben könnte. Muss dann aber trotzdem
    noch modifiziert werden, falls ein Anfahrpunkt doch mittlerweile bei
    einem Hindernis liegt und zu Beginn der Pfadplanung nicht erkennbar war.

    Gruß, Frank

    -----Ursprüngliche Nachricht-----
    Von: ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx
    [mailto:ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx] Im Auftrag von Timo
    Sandmann
    Gesendet: Freitag, 26. September 2008 14:21
    An: Entwicklung rund um den c't-bot
    Betreff: Re: [ct-bot] Erweiterung Posstack als FIFO-Queue

    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

    _______________________________________________
    ct-bot-entwickler Mailingliste
    ct-bot-entwickler@xxxxxxxxxxxxxxxxx
    http://www.heise.de/bin/newsletter/listinfo/ct-bot-entwickler

- Antworten:
  - Re: [ct-bot] Erweiterung Posstack als FIFO-Queue
    - From: Timo Sandmann

- Referenzen:
  - Re: [ct-bot] Erweiterung Posstack als FIFO-Queue
    - From: Timo Sandmann

- Voriger (Datum): Re: [ct-bot] Erweiterung Posstack als FIFO-Queue, Timo Sandmann
- Nächster (Datum): Re: [ct-bot] Erweiterung Posstack als FIFO-Queue, Timo Sandmann
- Voriger (Thread): Re: [ct-bot] Erweiterung Posstack als FIFO-Queue, Timo Sandmann
- Nächster (Thread): Re: [ct-bot] Erweiterung Posstack als FIFO-Queue, Timo Sandmann
- Indizes:
  - Datum
  - Thread