Einfacher Stack: in C++ und im C-Stil
Einfachheitshalber betrachten wir eine C++ Implementierung für einen Stack mit folgenden Eigenschaften:
-
Default-Constructor (legt einen leeren Stack an)
-
Destruktor (räumt einen Stack auf)
-
Empty-Methode (überprüft, ob der Stack leer ist)
-
Push-Methode (legt neues Element auf den Stack)
-
Pop-Methode (entfernt das oberste Element vom Stack)
-
Print-Methode (gibt den Stack aus)
Was offensichtlich für eine richtige Implementierung noch fehlt sind:
-
Copy-Constructor und Zuweisungsoperator
-
Constructor für eine R-Value-Referenz
Ein einfaches Test-Programm für diese Implementierung sieht zum Beispiel so aus:
int main()
{
Stack stack;
stack.push(1.3);
stack.push(3.5);
stack.push(-2);
stack.print("stack");
std::cout << "pop: " << stack.pop() << std::endl;
stack.print("stack");
std::cout << "pop: " << stack.pop() << std::endl;
stack.print("stack");
std::cout << "pop: " << stack.pop() << std::endl;
stack.print("stack");
}
Um genauer verstehen zu können, welche Arbeit der C++-Compiler leistet, vergleichen wir die Stack-Implementierung mit einer Implementierung im C-Stil. Wir benutzen dabei zwar einige C++-Features aber im wesentlichen könnte diese auch in reinem ANSI-C geschrieben sein. Hier sieht das Testprogramm dann so aus:
int main()
{
Stack stack;
stack_construct_default(&stack);
stack_push(&stack, 1.3);
stack_push(&stack, 3.5);
stack_push(&stack, -2);
stack_print(&stack, "stack");
std::cout << "pop: " << stack_pop(&stack) << std::endl;
stack_print(&stack, "stack");
std::cout << "pop: " << stack_pop(&stack) << std::endl;
stack_print(&stack, "stack");
std::cout << "pop: " << stack_pop(&stack) << std::endl;
stack_print(&stack, "stack");
stack_destruct(&stack);
}
Die C++ Implementierung
#define CPP_STACK_HPP 1
#include <cassert>
#include <iostream>
class Stack
{
public:
Stack()
: top(nullptr)
{
}
~Stack()
{
while(!empty()) {
pop();
}
}
bool empty() const
{
return !top;
}
void push(double value)
{
Element *add = new Element;
add->last = top;
add->value = value;
top = add;
}
double pop()
{
assert(!empty());
Element *remove = top;
top = remove->last;
double value = remove->value;
delete remove;
return value;
}
void print(const char *txt) const
{
std::cout << txt << ": ";
print_elements(top);
std::cout << ";" << std::endl;
}
private:
struct Element
{
double value;
Element *last;
};
void print_elements(const Element *top) const
{
if (top) {
print_elements(top->last);
std::cout << " " << top->value;
}
}
Element *top;
};
#endif // CPP_STACK_HPP
Regeln: Von C++ nach C-Stil
-
Aus class wird stets struct
-
Aus einem Constructor, einer Methode und dem Destructor werden jeweils Funktionen
-
Beim Namen der Funktion wird dabei der Name der Klasse als Prefix verpasst. Wir fügen zusätzlich noch einen Unterstrich dazu. Aus der Methode print der Klasse Stack wird so die Funktion stack_print.
-
Das erste Argument einer dieser Funktionen ist stets ein Zeiger namens this_ auf das Objekt. Dass hier this_ statt this vereinbart wird ist notwendig, da this in C++ ein Schlüsselwort ist.
-
Innerhalb einer Methode darf der Wert von this_ nicht verändert werden. Damit soll nachempfunden werden, dass in C++ auch this nicht verändert wird.
-
War die Methode als const deklariert, dann wird ist this_ ein Const-Pointer auf das Objekt.
-
War eine Methode oder Attribut als private deklariert, dann wird bei der Namensgebung ein Unterstrich als Suffix angehängt. Es ist jetzt eine reine Vereinbarung, dass nur innerhalb der Implementierung so gekennzeichnete Funktionen und Attribute verwendet werden dürfen.
-
Aus geschachtelten Klassen werden eigenständige Klassen. Der Name der ursprünglich übergeordneten Klasse wird wieder als Prefix angefügt. Aus der C++ Klasse Stack::Element wird beispielsweise Stack_Element.
-
Die C-Stil Implementierung
#define C_STYLE_STACK_HPP 1
#include <cassert>
#include <iostream>
struct Stack_Element
{
double value;
Stack_Element *last;
};
struct Stack
{
Stack_Element *top_;
};
void stack_construct_default(Stack * const this_)
{
this_->top_ = nullptr;
}
bool stack_empty(const Stack * const this_)
{
return !(this_->top_);
}
void stack_push(Stack * const this_, double value)
{
Stack_Element *add = new Stack_Element;
add->last = this_->top_;
add->value = value;
this_->top_ = add;
}
double stack_pop(Stack * const this_)
{
assert(!stack_empty(this_));
Stack_Element *remove = this_->top_;
this_->top_ = remove->last;
double value = remove->value;
delete remove;
return value;
}
void stack_destruct(Stack * const this_)
{
while (!stack_empty(this_)) {
stack_pop(this_);
}
}
void stack_print_elements_(const Stack * const this_, const Stack_Element *top)
{
if (top) {
stack_print_elements_(this_, top->last);
std::cout << " " << top->value;
}
}
void stack_print(const Stack * const this_, const char *txt)
{
std::cout << txt << ": ";
stack_print_elements_(this_, this_->top_);
std::cout << ";" << std::endl;
}
#endif // C_STYLE_STACK_HPP