Anfängerfrage: Stack programmieren - Compilerfehler
-
normal macht man sowas ohne "StackElement* next;"
lg lolo
-
Eigentlich seh ich das genauso.. ist ja keine LinkedList?!
Ich würde eher eine Variable mit der Anzahl gespeicherter Elemente deklarieren, aber da bin ich in C wohl eher out. Vermutlich nimmt man einen Zeiger der...?
-
geht beides aber zusätzlich zum zeiger, einen teil des speichers solltest dir per malloc besorgen falls die maximalanzahl vorher noch nicht fest steht und dann bei bedarf mit realloc vergrößern...
lg lolo
-
Eine linked list als unterliegende Datenstruktur für einen Stack macht durchaus Sinn, da so Einfüge- und Löschoperationen am Anfang und am Ende in konstanter Zeit ablaufen können.
-
@Athar also mein stack kennt nur push() und pop() und die macht der in O(1)
lg lolo
-
Athar schrieb:
Eine linked list als unterliegende Datenstruktur für einen Stack macht durchaus Sinn, da so Einfüge- und Löschoperationen in der Mitte in konstanter Zeit ablaufen können.
ftfy. Das wäre dann aber freilich kein Stack mehr.
noobLolo schrieb:
also mein stack kennt nur push() und pop() und die macht der in O(1)
Und push() in o(x), wenn vergrössert werden muss. Wie bestimmt man x?
-
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
-
Janjan schrieb:
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
Richtig. Aber nur für grosse Werte von 1.
-
Janjan schrieb:
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
ja aber dafür in diesem speziellen fall mit 2 zeigern pro element den doppelten speicher verbrauch.
mngbd schrieb:
Und push() in o(x), wenn vergrössert werden muss. Wie bestimmt man x?
keine ahnung
evtl. könnte man ja statt realloc einfach das letzte element des stacks mit einem neuen stack kaskadieren, sozusagen das beste aus beiden welten
lg lolo
-
noobLolo schrieb:
Janjan schrieb:
Eine Liste (richtig) implementiert hat mit Stackfunktionalität auch nur O(1) bei push() und pop().
ja aber dafür in diesem speziellen fall mit 2 zeigern pro element den doppelten speicher verbrauch.
sollten es nicht 3/2 mehr speicher verbrauch sein
-
Es ist grob n mehr Speicher. Denn jedes Element hat einen Zeiger auf sein Nachfoler. Bei einem üblichen Stack hat man nur einen Zeiger überhaupt.
-
Ich gehe davon aus, dass die linked list über ihren head und tail Buch führt und dass sie doppelt verkettet ist.
Der zusätzliche Zeiger kann durch Eigenheiten des Speichermanagement zu genau 0% mehr Speicherverbrauch führen. Einfach ausprobieren.
-
Athar schrieb:
Der zusätzliche Zeiger kann durch Eigenheiten des Speichermanagement zu genau 0% mehr Speicherverbrauch führen. Einfach ausprobieren.
bist du zauberer oder wie willst das machen
lg lolo
-
noobLolo schrieb:
bist du zauberer oder wie willst das machen
Nö, aber Speicher wird meist in Vielfachen von 8 bytes angefordert.
Mein
struct Node { Node* prev; Node* next; int value; };sind also 12 bytes + 4 bytes Verwaltungsaufschlag = 16 bytes.
Und ohne prev habe ich 8 bytes + 4 bytes = 12 bytes, aufgerundet auch 16 bytes.Kommt aber wie gesagt aufs System an. Anderswo kann der Overhead 8 bytes betragen und je nach Größe des Knotens schneidest du mit prev dann die nächsten 8 bytes an.