Eine Queue selber bauen
Vorwort:
Das hier ist mein erstes Tutorial, also entschuldige ich mich schon jetzt für eventuelle Anfängerfehler beim "Tutorieren".
Dieses Tutorial richtet sich an Leute, denen C++ kein Fremdwort mehr ist und schon etwas mehr Erfahrung damit gemacht haben.
Weiterhin sollte die Template-Programmierung geläufig sein, denn die Queue, die ich hier erkläre, soll für alle Typen funktionieren.
Inhalt:
1) Was ist eine Queue?
2) Wie kann man sich eine Queue vorstellen?
3) Was muss eine Queue können?
4) Wie implementiere ich solch eine Queue?
5) Wie verwende ich die Queue jetzt?
1) Was ist eine Queue?
Eine Queue ist eine Art "Warteschlange", in der verschiedene Informationen darauf warten, abgefragt zu werden.
Man benutzt eine Queue um beispielsweise für Nachrichten an Fenster, in der WinAPI.
Oder zur Kommunikation zwischen Threads: Ein Hauptthread der alles steuert und ein Nebenthread, der Texturen, etc. nachlädt.
Dort werden dann die Texturnamen und zu füllenden Schnittstellen gespeichert, und aus diesen Informationen lädt der Nebenthread dann die Texturen.
2) Wie kann man sich eine Queue vorstellen?
Eine Queue kann man sich wie ein Rohr vorstellen, bei dem an einem Ende ein hungriges Kind sitzt, das Zuckerwürfel haben will,
und am anderen Ende sitzt der Vater, der fleißig Zuckerwürfel nachschiebt. Die Zuckerwürfel rutschen dann in der Reihenfolge,
in der sie hineingesteckt wurden, wieder heraus.
Ungefähr so:
|
Quellcode
|
1
2
3
|
,----------------Das-ist-die-Queue---------------------
Kind[A]{ [B] [C] [D] [E] [F] Vater
'------------------------------------------------------
|
Die Buchstabenreihenfolge, ist die Reihenfolge in der die Würfel ankommen:
[ A ] ist schon angekommen, also nicht mehr in der Queue.
[ F ] kommt noch in die Queue.
Der Rest ist mittendrin.
Das ist eigentlich die einfache "Standard-Queue".
Es gibt aber auch Queues bei denen es möglich ist auch noch etwas an der Anfang zu schieben, dabei kann der Zuckerwürfel entweder
am Ende (wie oben) ODER an den Anfang, also zwischen Kind und erstem kommenden Zuckerwürfel, geschoben werden.
So in etwa sieht das aus:
|
|
Quellcode
|
1
2
3
4
5
6
|
----------------------------------
/ [B]
/ ---------------------------------_
,/ /---------------------------------" [F] Vater
Kind[A]{ [C] [D] [E]
'--------------------------------------
|
[ A ] und [ F ] sind wie ober nicht in der Queue
[ C ], [ D ] und [ E ] wurden zwar eher als [ B ] reingesetzt, aber [ B ] hat vorrang, denn es kommt an den Anfang!
Solche Queues benutze ich öfters, zum Beispiel bei Netzwerkspielen, etc. . Dabei können wichtige Nachrichten, wie "Der Spieler hat die Verbindug verloren!",
schnell nach vorn gesetzt werden, um darauf zu reagieren und das Problem zu lösen. Die restlichen Daten, wie Positionen, warten dann bis das Problem geslöst wurde.
Es gibt auch Priotity-Queues, bei denen jeder "Zuckerwürfel" noch eine Prioritätsstufe bekommt, und dann der Platz in der Queue gesucht wird,
zwischen denen die Priorität des Neuen liegt:
|
|
Quellcode
|
1
2
3
|
.- [C 2]
/
[A 1] <-" [B 3]
|
2 liegt zwischen 1 und 3 also kommt [C 2] genau dazwischen.
Dies ermöglicht eine genauere Abgrenzung, als bei der 2. Version.
Diese Art von Queues ist IMHO eher ungebräuchlich (zumindest bei mir).
3) Was muss eine Queue können?
Die Queue, die ich vorstellen werde, entspricht der 2. Version:
o Die Queue wird ein Template, das heißt jeder Type, ob int oder eigene Klassen, können gespeichert werden.
o Die, Daten die in die Queue geschickt werden, werden als Kopie gespeichert.
o Man kann Daten vorn und hinten reinsetzen, das bedeutet, dass wichtige Daten Vorrang bekommen können.
o Man kann nur von einer Seite lesen, das ist normal.
Eine Queue, die von beiden Seiten lesbar ist, ist eher ungebräuchlich, und verkompliziert die Sache nur unnötig.
4) Wie implementiere ich solch eine Queue?
Die Codes stammen aus meiner Engine, deshalb das "GT". Es wird aber alles implementiert, was zur Engine gehört. Die Engine selbst wird hier nicht benötigt.
Also am Anfang ist es ratsam für die Queue eine separate Header-Datei zu erstellen. Ich nenne sie "GTQueue.h" (sehr einfallsreich
)
An den Anfang kommen Guards:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
|
#if defined _MSC_VER && _MSC_VER >= 1020
#pragma once
#endif
#ifndef _GT_QUEUE_
#define _GT_QUEUE_
//Hierhin kommt die Queue
#endif
|
Zu Sicherheit wird doppelt geschützt (pragma für VC++ und für alle anderen gibt's defines)
Der Teil meiner Engine kommt am besten direkt nach den Guards
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
|
#define GTSafeDelete(Pointer) { delete(Pointer); (Pointer)=NULL; }
enum GTResult
{
GT_OK,
GT_ZERO_POINTER,
GT_INVALID_VALUE
};
|
GTSafeDelete ist ein Makro, um Speicher sicher freizugeben, und GTResult stellt Rückgabewerte dar.
Statt GTResult kann natürlich auch int oder ein eigener Type verwendet werden. So ein Makro wie GTSafeDelete sollte nirgends fehlen.
Kommen wir nun zur eigentlichen Queue, nachdem alle Vorbereitungen getroffen wurden.
Die Queue soll alle möglichen Daten speichern können, also nehme ich template.
Jede Queue kann aber nur einen Typ speichern!
|
|
C-/C++-Quelltext
|
1
2
3
4
|
template<class T>
class GTQueue
{
};
|
Hier müssen noch irgendwie die einzelnen Elemente gespeichert werden.
Diese enthalten Informationen über vorherige Nachricht, folgende Nachricht, und natürlich der eigentliche Wert.
Im Prinzip wird eine also doppelt verkettete Liste erstellt.
darum sieht die Klasse jetzt so aus
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
template<class T>
class GTQueue
{
public:
//Eintrag in die Queue, ähnlich wie eine doppelt verkettete Liste
struct SElement
{
SElement *pLast, //Pointer auf vor und danach
*pNext;
T Value; //Der eigentliche Wert
//Kopierkonstruktoren
SElement(T _Value, SElement *_pLast, SElement *_pNext)
: Value(_Value), pLast(_pLast), pNext(_pNext) {}
SElement(SElement &Element)
: Value(Element.Value), pLast(Element.pLast), pNext(Element.pNext) {}
};
};
|
Value ...speichert eine Kopie des Wertes, der in die Queue kommt (z.B. ein Nachricht)
pLast ...speichert einen Pointer auf das vorhergehende Element der Queue
pNext ...speichert einen Pointer auf der nächste Element der Queue
Der Anfang, das Ende, und Die Anzahl der Nachrichten müssen auch noch gespeichert werden
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
template<class T>
class GTQueue
{
public:
//Eintrag in die Queue, ähnlich wie eine doppelt verkettete Liste
struct SElement
{
SElement *pLast, //Pointer auf vor und danach
*pNext;
T Value; //Der eigentliche Wert
//Kopierkonstruktoren
SElement(T _Value, SElement *_pLast, SElement *_pNext)
: Value(_Value), pLast(_pLast), pNext(_pNext) {}
SElement(SElement &Element)
: Value(Element.Value), pLast(Element.pLast), pNext(Element.pNext) {}
};
private:
SElement *m_pFirst, //Verwaltung
*m_pLast;
int m_iElementsCnt;
};
|
m_pFirst ...speichert einen Pointer auf das erste Element der Queuekommt
m_pLast ...speichert einen Pointer auf das letzte Element der Queue
m_iElementsCnt ...speichert die Anzahl der Element, die noch in der Queue warten
Jetzt haben wir fast eine Queue, nur eins fehlt noch: Die Funktionen!
Also was brauchen wir alles?
1. eine Funktion, die die gesamte Queue mit einem mal leeren kann. ->
Delete
2. Den Destuktor der Delete aufruft, wenn noch Elemente in der Queue sind. ->
~GTQueue
3. einen Konstruktor, der schon am Anfang aufräumt, also m_iElementsCnt auf 0 setzt, usw. um Fehler zu vermeiden. ->
GTQueue
4. Eine Funktion um der Queue ein Element hinzuzufügen ->
Add
5. Das selbe, nur wird das Element diesmal ganz vorn hingeschrieben ->
AddBefore
6. Eine Funktion, die das nächste Element zurückliefert und aus der Queue entfernt, sprich die Nachricht zur Verarbeitung freigibt,
und als verabreitet abstempelt (also aus Queue entfernen) ->
Get
7. Eine Funktion, die das nächste Element liefert, aber noch nicht löscht, also in der Queue lässt ->
Peek
8. Wenn ein Element ge"Peek"t wurde, aber vieleicht veraltet ist, muss es gelöscht werden, denn es steht immernoch in der Queue ->
Destroy
Das ganze sieht jetzt so aus
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
//Eine "Warteschlange" für zum Beispiel Nachrichten,
//die nacheinander abgearbeitet werden müssen
//Es wird eine Kopie angelegt
template<class T>
class GTQueue
{
public:
//Eintrag in die Queue, ähnlich wie eine doppelt verkettete Liste
struct SElement
{
SElement *pLast, //Pointer auf vor und danach
*pNext;
T Value; //Der eigentliche Wert
//Kopierkonstruktoren
SElement(T _Value, SElement *_pLast, SElement *_pNext)
: Value(_Value), pLast(_pLast), pNext(_pNext) {}
SElement(SElement &Element)
: Value(Element.Value), pLast(Element.pLast), pNext(Element.pNext) {}
};
private:
SElement *m_pFirst, //Verwaltung
*m_pLast;
int m_iElementsCnt;
public:
//Konstruktor und Destruktor zum aufräumen
GTQueue(void) : m_pFirst(NULL), m_pLast(NULL), m_iElementsCnt(0) {}
~GTQueue(void);
void Delete(void); //aufräumen
int GetElementsCnt(void) const { return(m_iElementsCnt); } //selbsterklärend
//Queue bearbeiten
void Add(const T &); //Ganz normal ans Ende stellen
void AddBefore(const T &); //Ganz vorn ran stellen
GTResult Get(T *pToFill); //Nächstes Element raussuchen, in der Variable, deren Pointer übergeben wurde speichern, und aus Liste entfernen
GTResult Peek(T *pToFill) const; //Mal sehen was kommt
void Destroy(void); //Nächstes Element löschen (wenn's z.B. ungültig ist)
};
|
Bei
Get und
Peek wird ein Pointer auf eine Variable übergeben. Darin wird dann der Wert der in der Queue wartet gespeichert.
Es gibt noch eine Methode:
GetElementsCnt, die aber nur die Anzahl der Elemente (zB Nachrichten) zurückgibt.
Damit kann man ungefähr schätzen, ob sich zu viel anstaut und etwas beschleunigt werden muss, oder ganz einfach nur als Info.
Kommen wir nun zu den einzelnen Funktionen.
1) der Destruktor:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
|
template<class T>
GTQueue<T>::~GTQueue()
{
if(m_iElementsCnt) //Bei Bedarf leeren
Delete();
m_pFirst=NULL; //Zurücksetzen
m_pLast=NULL;
m_iElementsCnt=0;
}
|
Wenn also noch Elemente vorhanden sind, dann hat m_iElementsCnt einen logisch wahren Wert, ansonsten ist es logisch falsch.
Darum ist ein m_iElementsCnt!=0 unnötig. Ansonsten werden noch alle Member zurückgesetzt.
2) der Konstukror: ist direkt in der Klasse definiert, und macht nichts als alles zurückzusetzen.
3) Delete:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
template<class T> //Alles aufräumen
void GTQueue<T>::Delete(void)
{
//Liste leeren
if(m_iElementsCnt) //Liste ist gefüllt
{
if(m_iElementsCnt==1) //Nur ein Element
GTSafeDelete(m_pFirst)
else
for(SElement* pCurrent=NULL;
pCurrent!=m_pLast;) //Bis zum letzten Eintrag gehen
{
pCurrent= m_pFirst; //immer weiter gehen
m_pFirst= m_pFirst->pNext;
delete(pCurrent); //und löschen
}
}
m_pFirst=NULL; //Zurücksetzen
m_pLast=NULL;
m_iElementsCnt=0;
}
|
Hier sieht das schon etwas schwieriger aus.
Als erstes wird geprüft, ob überhaupt etwas in der Queue ist.
Wenn das der Fall ist, wird bei einem einzigen Element nur der Speicher freigegeben und dann der Rest zurückgesetzt, wie es der Konstruktor auch macht.
Wenn also noch viele Elemente drinstehen, wird die doppelte Verkettung ausgenutzt:
Das 2. Element wird als "offizieller" Start erklärt, somit ist das Erste aus der Queue raus, aber noch nicht aus dem Speicher.
Deshalb wird der Speicher per sicherem delete wieder freigegeben. Die Adresse wird durch doppelte Verkettung im jetztigen Start gespeichert.
Auf diese Weise wird der Start der Queue immer weiter nach hinten gerückt, bis alle Elemente freigegeben sind.
4) Add:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
template<class T>
void GTQueue<T>::Add(const T & Value)
{
if(!m_iElementsCnt) //Liste ist leer
{
//Neues Element erstellen und Zähler hochsetzen
SElement *pNew=new SElement(Value,NULL,NULL);
m_pFirst=m_pLast=pNew;
m_iElementsCnt=1;
return;
}
//Neues Element erstellen, letztes "linken" und Zähler hochsetzen
SElement *pNew=new SElement(Value,m_pLast,NULL);
m_pLast->pNext=pNew;
m_pLast=pNew;
m_iElementsCnt+=1;
}
|
Add erhält einen Wert, von dem eine Kopie angelegt werden soll.
Hierbei wird unterschieden ob es der alleserste Wert ist, oder irgendein anderer.
In beiden Fällen muss erstmal ein neues Element für die Queue geschaffen werden: per new und Konstruktor von SElement.
Hier wird der Wert kopiert. Der Anfang und das Ende der Queue ist hier ein und der selbe Wert. Weiterhin hat die Queue jetzt genau ein Element.
Wenn schon etwas in der Queue ist, wird nur das letzte Element aktuallisiert, dh: das Element, was bis jetzt das letzte war,
bekommt das neue Letzte als Nachfolger, und das neue Letzte wird zum allerletzten Element der Queue erklärt.
Und der Zähler wird erhöht.
5) AddBefore:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
template<class T> //An erste Stelle setzen
void GTQueue<T>::AddBefore(const T & Value)
{
if(!m_iElementsCnt) //Liste ist leer
{
//Neues Element erstellen und Zähler hochsetzen
SElement *pNew=new SElement(Value,NULL,NULL);
m_pFirst=m_pLast=pNew;
m_iElementsCnt=1;
return;
}
//Neues Element erstellen, erstes "linken" und Zähler hochsetzen
SElement *pNew=new SElement(Value,NULL,m_pFirst);
m_pFirst->pLast=pNew;
m_pFirst=pNew;
m_iElementsCnt+=1;
}
|
Hier gibt es eigentlich wenige Unterschiede zu Add:
Statt dem letzten Element der Queue wird das erste verwendet. Das neue Element wird praktisch nur ganz nach vorn geschoben.
6) Get:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
template<class T>
GTResult GTQueue<T>::Get(T *pToFill)
{
if(!pToFill) //NULL-Pointer ausschließen
return(GT_ZERO_POINTER);
if(!m_iElementsCnt) //Liste ist leer
return(GT_INVALID_VALUE);
//Wert kopieren
*pToFill=m_pFirst->Value;
//Erste Elemtent löschen
SElement *pTemp=m_pFirst->pNext;
//if(m_iElementsCnt != 1) //ist gleich mit:
if(pTemp) //Nur ein Element vorhanden
pTemp->pLast=NULL;
GTSafeDelete(m_pFirst);
m_pFirst=pTemp;
//Zähler runterzählen
m_iElementsCnt-=1;
return(GT_OK);
}
|
Die Funktion erwartet einen Pointer auf eine Variable, in der der gelesene Wert gespeichert wird.
Hier muss erstmal eine Fehleranalyse durchgeführt werden:
NULL-Pointer ausschließen und Überprüfen ob überhaupt was in gelesen werden kann. Bei Fehlern wird mit entsprechendem Error-Code abgebrochen.
Wenn kein Fehler auftrat, wird der Wert kopiert.
Und das Element wird aus der Queue entfernt, da es verarbeitet wurde:
Erst wird der Pointer auf das nächste Element gesetzt.
Dann wird geprüft ob es das letzte Element war, denn wenn es das nicht war, wird das gelesene Element von der Queue "abgeschnitten",
indem der einzige Pointer, der darauf zeigt, gelöscht wird.
Dann wird noch der Speicher freigegeben, das neue erste Element "ernannt" und der Zähler verringert.
7) Peek:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
|
template<class T>
GTResult GTQueue<T>::Peek(T *pToFill) const
{ //Inhalt ausgeben
if(!pToFill) //NULL-Pointer ausschließen
return(GT_ZERO_POINTER);
if(!m_iElementsCnt) //Liste ist leer
return(GT_INVALID_VALUE);
*pToFill=m_pFirst->Value;
return(GT_OK);
}
|
Das hier ist um einiges kürzer als Get, denn es muss ja nur mal etwas kopiert werden und nichts entfernt.
Da an der Queue nichts verändert wird, kann die Methode auch als const definiert werden.
Die Funktion sollte eigentlich selbsterklärend sein.
Destroy:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
template<class T>
void GTQueue<T>::Destroy(void)
{
if(!m_iElementsCnt) //Liste ist leer
return;
SElement *pTemp=m_pFirst->pNext;
//if(m_iElementsCnt != 1) //ist gleich mit:
if(pTemp) //Nur ein Element vorhanden
pTemp->pLast=NULL;
GTSafeDelete(m_pFirst);
m_pFirst=pTemp;
//Zähler runterzählen
m_iElementsCnt-=1;
}
|
Man erkennt hier eigentlich schon den Teil von Get, der bei Peek gefehlt hat.
Peek und Destroy ergeben nacheinander aufgerufen auch wieder Get.
Puh! Fertig ist die Queue!
Hier ist nochmal der gesamte Header:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
#if defined _MSC_VER && _MSC_VER >= 1020
#pragma once
#endif
#ifndef _GT_QUEUE_
#define _GT_QUEUE_
//Aus der Engine kopiert
#define GTSafeDelete(Pointer) { delete(Pointer); (Pointer)=NULL; }
enum GTResult
{
GT_OK,
GT_ZERO_POINTER,
GT_INVALID_VALUE
};
//Eine "Warteschlange" für zum Beispiel Nachrichten,
//die nacheinander abgearbeitet werden müssen
//Es wird eine Kopie angelegt
template<class T>
class GTQueue
{
public:
//Eintrag in die Queue, ähnlich wie eine doppelt verkettete Liste
struct SElement
{
SElement *pLast, //Pointer auf vor und danach
*pNext;
T Value; //Der eigentliche Wert
//Kopierkonstruktoren
SElement(T _Value, SElement *_pLast, SElement *_pNext)
: Value(_Value), pLast(_pLast), pNext(_pNext) {}
SElement(SElement &Element)
: Value(Element.Value), pLast(Element.pLast), pNext(Element.pNext) {}
};
private:
SElement *m_pFirst, //Verwaltung
*m_pLast;
int m_iElementsCnt;
public:
//Konstruktor und Destruktor zum aufräumen
GTQueue(void) : m_pFirst(NULL), m_pLast(NULL), m_iElementsCnt(0) {}
~GTQueue(void);
void Delete(void); //aufräumen
int GetElementsCnt(void) const { return(m_iElementsCnt); } //selbsterklärend
//Queue bearbeiten
void Add(const T &); //Ganz normal ans Ende stellen
void AddBefore(const T &); //Ganz vorn ran stellen
GTResult Get(T *pToFill); //Nächstes Element raussuchen und aus Liste entfernen
GTResult Peek(T *pToFill) const; //Mal sehen was kommt
void Destroy(void); //Nächstes Element löschen (wenn's z.B. ungültig ist)
};
template<class T>
GTQueue<T>::~GTQueue()
{
if(m_iElementsCnt) //Bei Bedarf leeren
Delete();
m_pFirst=NULL; //Zurücksetzen
m_pLast=NULL;
m_iElementsCnt=0;
}
template<class T> //Alles aufräumen
void GTQueue<T>::Delete(void)
{
//Liste leeren
if(m_iElementsCnt) //Liste ist gefüllt
{
if(m_iElementsCnt==1) //Nur ein Element
GTSafeDelete(m_pFirst)
else
for(SElement* pCurrent=NULL;
pCurrent!=m_pLast;) //Bis zum letzten Eintrag gehen
{
pCurrent= m_pFirst; //immer weiter gehen
m_pFirst= m_pFirst->pNext;
delete(pCurrent); //und löschen
}
}
m_pFirst=NULL; //Zurücksetzen
m_pLast=NULL;
m_iElementsCnt=0;
}
template<class T>
void GTQueue<T>::Add(const T & Value)
{
if(!m_iElementsCnt) //Liste ist leer
{
//Neues Element erstellen und Zähler hochsetzen
SElement *pNew=new SElement(Value,NULL,NULL);
m_pFirst=m_pLast=pNew;
m_iElementsCnt=1;
return;
}
//Neues Element erstellen, letztes "linken" und Zähler hochsetzen
SElement *pNew=new SElement(Value,m_pLast,NULL);
m_pLast->pNext=pNew;
m_pLast=pNew;
m_iElementsCnt+=1;
}
template<class T> //An erste Stelle setzen
void GTQueue<T>::AddBefore(const T & Value)
{
if(!m_iElementsCnt) //Liste ist leer
{
//Neues Element erstellen und Zähler hochsetzen
SElement *pNew=new SElement(Value,NULL,NULL);
m_pFirst=m_pLast=pNew;
m_iElementsCnt=1;
return;
}
//Neues Element erstellen, erstes "linken" und Zähler hochsetzen
SElement *pNew=new SElement(Value,NULL,m_pFirst);
m_pFirst->pLast=pNew;
m_pFirst=pNew;
m_iElementsCnt+=1;
}
template<class T>
void GTQueue<T>::Destroy(void)
{
if(!m_iElementsCnt) //Liste ist leer
return;
SElement *pTemp=m_pFirst->pNext;
//if(m_iElementsCnt != 1) //ist gleich mit:
if(pTemp) //Nur ein Element vorhanden
pTemp->pLast=NULL;
GTSafeDelete(m_pFirst);
m_pFirst=pTemp;
//Zähler runterzählen
m_iElementsCnt-=1;
}
template<class T>
GTResult GTQueue<T>::Get(T *pToFill)
{
if(!pToFill) //NULL-Pointer ausschließen
return(GT_ZERO_POINTER);
if(!m_iElementsCnt) //Liste ist leer
return(GT_INVALID_VALUE);
//Wert kopieren
*pToFill=m_pFirst->Value;
//Erste Elemtent löschen
SElement *pTemp=m_pFirst->pNext;
//if(m_iElementsCnt != 1) //ist gleich mit:
if(pTemp) //Nur ein Element vorhanden
pTemp->pLast=NULL;
GTSafeDelete(m_pFirst);
m_pFirst=pTemp;
//Zähler runterzählen
m_iElementsCnt-=1;
return(GT_OK);
}
template<class T>
GTResult GTQueue<T>::Peek(T *pToFill) const
{ //Inhalt ausgeben
if(!pToFill) //NULL-Pointer ausschließen
return(GT_ZERO_POINTER);
if(!m_iElementsCnt) //Liste ist leer
return(GT_INVALID_VALUE);
*pToFill=m_pFirst->Value;
return(GT_OK);
}
#endif
|
5) Wie verwende ich die Queue jetzt?
Wer 4) aufmerksam gelesen hat, sollte die Queue eigentlich jetzt schon verwenden können.
Ich habe hier ein Beispielprogramm (für Konsole) geschrieben, was Texte in die Queue schickt, und dann wieder abholt.
Weiterhin werden die Funktionen zum löschen einzelner Elemente und der gesamten Queue getestet.
Ohne viele Gerede, denn ein Code sagt mehr als tausend Worte:
|
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include<iostream>
using namespace std;
#include"GTQueue.h"
int main()
{
cout<<"Test der GTQueue\n"<<endl;
GTQueue<char *> Queue;
char *pcText;
Queue.Add("Hallo, Welt!");
Queue.Add("Holunderbeeren");
Queue.Add("Haselnussstrauch");
Queue.Add("Bockwurst mit Senf");
Queue.AddBefore("Apfelkuchen mit extra viel Sahne");
Queue.AddBefore("24-Zoll Monitor");
Queue.Add("Die Neue GTQueue!");
while(!Queue.Get(&pcText))
{
if(!pcText)
{
cout<<"#Fehler 1!"<<endl;
return(1);
}
cout<<pcText<<endl;
}
cout<<endl;
Queue.AddBefore("Test");
for(int i=0;i<3;i++)
{
Queue.Peek(&pcText);
if(!pcText)
{
cout<<"#Fehler 2!"<<endl;
return(2);
}
cout<<pcText<<endl;
}
cout<<"Rest 1: "<<Queue.GetElementsCnt()<<endl;
Queue.Destroy();
cout<<"Rest 2: "<<Queue.GetElementsCnt()<<endl;
Queue.Destroy();
cout<<"Rest 3: "<<Queue.GetElementsCnt()<<endl;
Queue.Add("Test");
Queue.Add("Test");
Queue.Add("Test");
Queue.Add("Test");
Queue.Add("Test");
cout<<endl;
cout<<"Rest 4: "<<Queue.GetElementsCnt()<<endl;
Queue.Delete();
cout<<"Rest 5: "<<Queue.GetElementsCnt()<<endl;
return(0);
}
|
SOOO! Das wars!
Ich hoffe das Tutorial hat euch das Thema "Queue" etwas näher gebracht.
PS: Wer Rechtschreibfehler gefunden hat, der kann sie behalten! ;o)
Zitat
Stan dart-Queue
04.05.2024, 20:30
Zum Seitenanfang
