C++ · Kontenery STL · Kolejka

Kolejka (queue) w C++

Poznaj kontener queue — strukturę danych działającą na zasadzie FIFO (First In, First Out). Dokładnie jak kolejka w sklepie: kto pierwszy przyszedł, ten pierwszy zostanie obsłużony.

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.

skladnia.cpp
#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.

kolejka_do_kasy.cpp
#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;
}
▶ Wyjście programu
Na poczatku: Kacper

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.

wczytywanie.cpp
queue<string> nowaKolejka;
string imie;

cin >> imie;
while (imie != "koniec") {
    nowaKolejka.push(imie);
    cin >> imie;
}
▶ Pomysł
Kazde imie trafia na koniec kolejki - dokladnie tak jak klient ustawiajacy sie w rzedzie.
obsluga.cpp
int numer = 1;
while (!nowaKolejka.empty()) {
    cout << numer << ". "
         << nowaKolejka.front();
    nowaKolejka.pop();
    numer++;
}
▶ Wyjście programu
1. Kacper 2. Ania 3. Bartek

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ć.

MetodaCo robiUwaga
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.

StrukturaZasada działaniaKiedy 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.

ElementRolaUwaga
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
bfs_szkielet.cpp
// 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.

Łatwe Kolejka do kasy
Wczytuj polecenia: 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.
Jak to ugryźć: Zadanie na rozgrzewkę — chodzi o samą składnię. Pamiętaj, żeby przed front() sprawdzić empty(), bo ktoś może wpisać OBSLUZ przy pustej kolejce.
Pokaż rozwiązanie
kasa.cpp
#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;
}
Łatwe Kto wyjdzie ostatni
Wczytaj n imion do kolejki i wypisz je w kolejności obsługi. Na końcu podaj, kto był ostatni.
Jak to ugryźć: Kolejka wydaje elementy w tej samej kolejności, w jakiej je wkładałeś — czyli wynik będzie identyczny z wejściem. To nie błąd, tylko cała istota kolejki (w przeciwieństwie do stosu, który odwraca kolejność).
Pokaż rozwiązanie
kolejnosc.cpp
#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;
}
Łatwe Przepustka na jazdę
Do karuzeli ustawiło się 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.
Jak to ugryźć: Kolejka par {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
karuzela.cpp
#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;
}
Średnie Gorący ziemniak
W kole stoi 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?
Jak to ugryźć: Kolejka idealnie modeluje krąg: zdejmij z przodu i od razu włóż z powrotem na koniec — to jest właśnie „podanie dalej”. Po k takich obrotach zdejmij bez wkładania z powrotem. Powtarzaj, aż zostanie jedno dziecko.
Pokaż rozwiązanie
ziemniak.cpp
#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;
}
Średnie Drukarka z priorytetami
Do drukarki trafia 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.
Jak to ugryźć: Kolejka par {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
drukarka.cpp
#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;
}
Trudne Najkrótsza droga w labiryncie
Wczytaj labirynt 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ść.
Jak to ugryźć: To zastosowanie z sekcji piątej. Wrzuć start do kolejki z odległością 0. Potem w pętli zdejmuj pole, sprawdzaj czterech sąsiadów i wrzucaj tych, na których jeszcze nie byłeś, z odległością o jeden większą. Kolejka gwarantuje, że pola bliższe startu sprawdzisz wcześniej — więc pierwsze dojście do K jest tym najkrótszym.
Pokaż rozwiązanie
labirynt.cpp
#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;
}

Częste błędy i dobre praktyki

🚫
pop() nic nie zwraca
pop() tylko usuwa element z przodu kolejki. Jeśli chcesz poznać jego wartość, najpierw wywołaj front(), a dopiero potem pop().
⚠️
Zawsze sprawdzaj empty()
Wywołanie front() lub pop() na pustej kolejce to zachowanie niezdefiniowane i częsta przyczyna crasha programu.
🔍
Brak dostępu do środka
Kolejki nie da się indeksować ani przeglądać pętlą for jak vector. Jedyny widoczny element to ten na początku.
➡️
Ta sama kolejność
Elementy schodzą z kolejki w takiej samej kolejności, w jakiej zostały dodane — to właśnie definicja FIFO.
🧩
Zastosowania
Kolejka świetnie sprawdza się przy symulacjach (kasy, drukarki, poczekalnie) oraz przy przeszukiwaniu grafu wszerz (BFS).
📦
Nagłówek <queue>
Żeby korzystać z queue, trzeba dołączyć nagłówek <queue> — bez niego kompilator nie rozpozna tego typu.

Gotowy na więcej?

Dołącz do T-Olimpians i trenuj z doświadczonymi mentorami. Zbuduj bazę, która prowadzi do finałów OI.