Queue, deque és BFS alapok

A queue a FIFO állapotáramlást tanítja meg, a deque ezt kétoldali működéssé bővíti, a BFS pedig ugyanezt a queue-logikát használja rétegenkénti bejárásra, minimum lépésszámos gondolkodásra és state expansionre.

---

1. Definíció

Mi az a queue?

A queue egy First-In, First-Out adatstruktúra. A legrégebben betett elem jön ki először. Az alapműveletek jellemzően enqueue, dequeue, peek és isEmpty.

Miért létezik?

A queue azért hasznos, mert sok folyamatnak érkezési sorrendet kell követnie. Ez előjön schedulingnél, bufferingnél, breadth-first explorationnél, level-order traversalnél és olyan state-space feladatoknál, ahol a korábban felfedezett állapotokat kell előbb feldolgozni.

Mi az a deque?

A deque egy double-ended queue. Mindkét végén támogat beszúrást és eltávolítást, ami rugalmasabbá teszi, mint a sima queue-t. Tud modellezni queue viselkedést, stack viselkedést, sliding window segédstruktúrát, és később 0-1 BFS-szerű mintákat.

Mi az a BFS?

A BFS a Breadth-First Search rövidítése. Rétegenként járja be az állapotteret, queue-t használ, mert a korábban felfedezett frontier-elemeket kell előbb feldolgozni. Ez tartja meg az unweighted távolságrétegeket.

Hova illik?

Ez a téma akkor fontos, ha a feladat FIFO feldolgozásról, level-order traversalról, minimum steps-ről unweighted környezetben, hullámszerű state expansionről, vagy kétoldali candidate-kezelésről szól.

Intuíció

A queue olyan, mint egy sor a pénztárnál — aki előbb érkezett, azt szolgálják ki előbb. A deque olyan sor, ahol mindkét végén kontrolláltan lehet műveletet végezni. A BFS pedig olyan, mint amikor egy várost gyűrűnként fedezel fel: először mindent, ami egy lépésre van, utána mindent, ami két lépésre, aztán mindent, ami háromra. A lényeg a rétegek sorrendje.

Java kontextus

Java-ban queue viselkedéshez is a Deque a standard API. Gyakori implementáció:

Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(10);
queue.offerLast(20);
int first = queue.peekFirst();
int removed = queue.pollFirst();

Sima queue szemantikához sokan a Queue interfészt használják ArrayDeque vagy LinkedList implementációval.

Interjúban az ArrayDeque általában a tiszta gyakorlati alapértelmezett.

---

2. Alapfogalmak

2.1 FIFO működés

A queue definíciójának lényege a FIFO — a korábban bekerült munkaelem kerül előbb feldolgozásra. Ez akkor fontos, ha a sorrend időt, távolságot vagy fairness-t modellez. Példák: ügyfélsor, task buffer, BFS frontier, fa bejárása szintenként, minimum-step exploration.

2.2 Queue műveletek és komplexitás

2.3 Deque műveletek

A deque mindkét végét támogatja: offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast. Ez azért fontos, mert sok interjúminta valójában olyan queue-logika, ahol az egyik végén érkeznek elemek, a másik végén pedig kontrollált tisztítás történik.

2.4 Miért kell queue a BFS-hez?

A BFS növekvő távolságsorrendben járja be az állapotokat. Amikor kibontasz egy állapotot, az újonnan felfedezett szomszédok a következő réteghez tartoznak, ezért be kell állniuk a jelenlegi réteg összes fennmaradó eleme mögé — ez pontosan FIFO. Ha véletlenül stack-szerű viselkedést használsz, DFS-szerű irányba csúszol el, és elveszik a réteggarancia.

2.5 A visited állapot számít

Graf vagy általános állapottér BFS-ben a visited gyakran kötelező. Enélkül ugyanaz az állapot többször bekerülhet, ciklusok végtelen feldolgozást okozhatnak, és a komplexitás elszállhat. Erős alapértelmezett szabály, hogy enqueue pillanatában jelölöd visitednek, nem dequeue pillanatában — így megelőzöd a duplikált enqueue-ket.

2.6 Level-order traversal

A fa szintenkénti bejárása a BFS egyik legtisztább formája. A queue a feldolgozásra váró node-okat tárolja, a gyerekek a jelenlegi réteg hátralévő node-jai mögé kerülnek be, ami természetesen adja a level-by-level kimenetet.

2.7 Távolságértelmezés

Unweighted gráfban vagy állapottérben a BFS a legrövidebb utat találja meg edge-számban vagy lépésszámban. Előbb az összes 0 távolságú állapot kerül sorra, utána az 1 távolságú, majd a 2, és így tovább — ezért amikor először érsz el egy node-ot, az már optimális távolság.

2.8 Multi-source BFS

Néha a BFS nem egy forrásból, hanem több kezdőállapotból indul egyszerre — egyszerűen az összes start állapotot beteszed induláskor a queue-ba. Ez gyakori nearest zero / nearest source feladatoknál, fertőzés vagy tűz terjedési modelleknél és legközelebbi forráshoz mért távolságoknál.

2.9 Queue méret és rétegek

Gyakori BFS minta: elmented a queue aktuális méretét, pontosan ennyi elemet dolgozol fel, utána növeled a depth-et. Így a réteghatárok explicit módon látszanak.

2.10 Felismerési jelek

Queue vagy BFS gondolkodás akkor kell, ha ilyesmit látsz:

• minimum number of moves unweighted közegben,
• level-order traversal,
• process in arrival order,
• terjedés egy forrásból kifelé,
• all neighbors of current states,
• vagy minimum steps egységes átmeneti költséggel.

2.11 Queue vs deque felismerés

Deque kell, ha:

• mindkét végét használod,
• sliding window segédstruktúrát építesz,
• ugyanazzal a struktúrával queue és stack viselkedésre is szükség van,
• vagy későbbi monotonic deque jellegű minta jelenik meg.

---

3. Gyakorlati használat

Mikor jó a queue?

A queue akkor jó, ha a legrégebben várakozó munkaelemnek kell előbb sorra kerülnie.

Tipikus helyzetek:

• request kezelés,
• producer-consumer buffer,
• BFS frontier feldolgozás,
• fa szintenkénti traversal,
• minimum-step feladatok egységes élköltséggel.

Mikor jó a deque?

A deque akkor erős, ha kontrollált művelet kell mindkét végén.

Példák:

• stack és queue szemantika ugyanazzal a struktúrával,
• sliding window maximum,
• candidate-ek rendezett karbantartása,
• strukturált first/back feldolgozás.

Mikor jó a BFS?

A BFS akkor jó első gondolat, ha a kérdés így hangzik:

• "Mi a minimum lépésszám?"
• "Mi a legrövidebb út unweighted gráfban?"
• "Járd be szintenként."
• "Mennyi idő, amíg a hatás mindenhová elér?"

Mikor NEM jó a BFS?

A BFS nem természetes választás, ha:

• a struktúra mély és csak egy út kell,
• weighted shortest path van,
• DFS egyszerűbb és elég,
• vagy a feladat nem rétegtávolságról szól.

Java-specifikus tanács

A legtöbb interjú queue és BFS kódhoz az ArrayDeque az alapértelmezett jó választás.

Hatékony a kétvégi műveleteknél.

A LinkedList is implementálhat Queue-t vagy Deque-ot, de algoritmusfeladatoknál az ArrayDeque általában tisztább és preferáltabb.

Pair-programming nézőpont

Egy erős magyarázat így hangzik:

• "Ez minimum steps feladat unweighted állapottérben, ezért BFS jó választás."
• "Beteszem a start állapotot a queue-ba, enqueue pillanatában visitednek jelölöm, és rétegenként dolgozom fel."
• "Amikor először érem el a célállapotot, az optimális, mert a BFS távolságsorrendet tart."

Ez sokkal jobb, mint annyi, hogy "használok egy queue-t".

Kapcsolódó LeetCode feladatok

• LeetCode #102 — Binary Tree Level Order Traversal — tankönyvi BFS szintkövetéssel.
• LeetCode #994 — Rotting Oranges — multi-source BFS griden.
• LeetCode #1091 — Shortest Path in Binary Matrix — BFS minimum lépésszámhoz.
• LeetCode #542 — 01 Matrix — multi-source BFS minden nullából egyszerre.
• LeetCode #239 — Sliding Window Maximum — monotonic deque range maximumhoz.

---

4. Kódpéldák

Alap példa

Ez a példa sima queue viselkedést mutat.

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueBasicsExample {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();

        queue.offerLast("first");
        queue.offerLast("second");
        queue.offerLast("third");

        while (!queue.isEmpty()) {
            System.out.println(queue.pollFirst());
        }
    }
}

A kimenet a beszúrási sorrendet követi.

Ez a FIFO lényege.

Haladó példa

Ez a példa BFS-sel jár be egy bináris fát szintenként.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class LevelOrderTraversalExample {
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value) {
            this.value = value;
        }
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offerLast(root);

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int count = 0; count < levelSize; count++) {
                TreeNode current = queue.pollFirst();
                currentLevel.add(current.value);

                if (current.left != null) {
                    queue.offerLast(current.left);
                }
                if (current.right != null) {
                    queue.offerLast(current.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }
}

Miért működik?

• a queue a jelenlegi frontier-t tárolja,
• a levelSize lezárja az aktuális réteget,
• a gyerekek már a következő rétegbe kerülnek.

Tipikus hiba

Ez egy klasszikus BFS bug minta.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class BrokenBfsIdea {
    public static void broken(int start, int[][] graph) {
        Deque<Integer> queue = new ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();

        queue.offerLast(start);

        while (!queue.isEmpty()) {
            int current = queue.pollFirst();

            for (int neighbor : graph[current]) {
                if (!visited.contains(neighbor)) {
                    queue.offerLast(neighbor);
                }
            }

            visited.add(current);
        }
    }
}

Miért veszélyes?

• ugyanaz a node többször is bekerülhet, mielőtt egyszer végre ki is vennéd,
• ez felesleges munkát okoz,
• sűrű gráfban a queue is indokolatlanul megnőhet.

Erősebb alapértelmezett szabály, hogy enqueue pillanatában jelölöd visitednek.

Még egy hasznos minta: minimum steps gridben

import java.util.ArrayDeque;
import java.util.Deque;

public class GridBfsExample {
    static class State {
        int row;
        int col;
        int distance;

        State(int row, int col, int distance) {
            this.row = row;
            this.col = col;
            this.distance = distance;
        }
    }

    public static int shortestPath(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (grid[0][0] == 1) {
            return -1;
        }

        boolean[][] visited = new boolean[rows][cols];
        Deque<State> queue = new ArrayDeque<>();
        queue.offerLast(new State(0, 0, 0));
        visited[0][0] = true;

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            State current = queue.pollFirst();

            if (current.row == rows - 1 && current.col == cols - 1) {
                return current.distance;
            }

            for (int[] direction : directions) {
                int nextRow = current.row + direction[0];
                int nextCol = current.col + direction[1];

                boolean inBounds = nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols;
                if (!inBounds || grid[nextRow][nextCol] == 1 || visited[nextRow][nextCol]) {
                    continue;
                }

                visited[nextRow][nextCol] = true;
                queue.offerLast(new State(nextRow, nextCol, current.distance + 1));
            }
        }

        return -1;
    }
}

Ez egy standard BFS template minimum-step state expansion feladatokra.

---

5. Trade-offok

Teljesítménybeli árnyalat

A BFS ereje az, hogy nem oldja meg újra és újra ugyanazokat a sekély állapotokat.

Viszont memóriában drága lehet, ha a frontier szélesre nő.

Ez a breadth alapú trade-off.

Memóriabeli árnyalat

A DFS-hez képest a BFS gyakran több egyidejű állapotot tárol.

Ez akkor elfogadható ár, ha a shortest-path garancia fontos.

Olvashatósági árnyalat

A BFS kód akkor marad tiszta, ha három dolog világos:

• mi a state,
• mikor lesz valami visited,
• és mit jelent egy queue-réteg.

---

6. Gyakori hibák

1. Rossz adatstruktúrát használsz — Ha véletlenül stack-szerű viselkedést kapsz, elvész a BFS rétegsorrendje.
2. Túl későn jelölöd a visited-et — Ha csak dequeue-nál jelölsz, ugyanaz az állapot többször is bekerülhet.
3. Nem kezeled a rétegeket — Ha a kérdés mélységről vagy távolságról szól, a rétegeket vagy a distance-et explicit módon követni kell.
4. Túl kevés state-et tárolsz — Sok BFS feladatban nem elég a pozíció; kellhet kulcs, irány, remaining budget vagy parity is.
5. Weighted shortest pathra BFS-t használsz — A BFS uniform edge costot feltételez. Weighted gráfhoz más algoritmus kellhet.
6. Elfelejted a bounds és blocker ellenőrzést — Grid BFS gyakran ezen csúszik el, nem a queue logikán.
7. Összekevered a queue és deque szerepét — A deque tud queue-ként működni, de a választott végműveleteknek továbbra is a helyes szemantikát kell követniük.

Debug tipp

Kis inputon logold ki a queue rétegenkénti tartalmát.

Ha a node-ok rossz távolsági sorrendben jelennek meg, akkor az enqueue vagy a visited időzítése hibás.

---

7. Mélyebb összefüggések

Miért ad shortest pathot a BFS unweighted feladatokban?

Mert távolságrétegenként jár be.

Az összes d távolságú állapot sorra kerül, mielőtt bármelyik d + 1 távolságú előkerülne.

Ezért amikor először éred el a célt, az már optimális lépésszám.

Ez a BFS legmélyebb alapötlete.

A BFS valójában frontier management

Hasznos mentális modell, hogy a BFS a már ismert, de még fel nem dolgozott állapotok frontier-jét kezeli.

A queue ennek a frontier-nek az időbeli sorrendje.

Ezért érződik hullámszerű terjedésnek.

A multi-source BFS sokak által alulhasznált minta

Rengeteg feladat egyszerűbb lesz, ha nem egy, hanem több forrásból indulsz egyszerre.

Példák:

• legközelebbi szolgáltató,
• fertőzés terjedési ideje,
• bármelyik forrástól mért minimum távolság.

Ha a kérdés a legközelebbi több lehetséges kezdőponthoz viszonyított távolság, a multi-source BFS legyen korai jelölt.

A deque későbbi erősebb mintákhoz vezet

Ebben a fejezetben a deque még csak alapozó szinten jelenik meg.

Később viszont visszajön:

• sliding window maximumnál,
• monotonic deque mintáknál,
• 0-1 BFS-nél,
• és fejlettebb scheduling/state pruning ötleteknél.

Ezért akkor is fontos megtanulni az API-t, ha most a feladat még "csak queue-szerű".

BFS vs DFS kommunikáció

Egy erős mérnök nem csak azt tudja, mi a BFS és mi a DFS.

Hanem azt is, hogy mikor jobb az egyik.

Például:

• BFS, ha a minimum edges számít,
• DFS, ha elég a teljes traversal és a memória profil fontosabb,
• queue, ha az érkezési vagy szintrend lényeges,
• stack, ha a legutóbbi feloldatlan elem számít.

Pair-programming helyzet

Képzelj el egy grid shortest-path feladatot.

Egy erős magyarázat így hangzik:

• a grid unweighted,
• minden lépés egyforma költségű,
• a BFS megőrzi a shortest-step sorrendet,
• a visited megelőzi a duplikátumokat,
• és amikor először érjük el a célt, az biztosan optimális.

Ez rövid, pontos és megnyugtató egy teammate vagy interjúztató számára.

---

8. Interjúkérdések

Q: Miért a BFS a standard megoldás legrövidebb útra unweighted gráfban? — A: Mert a node-okat rétegenként, növekvő távolságsorrendben dolgozza fel, ezért amikor először elérsz egy node-ot, az már a legrövidebb út.

Q: Miért érdemes általában enqueue pillanatában visitednek jelölni? — A: Mert így megelőzöd, hogy ugyanaz az állapot több különböző szülőtől többször is bekerüljön a queue-ba.

Q: Mi a gyakorlati különbség a queue és a deque között? — A: A queue az egyik végén tesz be és a másik végén vesz ki, míg a deque mindkét végén támogatja ezeket a műveleteket.

Q: Mikor rossz választás a BFS? — A: Ha az élköltségek nem egyformák, ha a shortest-step sorrend irreleváns, vagy ha a DFS egyszerűbb és elég.

Q: Miért szokás Java interjúkódban ArrayDeque-ot használni? — A: Mert hatékony kétvégi műveleteket ad, és tiszta queue/deque szemantikát biztosít régi API-k terhei nélkül.

---

9. Fogalomtár

---

10. Cheatsheet

• Queue-t akkor használj, ha a legrégebbi várakozó elem számít először.
• Java interjúkódban ArrayDeque legyen az alapértelmezett queue/deque implementáció.
• A BFS jó első tipp minimum steps feladatokra unweighted állapottérben.
• A visited-et általában enqueue pillanatában érdemes beállítani.
• A level-order traversal a BFS fa-változata.
• A deque mindkét végét támogatja, és később sliding-window mintákban is fontos lesz.
• Ha az élköltségek nem egyformák, a sima BFS könnyen rossz eszköz.
• Mondd ki explicit módon, hogy mit tartalmaz egy BFS state.
• Ha a válasz rétegtávolság, a queue szemantika általában kulcsfontosságú.
• Unweighted feladatban az első BFS-találat a célra jellemzően optimális lépésszámot jelent.