3.1. Co to jest kolejka?
Kolejka jest to
struktura danych, w której dostęp do danych jest możliwy tylko do pierwszego i ostaniego elementu. Kolejka jest określana mianem FIFO (First In First Out), czyli
pierwszy wchodzący element jest pierwszym wychodzącym.
3.2. Operacje na kolejce
Kolejka w STL'u posiada następujące operacje:
3.3. Jak wykorzystywać adapter kolejki w C++
Aby móc skorzystać z kolejki w C++, należy dołączyć plik nagłówkowy:
Kolejnym krokiem, jaki musimy wykonać jest utworzenie kolejki. Zapis uogólniony wygląda tak:
std::queue < TYP_DANYCH > nazwa_kolejki;
Kolejka może przechowywać dowolny typ danych - mogą być to typy, które już znasz czyli:
std::queue < int > kolejka1;
std::queue < std::string > kolejka2;
Mogą to być również struktury danych lub klasy, które utworzysz:
struct SDane
{
int liczba;
std::string tekst;
};
class CKlasa
{
private:
SDane dane[ 2 ];
public:
SDane & DajDane( int indeks )
{
return dane[ indeks ];
}
};
std::queue < SDane > kolejka3;
std::queue < CKlasa > kolejka4;
Jak widać utworzenie kolejki dowolnego typu danych jest proste i sprowadza się do napisania jednej linijki. W dalszej części tego rozdziału będą opisane metody za pomocą których możesz wykonywać wcześniej już wspomniane operacje na kolejce.
3.4. Umieszczanie nowego elementu w kolejce (metoda: push)
Metoda
push służy do umieszczenia nowego elementu na końcu kolejki.
void push( const TYP_DANYCH & wartosc );
Standardowa złożoność obliczeniowa metody:
O(1).
3.4.1. Przykład
#include <queue>
int main()
{
std::queue < int > kolejkaLiczb;
kolejkaLiczb.push( 123 );
kolejkaLiczb.push( 12 );
kolejkaLiczb.push( 55 );
return 0;
}
3.5. Odczytywanie i modyfikacja pierwszego elementu kolejki (metoda: front)
Metoda
front służy do odczytania lub modyfikacji wartości umieszczonej na początku kolejki.
TYP_DANYCH & front();
Standardowa złożoność obliczeniowa metody:
O(1).
3.5.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::queue < int > kolejkaLiczb;
std::cout << "Podaj liczbe: ";
int liczba;
std::cin >> liczba;
kolejkaLiczb.push( liczba );
kolejkaLiczb.push( 222 );
kolejkaLiczb.push( 555 );
std::cout << "Pierwsza liczba w kolejce to: " << kolejkaLiczb.front() << std::endl;
kolejkaLiczb.front() *= 2;
std::cout << "Zmodyfikowalem pierwsza liczbe w kolejce" << std::endl;
std::cout << "Pierwsza liczba w kolejce to: " << kolejkaLiczb.front() << std::endl;
kolejkaLiczb.front() = 1234;
std::cout << "Zmodyfikowalem pierwsza liczbe w kolejce" << std::endl;
std::cout << "Pierwsza liczba w kolejce to: " << kolejkaLiczb.front() << std::endl;
getch();
return 0;
}
3.6. Odczytywanie i modyfikacja ostatniego elementu kolejki (metoda: back)
Metoda
back służy do odczytania lub modyfikacji wartości umieszczonej na końcu kolejki.
TYP_DANYCH & back();
Standardowa złożoność obliczeniowa metody:
O(1).
3.6.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::queue < int > kolejkaLiczb;
std::cout << "Podaj liczbe: ";
int liczba;
std::cin >> liczba;
kolejkaLiczb.push( 123 );
kolejkaLiczb.push( 321 );
kolejkaLiczb.push( liczba );
std::cout << "Ostatnia liczba w kolejce to: " << kolejkaLiczb.back() << std::endl;
kolejkaLiczb.back() *= 2;
std::cout << "Zmodyfikowalem ostatnia liczbe w kolejce" << std::endl;
std::cout << "Ostatnia liczba w kolejce to: " << kolejkaLiczb.back() << std::endl;
kolejkaLiczb.back() = 1234;
std::cout << "Zmodyfikowalem ostatnia liczbe w kolejce" << std::endl;
std::cout << "Ostatnia liczba w kolejce to: " << kolejkaLiczb.back() << std::endl;
getch();
return 0;
}
3.7. Pobranie informacji o ilości elementów w kolejce (metoda: size)
Metoda
size zwraca ilość elementów aktualnie znajdujących się w kolejce.
size_type size() const;
Standardowa złożoność obliczeniowa metody:
O(1).
3.7.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::queue < int > kolejkaLiczb;
int liczba = 0;
do
{
std::cout << "Podaj liczbe (0 - konczy wprowadzanie liczb): ";
liczba = 0;
std::cin >> liczba;
if( liczba != 0 ) kolejkaLiczb.push( liczba );
} while( liczba != 0 );
std::cout << "W kolejce znajduje sie " << kolejkaLiczb.size() << " liczb." << std::endl;
getch();
return 0;
}
3.8. Sprawdzanie czy kolejka jest pusta (metoda: empty)
Metoda
empty sprawdza, czy kolejka jest pusta.
bool empty() const;
Standardowa złożoność obliczeniowa metody:
O(1).
3.8.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::queue < int > kolejkaLiczb;
if( kolejkaLiczb.empty() )
{
std::cout << "Kolejka jest pusta." << std::endl;
} else
{
std::cout << "W kolejce znajduje sie przynajmniej jeden element." << std::endl;
}
kolejkaLiczb.push( 1234 );
kolejkaLiczb.push( 124 );
kolejkaLiczb.push( 34 );
kolejkaLiczb.push( 4 );
if( kolejkaLiczb.empty() )
{
std::cout << "Kolejka jest pusta." << std::endl;
} else
{
std::cout << "W kolejce znajduje sie przynajmniej jeden element." << std::endl;
}
getch();
return 0;
}
3.9. Usunięcie istniejącego elementu z początku kolejki (metoda: pop)
Metoda
pop służy do usunięcia istniejącego elementu z początku kolejki.
void pop();
Standardowa złożoność obliczeniowa metody:
O(1).
3.9.1. Przykład
#include <queue>
#include <iostream>
#include <conio.h>
int main()
{
std::queue < int > kolejkaLiczb;
int liczba = 0;
do
{
std::cout << "Podaj liczbe (0 - konczy wprowadzanie liczb): ";
liczba = 0;
std::cin >> liczba;
if( liczba != 0 ) kolejkaLiczb.push( liczba );
} while( liczba != 0 );
std::cout << "Liczby wyjete z kolejki: ";
while( kolejkaLiczb.empty() == false )
{
std::cout << kolejkaLiczb.front() << ", ";
kolejkaLiczb.pop();
}
getch();
return 0;
}
3.10. Zaawansowane wykorzystywanie adaptera kolejki
Adapter kolejki w STL'u ma znacznie większe możliwości niż te, które do tej pory zobaczyłeś. Adapter STL'a umożliwia nam zmianę mechanizmu zarządzającego danymi bez potrzeby wprowadzania modyfikacji w całym programie. W rzeczywistości szablon STL'a zdefiniowany jest następująco:
namespace std
{
template < typename typZmiennej, typename kontenerDanych >
class queue
{
};
}
Aby adapter kolejki był łatwy w użyciu, twórcy STL'a dopisali linijkę, która dostarczy programiście kontener danych o najwyższej wydajności, jaki jest dostępny w STL'u. Linijka o której mowa wygląda następująco:
template < typename typZmiennej, typename kontenerDanych = deque < typZmiennej > >
class queue;
Dzięki powyższemu zapisowi kompilator wie, że jeśli nie podamy drugiego parametru, to użyje on domyślnego kontenera, którym dla kolejki w STL'u jest
deque. Zgodnie z powyższym - poniższe dwa zapisy są sobie równoważne:
std::queue < int > mojaKolejka1;
std::queue < int, std::deque < int > > mojaKolejka2;
Ponieważ programiści chcą być leniwi to używają krótszego zapisu, a ci początkujący często nie zdają sobie sprawy o tym, że istnieje jeszcze jeden parametr dla adaptera kolejki.
3.10.1. Po co tworzy się własne kontenery?
Pisząc własne programy może się zdarzyć tak, że będziesz chciał użyć własnego kontenera do obsługi kolejki, a nie STL'owego. Pierwsze co zrobiłby początkujący programista, to wykonałby następującą zmianę:
std::queue < int > mojaKolejka;
CMojaKolejka mojaKolejka;
Rozwiązanie takie jest oczywiście poprawne, jednak pozostali programiści pracujący w tym samym projekcie musieliby poznać jak jest zbudowana klasa CMojaKolejka i jakie daje metody. Co więcej prawdopodobnie nie będą oni zainteresowani zgłębianiem tajników klasy, którą utworzyłeś i użyją do tego celu STL'a, który może być znacznie wolniejszy od Twojego rozwiązania. Warto jednocześnie zaznaczyć, że tracisz możliwość używania dowolnego typu danych. Co więc zrobić, aby Twój kod był użyteczny i stosowany w programie? Należy napisać własny kontener, który podmienisz w linijce tworzącej kolejkę. Kontener ten będzie jednocześnie uniwersalny dla dowolnego typu danych, więc będzie mógł być wykorzystywany wielokrotnie w programie do różnych celów.
3.10.2. Zanim zabierzesz się za tworzenie własnego kontenera
Tworzenie kontenerów wiąże się z umiejętnością tworzenia
szablonów klas. Jeśli nie wiesz co to są szablony i jak się je tworzy, to warto prędzej czy później poczytać o nich, bowiem nigdy nie wiadomo kiedy się na nie natkniesz. Poniżej przedstawię tylko zarys szablonu klasy, który musi być zaimplementowany aby nasz kontener mógł zostać użyty w adapterze STL'a. Pamiętaj, że zmieniając kontener zmieniasz złożoność obliczeniową każdej z funkcji. Tworząc własny kontener możesz zaszkodzić wydajności programu, ponieważ Twój kontener może być wolniejszy od domyślnego STL'owego kontenera. Warto również go gruntownie przetestować pod kątem wszystkich operacji, żeby się nie okazało, że użycie Twojego kontenera powoduje np. wieszanie się całej aplikacji.
3.10.3. Jak utworzyć własny kontener do adaptera kolejki?
Poniższy kod jest wzorem, który można wykorzystać przy tworzeniu własnej implementacji kontenera, który będzie mógł współpracować z adapterem kolejki STL'a.
#include <queue>
template < typename typZmiennej >
class CKontenerKolejki
{
public:
typedef typZmiennej value_type;
typedef typZmiennej & reference;
typedef const typZmiennej & const_reference;
typedef int size_type;
void push_back( const_reference zmienna ) { }
void pop_front( void ) { }
bool empty( void ) const { }
size_type size( void ) const { }
reference front( void ) { }
reference back( void ) { }
CKontenerKolejki( void ) { }
CKontenerKolejki( const CKontenerKolejki & skopiuj ) { }
~CKontenerKolejki( void ) { }
};
int main()
{
std::queue < int, CKontenerKolejki < int > > mojaKolejka;
mojaKolejka.push( 12 );
mojaKolejka.pop();
mojaKolejka.empty();
mojaKolejka.size();
mojaKolejka.front();
mojaKolejka.back();
return 0;
}
Warto w tym miejscu dodać, że do powyższego szablonu klasy możesz dodawać własne zmienne i funkcje. Adapter kolejki będzie widział jednak tylko i wyłącznie funkcje, które zostały wyszczególnione w powyższym przykładzie co oznacza, że nie możesz nazwać inaczej funkcji publicznych, służących do wykonywania wyszczególnionych operacji.