www.panbachi.de
Blank Navigation Blank
Home
Forum
Impressum
Downloads
Tutorials
Dokumentationen
Blank   Blank
Blank
Blank Login Blank

Passwort vergessen?
Registrieren
Blank   Blank
Blank
Blank Counter Blank
Bis jetzt kamen 506062 Besucher. Zur Zeit sind 14 User & 8 Gäste Online

33623 registrierte User

Blank   Blank
Blank
Blank
Blank   Blank
Artikel
Home » Artikel » Tutorials » C / C++ » [C++] Stack
[C++] Stack
Autor: Cefour Views: 8001
Datum: 04.09.2006 - 21:24  
Kochrezept für C++ von Michael Burzan

Wie schreibe ich ein Stack?

Erstmal die Frage was ist ein Stack?
Für die Leute die es nicht wissen, ein Stack ist eine Datenstruktur, in der man nur ein Element oben drauf legen kann und auch nur von oben wieder abnehmen kann. Der Stack ist einer der einfachsten Datenstrukturen die es gibt.

Die Üblichen Funktionen für den Stack sind push(), pop(), isempty(), clear();

Erstmal die Header:

C / C++ Code
  1.  
  2. //stack.h
  3.  
  4. class stack
  5. {
  6.     public:
  7.  
  8.         // Default Konstruktor
  9.         Stack (void);   
  10.  
  11.         // Erzeugt ein Objekt der Klasse \"stack\" von der größe \"size\"
  12.         Stack(const int size); 
  13.  
  14.         // Copy Konstruktor
  15.         Stack(const Stack &a); 
  16.  
  17.         // Destruktor
  18.         ~Stack();   
  19.  
  20.         // Legt ein Element auf dem Stack ab
  21.         void push(const double x); 
  22.  
  23.         // Nimmt das erste Element vom Stack
  24.         double pop(void);   
  25.  
  26.         // Leert den Stack
  27.         void clear(); 
  28.  
  29.         // Vergleicht ob zwei Stacks miteinander gleich sind
  30.         bool equal(Stack a); 
  31.  
  32.         // Invertiert den Stack, d.h. das unterste Element ist oben
  33.         void invert(Stack a); 
  34.  
  35.         // Wieviel ist vom Stack benutzt
  36.         int get_used(void) const;   
  37.  
  38.         // Sagt wieviel Kapazität der Stack hat
  39.         int get_capacity (void) const;     
  40.  
  41.         // Prüft ob der Stack leer ist
  42.         bool empty(void) const; 
  43.  
  44.         // Prüft ob der Stack voll ist
  45.         bool full (void) const;   
  46.  
  47.         // Gibt den Stack aus
  48.         void print(); 
  49.    
  50.         // ist eine statische Funktion die sagt:
  51.         // Wie hoch ist die Default Capcity des Stack
  52.         // wenn ich ein Stack mit dem Default Konstruktor
  53.         // schreibe
  54.         static int get_default_capacity();     
  55.          
  56.         // Setzt die Default Kapazität
  57.        static void set_default_capacity(const int dc);   
  58.  
  59.     private:
  60.  
  61.         // Initialisiert den Stack mit einer bestimmten Größe
  62.         void initialisize(const int u); 
  63.    
  64.         // Die Kapazität des Stacks
  65.         int capacity;     
  66.            
  67.                 // Benutzt
  68.                 int used; 
  69.            
  70.                 // Die Elemente des Stack
  71.                 double * content; 
  72.            
  73.                 // Den Default Wert für die Kapazität
  74.                 static int default_capacity;
  75. };
  76.  


Jetzt noch die CPP - Datei

Erstmal die Headers die man braucht.

C / C++ Code
  1.  
  2. //stack.cpp
  3.  
  4. #include \"stack.h\"
  5. #include <iostream>
  6.  


"using namespace std" deshalb, um sich ein bisschen Syntax zu sparen. Ansonsten müßte man "std::cout" schreiben

C / C++ Code
  1.  
  2. using namespace std;
  3.  


Das ist ein Konstruktor wenn man ein Objekt der Klasse anleget. Er wird z.B "Stack stack;" aufgerufen. In der Funktion selber wird die private Funktion "initialisize" aufgerufen die einen statischen Wert namens "default_capacity" hat.

C / C++ Code
  1.  
  2. Stack::Stack()
  3. {
  4.     initialisize(default_capacity);
  5. }
  6.  


Ein Weitere Konstruktor der einen Stack mit einer userspezifischen Größe anlegt. "const int size" deshalb umzu verhindern das der Wert von "size" geändert wird.

C / C++ Code
  1.  
  2. Stack::Stack(const int size)
  3. {
  4.     initialisize(size);
  5. }
  6.  



Zitat von wikipedia
Der Kopierkonstruktor ist ein spezieller Konstruktor, der eine Referenz auf ein Objekt des selben Typs als Parameter entgegennimmt und die Aufgabe hat, eine Kopie des Objektes zu erstellen.

z.B

C / C++ Code
  1.  
  2. get_stack()
  3. {
  4.     Stack stack(20);
  5.  
  6.     // Aufruf des Kopie Konstruktor
  7.     return stack;
  8. }
  9.  
  10. Stack::Stack(const Stack &a)
  11. {
  12.     initialisize(a.get_used());
  13.     for(int i = 0; i < a.get_used(); i++)
  14.     {
  15.         push(a.content[i]);
  16.     }
  17. }
  18.  



Destruktor dieser wird aufgerufen um einen Stack zu zerstören. Dies macht die Laufzeitumgebung
automatisch. Den Destruktor muss man also nicht Explicit aufrufen.
Er gibt einfach mittels delete den Speicher wieder frei

C / C++ Code
  1.  
  2. Stack::~Stack()
  3. {
  4.     delete [] content;
  5. }
  6.  



Gibt ein Wert in den Stack rein.
Er überprüft ob der Stack voll ist, falls das so ist bricht er ab. An dieser Stelle sollte
man eigentlich eine Exception fahren, dies kommt in späteren Tutorials.
Dann übergibt er in das Array content an der Position used den Wert von x.
used ist eine private Membervariable. Normalerweise hat man keinen Zugriff drauf,
da aber die Funktion push() Mitglied der Klasse ist, kann man auf used zugreifen.

Als letzten Schritt muss man used um eine position nach oben rechnen.
Damit der nächste Wert der eingefügt wird an der richtigen Stelle ist.

C / C++ Code
  1.  
  2. void Stack::push(const double x)
  3. {
  4.     if (full())   
  5.         return;
  6.  
  7.     content[used] = x;
  8.     used ++;
  9. }
  10.  



Hollt einen Wert aus dem Stack heraus.
Er überprüft ob der Stack leer ist, falls das so ist gibt er einen Fehlercode
-100 raus. Dies sollte man auch mit einer Exception abfangen.
Erst rechnet er von used eins runter damit man den letzten Wert im Array content bekommt.

C / C++ Code
  1.  
  2. double Stack::pop(void)
  3. {
  4.     double stack_element; 
  5.    
  6.     if(empty())
  7.         return -100;
  8.  
  9.     used--;
  10.     stack_element = content[used];
  11.  
  12.     return stack_element;
  13. }
  14.  



Damit der Stack sauber gemacht wird ist nichts weiter nötig als used einfach auf 0
zu setzen. Somit überschreibt der Stack alle Werte die mit push() eingefügt werden.

C / C++ Code
  1.  
  2. void Stack::clear()
  3. {
  4.     used = 0;
  5. }
  6.  


Überprüft ob zwei Stacks gleich sind
z.b so ein Aufruf:

C / C++ Code
  1. b.equal(a);



Diese Funktion vergleicht die capacity vom den Stack a und die capacity vom Stack b und
vergleicht gleichzeitig ob used von a genau so groß ist wie used von b.
Falls das wahr ist geht er in die innere Scheife wo er jetzt jedes Element überprüft.

C / C++ Code
  1.  
  2. bool Stack::equal(Stack a)
  3. {
  4.     bool result;       
  5.     if((a.get_capacity() == capacity) && ( a.get_used() == used))
  6.     {
  7.         for(int i = 0; i < used; i++ )
  8.         {
  9.             if (a.content[i] == content[i])
  10.             {
  11.                 result  = true;
  12.             }   
  13.             else
  14.             {
  15.                 return false;
  16.             }
  17.         }
  18.     }
  19.     else
  20.     {
  21.         return false;
  22.     }
  23.     return result;
  24. }
  25.  



Dreht einen Stack um. Das letzte Element ist das erste und das erste Element ist das letzte.
Die Funktion geht solange durch den Stack a, bis er leer ist.
Dabei pusht die Funktion einen Wert von a in den neuen Stack hinein.

C / C++ Code
  1.  
  2. void Stack::invert(Stack a)
  3. {
  4.     while(!a.empty())   
  5.         push(a.pop());
  6. }
  7.  



Gibt used zurück.

C / C++ Code
  1.  
  2. int Stack::get_used(void) const
  3. {   
  4.     return used;
  5. }
  6.  



Gibt capacity zurück.

C / C++ Code
  1.  
  2. int Stack::get_capacity(void) const
  3. {
  4.     return capacity;
  5. }
  6.  



Prüft ob der Stack leer ist.

C / C++ Code
  1.  
  2. bool Stack::empty() const
  3. {
  4.     if (used == 0)       
  5.         return true;
  6.     else
  7.         return false;
  8. }
  9.  



Prüft ob der Stack voll ist.

C / C++ Code
  1.  
  2. bool Stack::full() const
  3. {
  4.     if (used == capacity)
  5.         return true;
  6.     else
  7.         return false;
  8. }
  9.  



Gibt den Stack aus

C / C++ Code
  1.  
  2. void Stack::print()
  3. {
  4.     for (int i = 0; i < used; i++)
  5.     {
  6.         cout<<\" \"<<content[i];
  7.         cout<<\"\\n\";
  8.     }
  9. }



Gibt die default_capacity.

C / C++ Code
  1.  
  2. int Stack::get_default_capacity()
  3. {
  4.   return default_capacity;
  5. }
  6.  



Setzt default_capacity auf den Wert von db.

C / C++ Code
  1.  
  2. void Stack::set_default_capacity(const int dc)
  3. {
  4.     default_capacity = dc;
  5. }
  6.  



Initialisiert den Stack mit der Größe u.

C / C++ Code
  1.  
  2. void Stack::initialisize(const int u)
  3. {
  4.     content = new double[u];   
  5.     capacity = u;
  6.     used = 0;
  7. }
  8.  



Statische Variable die ausserhalb der Klasse initialisiert werden muss.
Dieser Wert ist für alle Objekte der Klasse gleich.
Wenn man diesen Wert ändert werden auch alle Objekte geändert die Angelegt worden sind.

C / C++ Code
  1.  
  2. int Stack::default_capacity = 10;
  3.  


Somit ist der Stack fertig. Eine kleine Datenstruktur für viele Anwendungen,
wie z.B Ein Taschenrechner Programm, der Ausdrücke in der Art rechnen soll:

2 +3 +4 *7

Das ginge jetzt kein Problem!!!

Fragen zum Stack einfach in das C / C++ Forum posten.

Zum Schluss nocheinmal der ganze CPP Code:

C / C++ Code
  1.  
  2. //stack.cpp
  3.  
  4. #include \"stack.h\"
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. Stack::Stack()
  10. {
  11.     initialisize(default_capacity);
  12. }
  13.  
  14. Stack::Stack(const int size)
  15. {
  16.     initialisize(size);
  17. }
  18.  
  19. Stack::~Stack()
  20. {
  21.     delete [] content;
  22. }
  23.  
  24. void Stack::push(const double x)
  25. {
  26.     if (full())   
  27.         return;
  28.  
  29.     content[used] = x;
  30.     used ++;
  31. }
  32.  
  33. double Stack::pop(void)
  34. {
  35.     double stack_element; 
  36.    
  37.     if(empty())
  38.         return -100;
  39.  
  40.     used--;
  41.     stack_element = content[used];
  42.  
  43.     return stack_element;
  44. }
  45.  
  46. void Stack::clear()
  47. {
  48.     used = 0;
  49. }
  50.  
  51. bool Stack::equal(Stack a)
  52. {
  53.     bool result;       
  54.     if((a.get_capacity() == capacity) && ( a.get_used() == used))
  55.     {
  56.         for(int i = 0; i < used; i++ )
  57.         {
  58.             if (a.content[i] == content[i])
  59.             {
  60.                 result  = true;
  61.             }   
  62.             else
  63.             {
  64.                 return false;
  65.             }
  66.         }
  67.     }
  68.     else
  69.     {
  70.         return false;
  71.     }
  72.     return result;
  73. }
  74.  
  75. void Stack::invert(Stack a)
  76. {
  77.     while(!a.empty())   
  78.         push(a.pop());
  79. }
  80.  
  81. int Stack::get_used(void) const
  82. {   
  83.     return used;
  84. }
  85.  
  86. int Stack::get_capacity(void) const
  87. {
  88.     return capacity;
  89. }
  90.  
  91. bool Stack::empty() const
  92. {
  93.     if (used == 0)       
  94.         return true;
  95.     else
  96.         return false;
  97. }
  98.  
  99. bool Stack::full() const
  100. {
  101.     if (used == capacity)
  102.         return true;
  103.     else
  104.         return false;
  105. }
  106.  
  107. void Stack::print()
  108. {
  109.     for (int i = 0; i < used; i++)
  110.     {
  111.         cout<<\" \"<<content[i];
  112.         cout<<\"\\n\";
  113.     }
  114. }
  116. int Stack::get_default_capacity()
  117. {
  118.   return default_capacity;
  119. }
  121. void Stack::set_default_capacity(const int dc)
  122. {
  123.     default_capacity = dc;
  124. }
  126. void Stack::initialisize(const int u)
  127. {
  128.     content = new double[u];   
  129.     capacity = u;
  130.     used = 0;
  131. }
  133. int Stack::default_capacity = 10;


Autor: Michael Burzan
Blank   Blank
Blank Spenden Blank
Blank   Blank
Blank
Blank Werbung Blank
Blank   Blank
Blank
Blank


Coder Forum