Was ist die beste Datenstruktur, um ein Element aus der Mitte zu entfernen?

Question

Die Datenstruktur muss wie ein Stapel sein. Nur mit einem Unterschied. Ich möchte von einem beliebigen Index aus poppen, nicht nur vom letzten. Wenn ich ein Element gepoppt habe n die Elemente mit den Indizes N > n muss wechseln zu N-1 . Irgendwelche Ideen?

P.S.

1. Schiebendes Element n in den letzten Index des Stapels.
2. Dann springt er heraus.
3. Dann löschen Sie stack[n]

ist eine schlechte Idee.

Answer 1

Ich glaube, Sie suchen nach einer verknüpften Liste.

Answer 2

Eine verknüpfte Liste ( std::list ) ermöglicht es Ihnen, ein Element aus der Mitte zu entfernen mit O(1) Komplexität und "zieht" automatisch die nachfolgenden Elemente hoch. Sie können eine verknüpfte Liste wie einen Stapel verwenden, indem Sie push_front . Sie müssen sich jedoch bewusst sein, dass der Zugriff auf ein Element in einer verknüpften Liste O(n) da Sie am Anfang der Liste beginnen und dann die Links von einem Element zum nächsten durchlaufen müssten, bis Sie beim Element n (es gibt also keine O(1) Indizierung)

Im Grunde müssten Sie

• Einen Iterator erstellen
• advance es zu positionieren n
• Holt das Element aus dem Iterator
• erase das Element, auf das der Iterator gerade zeigt

Einige Beispielcodes finden Sie hier aquí .

Answer 3

Sie müssen eine verknüpfte Liste implementieren, aber anders als bei einem Array wird die Reihenfolge in einer verknüpften Liste durch einen Zeiger in jedem Objekt bestimmt. Sie können also keine Indizes für den Zugriff auf die Elemente verwenden.