Aufbau einer Deque

Hallihallo,

ich muss zur Zeit eine Ausarbeitung zum Double Ended Queue erstellen. Ich habe im Internet auch schon einiges zum Thema gefunden, wie man eine mit Hilfe der STL erstellt und damit arbeitet etc. Allgmein Container etc.

Leider finde ich keine Beschreibung oder Erklärung wie die Deque im "verborgenen" arbeitet. Ich weiß das die Deque einen Verwaltungsvektor besitzt der wiederrum auf mehrere Datenvektoren bzeigt. Aber wie kann das alles verwaltet wird finde ich leider nirgends.

Wäre nett wenn vl irgendjemand eine Ahnung hat wo ich das nachschauen könnte, aus der deque.h werd ich irgendwie nicht schlau.

mfg
Chris

Fencer

Du kannst eine Deque zum Beispiel mit einem einfachen Array aufbauen:

Array arr initialisieren. zwei ints beg, end und size. size auf 0 setzen

einfügen:
wenn size=0, beg auf array_size-1 und end auf 0 setzen.

wenn size!=array_size an arr[beg] bzw. arr[end] den neuen Wert einfügen. size um eins erhöhen

beg/end (je nachdem wo du anfügts) um eins erniedrigen/erhöhen. wenn es einen Überlauf gab z.B. beg=-1 dann ans andere Ende des Array springen (z.B. beg=array_size-1)

entfernen: wenn size>0 beg/end jetzt umgegekehrt zum Anfang erhöhen/erniedrigen.
dann size noch um eins erniedrigen.

Fehlerbearbeitung ist jetzt hier nicht beschrieben und natürlich ist dies nur eine Lösung wenn du ungefähr die größe kennst. Ansonsten kanns du auch einen Vektor benutzen. Kann sein das ein paar kleine Flüchtigkeits drin sind. :xmas1: :xmas1:

Nexus

Schau mal hier nach. Dort steht unter anderem, dass die std::deque implementierungsabhängig ist. Es gibt also nicht die Deque. Gemeinsamkeiten stehen aber auch auf der verlinkten Homepage.

Für die konkrete Implementierung deiner Deque schaust du wohl doch am besten im Sourcecode nach.

Fencer

Recht hat er

aber mein vorschlag ist eine lösung