[Kurs STL, C++] III. Adapter kolejki (std::queue)

var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));


var pageTracker = _gat._getTracker("UA-3650348-1");
pageTracker._initData();
pageTracker._trackPageview();



Serwis został przeniesiony pod nową domenę: http://cpp0x.pl/ Strona główna Kursy Artykuły Forum Pliki Promuj Nas! PowrótHistoria odwiedzonych stronPoprzednia lekcjaKurs STL, C++Następna lekcjaIII. Adapter kolejki (std::queue)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 kolejceKolejka w STL'u posiada następujące operacje:push - umieszczenie nowego elementu na końcu kolejki;pop - usunięcie istniejącego elementu z początku kolejki;empty - informacja czy kolejka jest pusta;size - zwraca ilość elementów umieszczonych w kolejce;front - zwraca wartość pierwszego elementu w kolejce.back - zwraca wartość ostatniego elementu w kolejce.3.3. Jak wykorzystywać adapter kolejki w C++Aby móc skorzystać z kolejki w C++, należy dołączyć plik nagłówkowy:#include <queue>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; //kolejka przechowująca liczbystd::queue<std::string> kolejka2; //kolejka przechowująca stringi (czyli tekst)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 kolejkiAdapter 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  {    //...  };//class queue}//namespace stdAby 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;//ten wiersz wyrzucaCMojaKolejka mojaKolejka;//ten wiersz wstawiaRozwią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 konteneraTworzenie 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.Poprzednia lekcjaKurs STL, C++Następna lekcjaWszelkie prawa zastrzeżone. Autor: Piotr SzawdyńskiWszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści bez wyraźnej zgody jego autora jest zabronione.PowrótHistoria odwiedzonych stronPanel LogowaniaLogin:Hasło:Zapamiętaj mnie!Zarejestruj sięOdzyskiwanie hasłaUżytkownikówObecnie aktywnych:13Zalogowanych:0Zarejestrowanych:4367Ostatnie 24h:413Non-cookie 24h:3190Wszystkich:264759Ostatnia Aktualizacja2010-11-23 00:46:20 (39 dni temu)Ostatnio aktywniHandy9020 godzPiotr Szawdyński21 godzFletcher37 godzwiew39 godzPietrzuch40 godzmat250149 godzbooncki51 godzRaver74 godzWynajem Sopot - wakacjePokój 2 osobowy 130zł/doba;Lokalizacja: Sopothttp://sopotwynajem.pl


O portaluArchiwumHistoriaIndeksRegulaminWyszukiwarkaLinkiRestauracja "ATOL" - Sopot© Wszelkie prawa zastrzeżone   2005-2011Czas wygenerowania strony: 0.050sAutor: Piotr Szawdyński