Czym jest kolejka?
queue to kontener działający na zasadzie FIFO (First In, First Out) — "kto pierwszy wszedł, ten pierwszy wyjdzie". W przeciwieństwie do vector, w queue nie można zajrzeć do środka ani wyciągnąć dowolnego elementu — dodajemy tylko na koniec, a wyciągamy tylko od przodu.
#include <queue>
queue<typ> nazwa;
// przykład:
queue<string> kolejkaDoKasy;
push, front, pop, empty, size
Pięć operacji wystarczy, żeby swobodnie posługiwać się kolejką. Dodajemy zawsze na koniec, a odczytujemy i usuwamy zawsze z przodu.
push(x)
Dodaje nowy element na koniec kolejki. To on będzie obsłużony jako ostatni z aktualnie czekających.
front()
Pokazuje element na początku kolejki (ten, który będzie obsłużony jako następny), nie usuwając go.
pop()
Usuwa element z początku kolejki. Uwaga: pop() nic nie zwraca — element trzeba najpierw odczytać przez front().
empty() / size()
empty() sprawdza, czy kolejka jest pusta (przed front()/pop() warto to zrobić), a size() zwraca liczbę elementów.
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<string> kolejkaDoKasy;
kolejkaDoKasy.push("Kacper");
kolejkaDoKasy.push("Ania");
cout << "Na poczatku: " << kolejkaDoKasy.front();
kolejkaDoKasy.pop(); // obsluzono "Kacper"
return 0;
}
Symulacja kolejki do kasy
Użytkownik podaje imiona, wpisując koniec, gdy skończy. Program dodaje je do kolejki, a potem obsługuje w kolejności wejścia (FIFO) — dokładnie tak, jak działa prawdziwa kolejka.
queue<string> nowaKolejka;
string imie;
cin >> imie;
while (imie != "koniec") {
nowaKolejka.push(imie);
cin >> imie;
}
int numer = 1;
while (!nowaKolejka.empty()) {
cout << numer << ". "
<< nowaKolejka.front();
nowaKolejka.pop();
numer++;
}
Wszystko, co robi się z kolejką
Kolejka jest wyjątkowo skromna: każda operacja to O(1), ale zestaw operacji jest bardzo krótki. Widać wyłącznie oba końce — do środka nie da się zajrzeć ani niczego wyszukać.
| Metoda | Co robi | Uwaga |
|---|---|---|
q.push(x) |
Dokłada element na koniec kolejki. | Jak stanięcie na końcu ogonka |
q.front() |
Podgląda pierwszy element — ten, który wyjdzie najwcześniej. | Nie usuwa |
q.back() |
Podgląda ostatni dodany element. | Rzadko potrzebne |
q.pop() |
Usuwa pierwszy element. | Nic nie zwraca |
q.size() / q.empty() |
Liczba elementów i test pustości. | Sprawdzaj przed front() |
szukanie elementu |
Niemożliwe — widać tylko oba końce. | To cena za prostotę |
q[i] |
Też niemożliwe. | Potrzebujesz tego → weź deque |
d.push_front(x) / d.pop_front() |
deque: dokładanie i zdejmowanie z przodu. |
— |
d.push_back(x) / d.pop_back() |
deque: to samo z tyłu. |
— |
d[i] |
deque pozwala na indeksowanie. |
W przeciwieństwie do queue |
Dwa wiersze oznaczone jako brak to nie ograniczenie do obejścia, tylko cecha konstrukcyjna. Jeśli potrzebujesz indeksowania albo zdejmowania z obu stron — właściwym narzędziem jest deque, która potrafi wszystko to, co kolejka, a do tego więcej.
| Struktura | Zasada działania | Kiedy wybrać |
|---|---|---|
queue |
Pierwszy wszedł, pierwszy wychodzi — jak kolejka do kasy. | Symulacje, obsługa zgłoszeń po kolei |
stack |
Ostatni wszedł, pierwszy wychodzi — jak stos talerzy. | Nawiasy, cofanie akcji |
deque |
Oba końce plus indeksowanie. | Gdy potrzebujesz dokładać z obu stron |
priority_queue |
Wychodzi element najważniejszy, nie najstarszy. | Gdy liczy się priorytet — patrz temat Kopiec |
vector jako kolejka |
erase(begin()) przesuwa wszystko. |
Nie rób tego — jest wolne |
Ostatni wiersz to częsty błąd początkujących: vector z erase(v.begin()) wygląda jak kolejka, ale każde zdjęcie przesuwa wszystkie pozostałe elementy. Przy stu tysiącach operacji to O(n^2) zamiast O(n).
Szukanie najkrótszej drogi
Tej sekcji nie musisz jeszcze rozumieć. Pokazujemy ją, żebyś wiedział, po co kolejka istnieje — bo to jej najsłynniejsze zastosowanie. Wyobraź sobie labirynt i pytanie: ile kroków dzieli wejście od wyjścia? Kolejka rozwiązuje to w zaskakująco prosty sposób: zaczynasz od pola startowego, wkładasz do kolejki wszystkich jego sąsiadów, potem sąsiadów sąsiadów — i tak dalej. Ponieważ kolejka wydaje pola w tej samej kolejności, w jakiej je wkładałeś, pola bliższe startu są zawsze sprawdzane przed dalszymi. Dzięki temu pierwsze dojście do wyjścia jest od razu tym najkrótszym.
Pomysł jest prosty: odwiedzamy pola warstwami. Najpierw wszystkie oddalone o jeden krok, potem o dwa, i tak dalej. Ponieważ kolejka oddaje elementy w kolejności wkładania, warstwy same układają się po kolei — a pierwszy moment dotarcia do pola to od razu najkrótsza droga do niego.
| Element | Rola | Uwaga |
|---|---|---|
Kolejka pozycji |
Trzyma pola czekające na odwiedzenie. | Startowa pozycja wchodzi jako pierwsza |
Tablica odległości |
dist[i][j] — ile kroków do tego pola. |
Wypełniona -1 = nieodwiedzone |
Zdejmij z przodu |
q.front(), potem q.pop(). |
Zawsze najbliższe pole |
Sprawdź sąsiadów |
Cztery kierunki przez tablice dx, dy. |
Osiem, gdy dozwolone skosy |
Oznacz przy wkładaniu |
Ustaw dist w momencie push. |
Nie przy zdejmowaniu — inaczej duplikaty |
Pierwsze dotarcie = najkrótsze |
BFS odwiedza pola warstwami. | Działa tylko przy równych kosztach |
// szkielet BFS - zapamiętaj ten układ, wraca w każdym zadaniu
queue<pair<int, int>> q;
q.push({startX, startY});
dist[startX][startY] = 0;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (poza_plansza(nx, ny)) continue;
if (sciana(nx, ny)) continue;
if (dist[nx][ny] != -1) continue; // już byliśmy
dist[nx][ny] = dist[x][y] + 1;
q.push({nx, ny}); // oznacz PRZY WKŁADANIU
}
}
Najczęstszy błąd w BFS to oznaczanie pola jako odwiedzonego dopiero przy zdejmowaniu z kolejki. Wtedy to samo pole trafia do niej wielokrotnie — zanim je zdejmiemy, sąsiedzi zdążą wrzucić je jeszcze kilka razy. Kolejka puchnie, program zwalnia, a przy większych planszach kończy się pamięć. Oznaczaj przy wkładaniu.
Warto też pamiętać o ograniczeniu: BFS daje najkrótszą drogę tylko wtedy, gdy każdy krok kosztuje tyle samo. Gdy krawędzie mają różne wagi, potrzebny jest algorytm Dijkstry — a tam zamiast zwykłej kolejki używa się kopca.
Sprawdź się na zadaniach
Trzy zadania: czysta symulacja na kolejce, wzorcowy BFS i przypadek, w którym zwykła kolejka nie wystarcza i trzeba sięgnąć po deque. Rozwiązania są zwinięte — spróbuj najpierw sam.
DODAJ imie dodaje osobę na koniec kolejki, OBSLUZ obsługuje pierwszą osobę i wypisuje jej imię, ILE wypisuje liczbę czekających. Dane kończy KONIEC.front() sprawdzić empty(), bo ktoś może wpisać OBSLUZ przy pustej kolejce.Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
queue<string> q;
string polecenie;
while (cin >> polecenie && polecenie != "KONIEC") {
if (polecenie == "DODAJ") {
string imie;
cin >> imie;
q.push(imie);
}
else if (polecenie == "OBSLUZ") {
if (q.empty()) {
cout << "pusto\n";
} else {
cout << q.front() << "\n";
q.pop();
}
}
else if (polecenie == "ILE") {
cout << q.size() << "\n";
}
}
return 0;
}
n imion do kolejki i wypisz je w kolejności obsługi. Na końcu podaj, kto był ostatni.Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
queue<string> q;
for (int i = 0; i < n; i++) {
string imie;
cin >> imie;
q.push(imie);
}
string ostatni;
while (!q.empty()) {
ostatni = q.front();
cout << ostatni << " ";
q.pop();
}
cout << "\nOstatni: " << ostatni;
return 0;
}
n dzieci, każde chce się przejechać k razy. Karuzela zabiera jedno dziecko na jeden przejazd, po czym wraca ono na koniec kolejki. Wypisz kolejność przejazdów.{imie, ile_zostalo}. Po przejeździe zmniejsz licznik i — jeśli dziecko chce jeszcze jechać — wrzuć je z powrotem przez push. Tak modeluje się „wraca na koniec”.Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
queue<pair<string, int>> q;
for (int i = 0; i < n; i++) {
string imie;
cin >> imie;
q.push({imie, k});
}
while (!q.empty()) {
auto [imie, zostalo] = q.front();
q.pop();
cout << imie << " ";
zostalo--;
if (zostalo > 0) q.push({imie, zostalo});
}
return 0;
}
n dzieci. Ziemniak przechodzi k razy z rąk do rąk, a potem dziecko, które go trzyma, odpada. Kto zostanie na końcu?k takich obrotach zdejmij bez wkładania z powrotem. Powtarzaj, aż zostanie jedno dziecko.Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
queue<string> q;
for (int i = 0; i < n; i++) {
string imie;
cin >> imie;
q.push(imie);
}
while (q.size() > 1) {
// k podan: z przodu na koniec
for (int i = 0; i < k; i++) {
q.push(q.front());
q.pop();
}
// ten, kto trzyma, odpada
cout << "Odpada: " << q.front() << "\n";
q.pop();
}
cout << "Wygral: " << q.front();
return 0;
}
n dokumentów, każdy z ważnością od 1 do 9. Drukarka bierze pierwszy dokument z kolejki, ale jeśli dalej czeka ważniejszy, odkłada go na koniec i bierze następny. Wypisz kolejność drukowania.{numer, waznosc}. Żeby sprawdzić, czy dalej czeka ważniejszy, potrzebujesz osobnego licznika ilu dokumentów o każdej ważności jeszcze zostało — albo po prostu przejrzyj pomocniczą tablicę liczników.Pokaż rozwiązanie
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
queue<pair<int, int>> q; // {numer, waznosc}
int ile[10] = {}; // ile zostalo kazdej waznosci
for (int i = 1; i <= n; i++) {
int w;
cin >> w;
q.push({i, w});
ile[w]++;
}
while (!q.empty()) {
auto [numer, waznosc] = q.front();
q.pop();
// czy dalej czeka wazniejszy?
bool jestWazniejszy = false;
for (int w = waznosc + 1; w <= 9; w++) {
if (ile[w] > 0) jestWazniejszy = true;
}
if (jestWazniejszy) {
q.push({numer, waznosc}); // na koniec
} else {
cout << numer << " ";
ile[waznosc]--;
}
}
return 0;
}
n × m, w którym . to wolne pole, # to ściana, S to start, a K to koniec. Wypisz najmniejszą liczbę kroków od startu do końca albo -1, jeśli nie da się przejść.K jest tym najkrótszym.Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> plansza(n);
for (int i = 0; i < n; i++) cin >> plansza[i];
vector<vector<int>> odl(n, vector<int>(m, -1));
queue<pair<int,int>> q;
// znajdujemy start
for (int w = 0; w < n; w++)
for (int k = 0; k < m; k++)
if (plansza[w][k] == 'S') {
q.push({w, k});
odl[w][k] = 0;
}
int dw[4] = {-1, 1, 0, 0};
int dk[4] = {0, 0, -1, 1};
while (!q.empty()) {
auto [w, k] = q.front();
q.pop();
if (plansza[w][k] == 'K') {
cout << odl[w][k];
return 0;
}
for (int i = 0; i < 4; i++) {
int nw = w + dw[i], nk = k + dk[i];
if (nw < 0 || nw >= n || nk < 0 || nk >= m) continue;
if (plansza[nw][nk] == '#') continue;
if (odl[nw][nk] != -1) continue; // juz bylem
odl[nw][nk] = odl[w][k] + 1;
q.push({nw, nk});
}
}
cout << -1;
return 0;
}