Stack Implementieren in C++

[Tobi_tobsen (Gast)]

Hallo ich hab hier eine Übungsaufgabe zur Prüfungsvorbereitung,
ich kann mir vorstellen das hier nicht gern geholfen wird wenn es um 
Studium etc geht.
Wäre trotzdem super wenn mir jemand helfen könnte:
Die Aufgabe lautet wie folgt:

Implementieren Sie einen Stack, entwerfen Sie die Methode Push und Pop.
Push soll mit dem Rückgabewert informieren ob noch platz für das auf den
Stapel zu legende Element ist.
Des weiteren benötigt der Stack eine Methode mit dem Namen "isEmpty" die 
1 zurückliefert wenn der Stack leer ist. Ansonsten soll sie 0 
zurückliefern.

Der Konstruktor des Stacks soll als Argument die Größe des Stacks 
besitzen.
Der vom Stack verwendetet Speicher soll dynamisch angefordert werden

(Zum abfragen des Fehlerstatus soll das Attribut errorState und die 
Methode GetErrorstate verwendet werden.)

Bereits gegeben ist folgende Klassendeklaration:

#ifndef _STACK_H
#define _STACK_H
class Stack
{
privat e :
int, *data,.
int arlz i / / aktuelle Anzahl Stackelemente
int maxanz; / / maximale Anzahl Stackelemente
int errorState;
public:
Stack(int s);
-Stack (void) ; int push ( int w) ; int pop (void) ;
int isEmpty (void) ; int GetErrorState O ;
];
#endif /* _STACK_H * /

Mein Lösungsvorschlag für die Klassendefinition wäre folgender wobei 
hier sicher noch Fehler vorhanden sind.
Kann mir jemand bitte Tipps geben was falsch ist und wie es richtig 
wäre, hoffe es ist nicht komplett falsch!

#include "iostream.h"
#include <Stack.h>


Stack::Stack (int s)
{data=new int[s];}


Stack:~Stack (void)
{
delete data[];
}


int Stack::Push (int w)
{anz=anz+1;
data[anz-1]=w;

if (anz>=maxanz)
{return 0;}

else
{ return 1;}
}


int Stack::Pop (void)
anz=(anz-1);
data[anz-1]=0;//muss hier Speicher freigegeben werden, wenn ja wie???



int Stack::isEmpty()
{
if ((anz)>0)
{return 0;}
else
 {return 1;}
}

Grüße Tobi

[Salewski, Stefan (Gast)]

Tobi_tobsen schrieb:
> Hallo ich hab hier eine Übungsaufgabe zur Prüfungsvorbereitung,
> ich kann mir vorstellen das hier nicht gern geholfen wird wenn es um
> Studium etc geht.

Wohl eher Grundschule?

Auch ohne den Code wirklich anzusehen:

Pop() sollte ja wohl zuerst untersuchen, ob der Stack nicht eventuell 
leer ist.

Und Push(): Die Abfrage ob voll kommt ja eigentlich ganz zu Anfang.

Dass der Code nicht schön ist, ist Dir ja wohl klar. Wenn er sich 
kompilieren lässt, kannst Du ihn doch ausprobieren. Wenn nicht, dann 
korrigieren.

[Gs S. (gs-scarnight)]

Bei push solltest du auch vorher überprüfen ob noch Platz vorhanden ist.

Ansonsten kann ich meinem Vorredner nur zustimmen, übersetzen, testen 
und debuggen....

[Hoho (Gast)]

Das mit den geschweiften Klammern solltest Du Dir nochmals ansehen. Die 
Formatierung die Du zur Zeit hast ist schlicht nicht lesbar.

[manni (Gast)]

Hast Du es denn getestet? Wenn nicht: Warum? Ich denke, dass Du das 
Prinzip mehr oder weniger verstanden hast.
Einige Hinweise: Du solltest anz initialisieren, in Push nicht 
unnötigerweise erst 1 addieren und dann wieder subtrahieren - und auch 
vor dem Zugriff prüfen, nicht erst, wenn das Programm bereits abgestürzt 
ist ;-).
In Pop solltest Du etwas zurückgeben. Den Speicher musst Du dort nicht 
freigeben (bzw. darfst es natürlich nicht) und auch nicht den Wert auf 0 
setzen. Außerdem subtrahierst Du dort erst 1 von anz und greifst danach 
auf data[anz-1] zu.
Evtl. in Pop prüfen, ob überhaupt noch etwas vorhanden ist; allerdings 
scheint das ebenso wie die Parameterprüfung im Konstruktor nicht Teil 
der Aufgabe zu sein. In "echten" C++-Bibliotheken lässt man Checks, die 
bei jedem Zugriff ausgeführt würden, zumindest in Releaseversionen aus 
Effizienzgründen meist weg und überlässt die Verantwortung dem Benutzer 
der Klassen. Das sollte Dir aber hier kein Vorbild sein.

[manni (Gast)]

Ach ja: Woher bekommen die anderen Variablen wie maxanz ihren Wert? 
maxanz sollte auch eine Konstante sein.

[Martin S. (sirnails)]

Sind die Rechtschreibfehler im gegebenen teil von dir? Destruktoren 
werden mit ~, und nicht mit - gekennzeichnet.

[Tobi_tobsen (Gast)]

Hallo Manni,

manni schrieb:
> Hast Du es denn getestet? Wenn nicht: Warum?
Weil ich noch kein main-Programm habe und mir auch nicht zu 100% klar
ist wie ich das schreiben müsste. Das hätte dann so viele Fehler wie 
meine Implementierungsdatei, wollte erstmal wissen ob das Grundprinzip 
überhaupt richtig ist.

>Ich denke, dass Du
> das
> Prinzip mehr oder weniger verstanden hast.
vielleicht zu 60%

> Einige Hinweise: Du solltest anz initialisieren,
wo initalisieren?
>in Push nicht
> unnötigerweise erst 1 addieren und dann wieder subtrahieren
addiert hab ich 1 damit die anz stimmt, 1 habe ich wieder abgezogen da 
das Array ja bei 0 beginnt. Die abgezogene 1 wird ja aber nicht anz 
zugewiesen


> und auch
> vor dem Zugriff prüfen, nicht erst, wenn das Programm bereits abgestürzt
> ist ;-).
ok:-)
> In Pop solltest Du etwas zurückgeben.
ja aber  die Klassedekleration war vorgewgeben und sieht das doch nicht 
vor, oder wie meinst du das? Der aktuelle Stackwert kann doch über den 
Pointer auf Data abgefragt werden..?

>Den Speicher musst Du dort nicht
> freigeben (bzw. darfst es natürlich nicht) und auch nicht den Wert auf 0
> setzen.
weshalb darf ich den Wert nicht auf 0 setzen? schließlich ist das 
Element nicht mehr auf dem Stack

 Außerdem subtrahierst Du dort erst 1 von anz und greifst danach
> auf data[anz-1] zu.
hatte ich gemacht weil mein Array doch beim Indize 0 beginnt...falsch??



> Evtl. in Pop prüfen, ob überhaupt noch etwas vorhanden ist; allerdings
> scheint das ebenso wie die Parameterprüfung im Konstruktor nicht Teil
> der Aufgabe zu sein.
vielleicht sollte das mit folgender aufgabenstellung geprüft werden oder 
was könnte damit gemeint sein?:
Überlegen Sie an welchen Stellen Fehler auftreten können die sie 
erkennen können. Zum abfragen des Fehlerstatus soll das Attribut 
errorState und die
Methode GetErrorstate verwendet werden.

 In "echten" C++-Bibliotheken lässt man Checks, die
> bei jedem Zugriff ausgeführt würden, zumindest in Releaseversionen aus
> Effizienzgründen meist weg und überlässt die Verantwortung dem Benutzer
> der Klassen. Das sollte Dir aber hier kein Vorbild sein.

Danke für deine Hilfestellung!

Grüße Tobi

[Martin S. (sirnails)]

Hallo Tobi. Arrays sind immer zur Basis null und das weiß auch jeder 
Programmierer. Nur der Optik wegen würde ich da gar nichts addieren. 
Ansonsten ist anz++; die schönere Schreibweise.

Ansonsten sind memcpy und realloc deine Freunde.

[Dussel (Gast)]

Nicht so ganz ernst gemeint: Sind sonstige Einschränkungen gegeben? Wenn 
C++ verlangt ist, könnte man standardkonform auch in die Richtung gehen:

Pseudocode:

#include <stack>
stack<int> myStack;

void push(int i)
{
    mystack.push(i);
}

int pop()
{
    return mystack.pop;
}

bool isEmpty()
{
    return mystack.empty();
}
...

Man soll ja schließlich möglichst einfach programmieren und nicht immer 
das Rad neu erfinden ;-)

[manni (Gast)]

Hallo Tobi,

>> Hast Du es denn getestet? Wenn nicht: Warum?
> Weil ich noch kein main-Programm habe und mir auch nicht zu 100% klar
> ist wie ich das schreiben müsste.

Na ja, eine Instanz für jeden Test erzeugen und dann die Methoden 
aufrufen. Mal ganz einfach:

void TestSimplePushPop()
{
  Stack stack(10);
  stack.push(1);

  if(stack.pop != 1) ...
}

int main()
{
  TestSimplePushPop();
}

Sinnvolle Testszenarien musst Du Dir natürlich ausdenken. Normale 
Operationen, aber insbesondere auch mögliche Fehlerfälle.

>Das hätte dann so viele Fehler wie meine Implementierungsdatei

Das macht man auch während der Implementierung Stück für Stück, Methode 
für Methode (bei komplexeren Programmen/Bibliotheken mit Hilfe von 
Test-Frameworks).

> wollte erstmal wissen ob das Grundprinzip überhaupt richtig ist.

Ok.

>> Einige Hinweise: Du solltest anz initialisieren,
> wo initalisieren?

Stack::Stack(int size)
  : anz(0) /*, errorState(...)*/
{
  data = new int[size];
}

>>in Push nicht
>> unnötigerweise erst 1 addieren und dann wieder subtrahieren
> addiert hab ich 1 damit die anz stimmt, 1 habe ich wieder abgezogen da
> das Array ja bei 0 beginnt. Die abgezogene 1 wird ja aber nicht anz
> zugewiesen

int Stack::Push(int w)
{
  if (anz == maxanz) return 0;
  
  data[anz++] = w; // Oder 'data[anz] = w; ++anz;'

  return 1;
}

(wenn 1 ok bedeutet)

>> In Pop solltest Du etwas zurückgeben.
> ja aber  die Klassedekleration war vorgewgeben und sieht das doch nicht
> vor, oder wie meinst du das?

Ähm, "int pop (void)"? int ist der Returntyp. Das ist doch die halbe 
Miete eines Stacks.

>Der aktuelle Stackwert kann doch über den Pointer auf Data abgefragt >werden..?

Nein, nicht von außen; das sind private Daten der Klasse. push, pop, 
isEmpty und GetErrorState bilden die Schnittstelle. Dir fehlen aber 
schon ein paar Grundlagen, oder?

>>Den Speicher musst Du dort nicht
>> freigeben (bzw. darfst es natürlich nicht) und auch nicht den Wert auf 0
>> setzen.
> weshalb darf ich den Wert nicht auf 0 setzen? schließlich ist das
> Element nicht mehr auf dem Stack

Muss != darf. Das "darf" bezieht sich auf die Speicherfreigabe.

>  Außerdem subtrahierst Du dort erst 1 von anz und greifst danach
>> auf data[anz-1] zu.
> hatte ich gemacht weil mein Array doch beim Indize 0 beginnt...falsch??

Nein, das stimmt schon, aber

>>> anz=(anz-1);
>>> data[anz-1]=0;

Du greifst dort insgesamt auf data[anz-2] zu. Der "aktuelle Index" ist 
'anz-1' - es sei denn, der Stack ist gerade leer.

return data[anz--];

oder

--anz;
return data[anz];

Vorher aber besser prüfen, ob der Stack bereits leer ist.

> vielleicht sollte das mit folgender aufgabenstellung geprüft werden oder
> was könnte damit gemeint sein?:
> Überlegen Sie an welchen Stellen Fehler auftreten können die sie
> erkennen können. Zum abfragen des Fehlerstatus soll das Attribut
> errorState und die
> Methode GetErrorstate verwendet werden.

Es bedeutet, dass Du Fehlerwerte definieren musst (eigentlich sollten 
diese bereits vorgegeben sein), im Fehlerfall errorState auf den 
entsprechenden Wert setzt und in GetErrorState errorState zurückgibst.
An sich ergibt das hier keinen Sinn.
Möglichkeit 1: Du machst Du etwas "illegales" - schreibst z.B. über den 
reservierten Speicherbereich hinaus - und versuchst dann, errorState zu 
setzen. Das ist natürlich witzlos.
Möglichkeit 2: Du fängst mögliche Fehler ab. Dann ist das Objekt selbst 
aber nie in einem "Error-State", zumindest in keinem, den Du selbst 
feststellen könntest.
Es ist also wohl gemeint, dass Du für den letzten aufgetretenen 
"illegalen" Aufruf einen entsprechenden Wert in errorState ablegen 
sollst. Das ist dann aber inkonsistent, denn 'push' soll ja als 
"Erfolgsanzeige" 0 oder 1 zurückgeben. Ein Aufruf von push bei einem 
vollen Stack ist dann genau genommen kein Fehler. Also bleibt nur pop 
bei leerem Stack übrig.

Und überhaupt: Die Sache mit dem Error-State, errorstate als int, int 
statt bool bei isEmpty und push, GetErrorState groß, keine Exceptions 
(wenn schon Fehlerprüfung) etc.; das Ganze ist ein bischen merkwürdig, 
selbst wenn man die ~50 Syntaxfehler ignoriert.

[Vlad T. (vlad_tepesch)]

hier hat aber auch der Aufgabensteller nicht viel Ahnung von gutem 
Design.

Warum soll zB ein bool wert (isEmpty) durch 1 und 0 repräsentiert 
werden?

die Beschreibung von push ist komisch. Soll zurückgegeben werden, ob das 
push erfolgreich war, oder soll zurückgegeben werden, ob weiterer Platz 
da ist?

[Karl H. (kbuchegg)]

Vlad Tepesch schrieb:
> hier hat aber auch der Aufgabensteller nicht viel Ahnung von gutem
> Design.

ungeachtet dessen.
Wer soweit ist, dass er in den Themenkomplex 'dynamische 
Speicherverwaltung' vorstösst, sollte deutlich weiter in seinen 
Kenntnissen sein, als der TO.

[Vlad T. (vlad_tepesch)]

jep, das ganze sieht mir nach einem Lehrgang aus, der komplett auf dem 
Papier stattfindet aus. Die Frage ist (hoffentlich) durch eine schlechte 
OCR gewandert und die Antwort hat auch noch nie einen Compiler gesehen.

Edit:
dabei ist es so einfach:
http://codepad.org/

[Martin S. (sirnails)]

Vlad Tepesch schrieb:
> Edit:
> dabei ist es so einfach:
> http://codepad.org/

Das ist ja mal cool!

[zong (Gast)]

Das ist ja ein reiner Integerstack!
Was für ein Studienfach denn?