Stack
Folgendes Programm in C:
#include <stdio.h>
int collatz(int);
int even(int n) {
return 1 + collatz(n/2);
}
int odd(int n) {
return 1 + collatz(3*n + 1);
}
int collatz(int n) {
if (n == 1) {
return 0;
} else if (n % 2 == 0) {
return even(n);
} else {
return odd(n);
}
}
int main() {
int n = collatz(837799);
printf("%d\n", n);
}
Das Programm besteht aus mehreren Funktionen, die sich gegenseitig aufrufen.
Wenn jetzt eine Funktion aufgerufen wird, woher weiß das Programm
- welche Argumente an die Funktion übergeben wurden
- an welcher Stelle es bei einem return die Verarbeitung fortsetzen soll,
- welche Werte die lokalen Variablen hatten, unmittelbar bevor die Funktion aufgerufen wurde?
Das alles wird auf einem sogenannten Aufrufstapel (engl. call stack) gespeichert. Jeder Funktionsaufruf erzeugt einen neuen Eintrag auf dem Aufrufstapel. Jedes return, das ausgeführt wird, entfernt den obersten Eintrag vom Aufrufstapel.
Den Code für die Verwaltung der Aufrufstapels sieht man nicht, weil er während der Übersetzung des Quelltextes in Maschinencode vom Übersetzer automatisch eingefügt wird.
Wie dieser Code im Detail aussieht, kann bei verschiedenen Übersetzern unterschiedlich sein. Deshalb kann es vorkommen, dass eine Bibliothek, die mit einem bestimmten Übersetzer übersetzt wurde, nicht von einem Programm verwendet werden kann, das mit einem anderen Übersetzer übersetzt wurde. Die Details, wie der Aufrufstapel verwaltet wird, ist in einer sogenannten Aufrufkonvention (engl. calling convention) geregelt.
Queue
Ein Drucker ist an einen Rechner A angeschlossen. Der Rechner A ist an ein Netzwerk angeschlossen. Der Rechner A erlaubt anderen Rechnern des Netzwerks, den Drucker zu benutzen. Rechner A nennt man in diesem Zusammenhang einen Druckerserver. Er muss sicherstellen, dass Druckauftäge auch dann angenommen werden können, wenn der Drucker gerade druckt. Dazu packt er ankommende Druckauftäge in eine Warteschlange und wenn der Drucker mit seinem aktuellen Druckauftrag fertig ist entnimmt der Druckerserver den ältesten Druckauftrag und sendet ihn an den Drucker.
Listen
Ich weiß nicht genau, was damit gemeint ist.
Was wird mithilfe eines abstrakten Datentypen beschrieben?
Es werden Daten beschrieben und es werden Operationen beschrieben, die auf diese Daten zugreifen.
