L3_3.1 Dynamische Datenstrukturen: Warteschlange (Queue)
| Am Flughafen gibt es einen Taxistand mit zehn Stellplätzen. Ankommende Taxis stellen sich in einer Schlange an. Im Taxistand kann nicht gewendet werden. Deswegen kann immer nur das vorderste Taxi Fahrgäste aufnehmen und abfahren. Das folgende Schaubild soll den Sachverhalt verdeutlichen. |  |
Ankommende Taxis werden von einem elektronischen Erfassungssystem mit der Taxinummer erfasst. Verlässt ein Taxi den Taxistand wird dies ebenfalls erfasst. Ihnen liegen folgende Daten vor:
|
Hinweis: Kommen mehrere Taxis zur gleichen Zeit an (vgl. 14:01 Uhr), sind sie in der Tabelle nach ihrer Ankunft aufgelistet (T254 vor T255). |
|---|
1.1 Aus der Auflistung wird ersichtlich, dass im automatischen Erfassungssystem ein Fehler sein muss. Beschreiben Sie diesen Fehler.
Sie erhalten neue Daten vom 01.08. aus dem automatischen Erfassungssystem.
|
|
|---|
1.2 Wie viele Taxis befanden sich vor der Einfahrt des Taxis T021 im Taxistand?
1.3Welche Taxis befinden sich in welcher Reihenfolge um 08:22 Uhr im Taxistand? Vervollständigen Sie zur Beantwortung der Frage die folgende Tabelle.
| 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 08:00 | ||||||||||
1.4 Um 08:01 Uhr kommt Sandra Meier am Taxistand an. Es warten keine Fahrgäste auf ein Taxi. Sandra Meier möchte aber ausschließlich mit dem Taxi T021 fahren. Wann ist Sandra Meier abgefahren und wie viele Fahrgäste hat sie vorgelassen?
1.5 In der Zeit von 08:30 bis 09:00 arbeitete das automatische Erfassungssystem fehlerhaft. Es wurden zwar die Uhrzeiten und die Taxinummern erfasst, jedoch nicht, ob es sich um eine Ausfahrt oder Einfahrt handelte.
Vervollständigen Sie die nachfolgenden Lücken unter Beachtung der dynamischen Datenstruktur Warteschlange.
|
|
|---|
2 Taxistand - Teil 2
Aufgrund einiger Unstimmigkeiten der Fahrgäste bei der Taxivergabe hat der Flughafen neben dem Taxistand auch eine Wartelinie für Fahrgäste eingerichtet (P1 – P20).
Als zusätzliche Information können zukünftig die Sitzplätze eines Taxis gespeichert werden. So hat das Taxi T432.3 bspw. 3 Sitzplätze, das Taxi T009.6 hat 6 Sitzplätze. Außerdem muss auch die Anzahl der zusammengehörigen Fahrgäste (= Fahrgastgruppe) beachtet werden. So hat die Fahrgastgruppe F1.2 beispielsweise 2 Personen und die Fahrgastgruppe F2.8 sogar 8 Personen.
|
|
|---|
In diesem Beispiel kommt um 08:00 das Taxi T021.5 an. Um 08:01 kommen die Fahrgastgruppen F1 mit drei Personen und die Fahrgastgruppe F2 mit zwei Personen. Die Fahrgastgruppe F1.3 kann direkt abfahren, sodass um 08:02 nur noch die Fahrgastgruppe F2.2 auf ein Taxi wartet. Folglich können mehrere Fahrgastgruppen nicht mit einem Taxi fahren (z. B. aufgrund unterschiedlicher Fahrtziele).
Eine Fahrgastgruppe kann sich dagegen auf zwei oder mehrere Taxis verteilen.
Die nachfolgende Tabelle verdeutlicht den Sachverhalt.
| Taxi | ... | 5 | 4 | 3 | 2 | 1 | ||||||
| Person | ... | ... | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| 08:00 | ... | T021.5 | ||||||||||
| ... | ... | |||||||||||
| 08:01 | ... | T021.5 | ||||||||||
| ... | ... | F2.2 | F2.2 | F1.3 | F1.3 | F1.3 | ||||||
| 08:02 | ... | |||||||||||
| ... | ... | F2.2 | F2.2 | |||||||||
Sie erhalten aus dem automatischen Erfassungssystem neue Daten vom 02.08.
|
|
|---|
2.1 Vervollständigen Sie die nachfolgende Tabelle mit den Plätzen im Taxistand und der Warteschlange für die Fahrgastgruppen. Beachten Sie die Regeln für die dynamische Datenstruktur Warteschlange.
| 08:00 | ||||||||||||||
2.2 Wie viele Taxis und wie viele Fahrgäste sind um 08:06 Uhr im Taxistand?
2.3 Ermitteln Sie die Fahrgastzahl des Taxis T010.6, wenn es um 08:13 Uhr den Taxistand verlässt.
2.4 Wie viele Fahrgäste können mindestens und höchstens bis 08:30 Uhr abfahren, wenn kein weiteres Taxi mehr kommt?