Programowanie w języku C/C++

Kolejki

Witam. Pierwszy post, troche stresu :) Wolne tłumaczenie z artykułów w języku ang.
A więc...

Kolejka, ang. "queue", jest to pewnego rodzaju "pojemnik", przygotowany do pracy w kontekście FIFO (first-in, first-out), gdzie elementy w nim umieszczane są w późniejszych fazach naszego algorytmu rozpatrywane.

Myślicie, jakie zastosowanie? Odpowiedź: Przykładem może być algorytm Djikstry, gdzie w labiryncie szukamy optymalnej ilości ruchów na pokonanie drogi. Często stosowany w zadaniach "poszukiwawczych" opartych na macierzach. (Jeżeli chcecie się dowiedzieć więcej o tym algorytmie, zapraszam na Google :) Na 4programmers sądzę, że też coś znajdziecie, szczerze nie przeglądałem jeszcze :) )

Wracając do naszej kolejki...

Znajduje się ona w bibliotece o nazwie "queue". Aby dodać ją do naszego programu należy dodać dyrektywe (nagłówek) #include<queue>. Jest to standardowa biblioteka w C++.
Gdy dodamy ją już do programu, należy ją potem skonstruować. Kolejka jak każda zmienna posiada swój typ, który trzeba określić przy jej tworzeniu. Dla przykładu podam tworzenie kolejki typu "string":
 #include<iostream>
 #include <queue>  // nasza biblioteka
 
 using namespace std;
 
 int main(){ 
 
  queue<string> nazwa_kolejki;  // i konstruktor
}


Proste, prawda? Dobra, rozbudujmy nasz program o kilka dodatkowych funkcji.

 #include<iostream>
 #include <queue>
 
 using namespace std;
 
 int main(){ 
 
  queue<string>nazwa_kolejki;
  while( nazwa_kolejki.size() < 5 ) {
    cout << "Witam, podaj jakies imie: ";
    string s;
    getline( cin, s );
   nazwa_kolejki.push(s);
  }
 
  while( !nazwa_kolejki.empty() ) {
    cout << "Podales: " << nazwa_kolejki.front() << endl;
    nazwa_kolejki.pop();
  }
system("PAUSE");
}


I już wszystko wyjaśniam pokolei.
Rozpatrzmy linię

while( nazwa_kolejki.size() < 5 ) 


Jak zapewnie sie domyślacie funkcja size() zwraca liczbę elementów w kolejce.

Kolejna linia istotna dla nas, to

 
nazwa_kolejki.push(s);


Funkcja push(zmienna) odpowiada za dodawanie elementu "zmienna" na koniec kolejki. Śledząc działania naszego programu, dodaje on na koniec kolejki kolejne podane przez nas imię.

Następnie mamy  
while( !nazwa_kolejki.empty() )


Funkcja empty() zwraca prawdę (true) kiedy kolejka jest pusta. Zatem w naszym małym programie "wyrzucamy" kolejne elementy z kolejki na ekran, aż do momentu kiedy kolejka będzie pusta.

Jedziemy dalej, funkcja front() zwraca wartość pierwszego elementu w kolejce. Nie sposób było się domyślić :) Analogiczną do niej funkcją jest funkcja back(), która zwaraca wartość elementu stojącego na samym końcu kolejki.

Następna linia  

nazwa_kolejki.pop();


Tutaj widzimy funkcję pop(). Co robi? Usuwa pierwszy element w kolejce. Proste.

Narazie tyle ile znalazłem, jeżeli coś mi się wiecej nawinie, podziele się z Wami :)



3 komentarze

Piotrekdp 2007-11-15 12:08

Kolejka na starcie zajmuje już ok 40 bajtów ale nie to jest najważniejsze majważniejsza jest jej funkcjonalność. a potem jej rozmiar rośnie podobnie do tablicy.co przy wiekszej ilości danych traci znaczenie .

menda90 2007-11-13 18:56

Co do ostatniego i przedostatniego Twojego zdania , nie ma sprawy, ale tak poza tym to nie lubie polskiego =]

Wie ktoś może jak stoi sprawa z pamięcią w kolejce? Pożera dużo więcej niż np. tablica z identyczną ilością elementów?

Piotrekdp 2007-11-13 13:53

Faktycznie wygląda to jak post
Kolejka
Kolejka jest to strukura z ograniczonym dostępem do pamięci , dla której określono początek i koniec.
Istota kolejki polega na tym , że w pierwszej kolejności  zawsze obsługiwany jest element z przodu kolejki natomiast nowe elementy są dołączane na jej koniec. Mówimy ,że elementy kolejki obsługiwane są według kolejności FIFO (First in First Out ) czyli "pierwszy przyszedł , pierwszy wyszedł".

itd, Tak sie pisze ! :p ale nie mam czasu sie rozpisywać więc tego nie poprawię :p
Nie używaj zwrotów typu:
"Pierwszy post, troche stresu :) "
Nie zaczynaj zdania od "a więc" - już mi o tym Pani z polskiego kilka lat temu mówiła :p