Struktury danych/Implementacje w C++/Kolejki

Z Wikibooks, biblioteki wolnych podręczników.
Przejdź do nawigacji Przejdź do wyszukiwania

Implementacja tablicowa[edytuj]

 1 template <typename type>
 2 class Queue
 3 {
 4 	type* tab; // dynamicznie alokowana pamięć na tablicę cykliczną
 5 	int size; // aktualna wielkość tablicy
 6 	int front;// indeks tablicy wskazujący na początek kolejki
 7 	int back; // indeks tablicy wskazujący na koniec kolejki, normalnie będzie wskazywał na pierwsze wolne pole w tablicy
 8 	int index_add(int);// funkcja pomocnicza do obliczania indeksu
 9 public:
10 	Queue(); //konstruktor domyślny tworzący kolejkę wielkości 
11 	Queue(int s);
12 	~Queue();
13 
14 	void enqueue(type co); //ustawia na końcu kolejki
15 	type dequeue();        //usuwa z początku kolejki
16 	bool empty();
17 	bool full();
18 };
19 
20 template <typename type>
21 Queue<typ>::Queue()
22 {
23 	size=10; //domyślna wielkość kolejki
24 	front=0; 
25 	back=0; 
26 
27 	tab = new type[size];
28 	if (tab == NULL) // ewentualne zabezpieczenie przed brakiem pamięci
29 	{
30 		throw "Błąd alokacji pamięci!";
31 	}
32 }
33 
34 template <typename type>
35 Queue<type>::Queue(int s) // konstruktor z zadaną przez nas wielkością kolejki
36 {
37 	size=s; // przypisanie przekazanej wielkości
38 	front=0;
39 	back=0;
40 
41 	tab = new type[size];
42 	if (tab == NULL)
43 	{
44 		throw "Błąd alokacji pamięci!";
45 	}
46 
47 }
48 
49 template <typename type>
50 Queue<type>::~Queue()
51 {
52 	delete []tab; // zwolnienie zaalokowanej wcześniej pamięci
53 }
54 
55 template <typename type>
56 void Queue<type>::enqueue(type co)
57 {
58 	if(full())
59 		throw "Queue jest pełna!";
60 	else
61 	{
62 		tab[back]=co;
63 		back=index_add(back);
64 	}
65 }
66 
67 template <typename type>
68 type Queue<type>::dequeue()
69 {
70 	if(empty())
71 	{
72 		throw "Queue jest pusta!";
73 		return -1;
74 	}
75 	else
76 	{
77 		type tmp = tab[front];
78 		front = index_add(front);
79 		return tmp;
80 	}
81 }
82 
83 template <typename type>
84 int Queue<type>::index_add(int i)
85 {
86 	return (i+1)%size;
87 }
88 
89 template <typename type>
90 bool Queue<type>::empty()
91 {
92 	return back == front;
93 }
94 
95 template <typename type>
96 bool Queue<type>::full()
97 {
98 	return index_add(back) == front;
99 }