Интерактивен учебник по информатика

Какво е опашка

Опашката е структура от данни с принцип FIFO (First In, First Out) — първият влязъл е първият излязъл. Точно като опашката пред касата: новодошлите се нареждат отзад, обслужваните си тръгват отпред.

Фиг. 1 — Опашка: добавяне от единия край (back), вземане от другия (front)

Ключово

Опашката е „огледалното" на Стек. Стекът е LIFO (последен влязъл, първи излязъл), Опашката е FIFO (първи влязъл, първи излязъл).

Основни операции

Enqueue(x) — добавя x в края.
Dequeue() — маха и връща елемента отпред.
Peek() — поглежда елемента отпред, без да го маха.
Count — колко елемента има в опашката.
Clear() — изпразва опашката.

using System.Collections.Generic;

var queue = new Queue<string>();
queue.Enqueue("Иван");
queue.Enqueue("Мария");
queue.Enqueue("Петър");

Console.WriteLine(queue.Peek());    // Иван  (не го маха)
Console.WriteLine(queue.Dequeue()); // Иван  (маха го)
Console.WriteLine(queue.Dequeue()); // Мария
Console.WriteLine(queue.Count);     // 1

Внимание

Както при Стека, Dequeue и Peek хвърлят грешка при празна опашка. Винаги проверявай queue.Count > 0 преди извикване.

Опашка срещу Стек

	Стек (LIFO)	Опашка (FIFO)
Принцип	Последен влязъл, първи излязъл	Първи влязъл, първи излязъл
Добавяне	Push — отгоре	Enqueue — отзад
Вземане	Pop — отгоре (същия край)	Dequeue — отпред (другия край)
Аналогия	Купчина чинии	Опашка пред касата
Типично приложение	Undo, balanced brackets, рекурсия	BFS, симулация на чакане, задачи в принтер

Класически приложения

1. Симулация на принтерна опашка

Документите се изпращат в реда на пристигане; принтерът ги обработва най-старите първо.

var printQueue = new Queue<string>();
printQueue.Enqueue("домашно.pdf");
printQueue.Enqueue("задача.docx");
printQueue.Enqueue("снимка.jpg");

while (printQueue.Count > 0)
{
    string doc = printQueue.Dequeue();
    Console.WriteLine($"Печатам: {doc}");
}

2. „Горещ картоф" (Hot Potato)

n деца стоят в кръг и си подават топка. На всеки k подавания, детето с топката излиза. Кой остава последен?

static string HotPotato(string[] names, int k)
{
    var q = new Queue<string>();
    foreach (var n in names) q.Enqueue(n);

    while (q.Count > 1)
    {
        // първите k-1 деца получават топката и я подават нататък
        for (int i = 0; i < k - 1; i++)
            q.Enqueue(q.Dequeue());
        // k-тото излиза
        q.Dequeue();
    }
    return q.Dequeue();
}

Console.WriteLine(HotPotato(new[] { "Ани", "Боян", "Вики", "Гошо", "Деси" }, 3));

3. BFS — обхождане на граф/мрежа в ширина

Когато търсиш най-късия път в мрежа (брой стъпки, не разстояние), обикновено ползваш BFS (Breadth-First Search) с опашка. Подробно ще видим това в урока за обхождане на графи.

4. Симулация на чакане

Колко време средно стои клиент на опашка в магазина при дадено темпо на пристигане и обслужване? Това се моделира директно с Queue.

Обхождане без изпразване

За разлика от Стек, foreach върху Queue обхожда елементите от началото към края, без да ги маха:

foreach (var item in queue)
    Console.WriteLine(item);
// извежда от front към back, опашката остава непроменена

Priority Queue — опашка с приоритет

Понякога не искаме „първи дошъл, първи обслужен", а „с най-висок приоритет, първи обслужен" — например спешен случай в болница винаги е пред редовния преглед. За това има PriorityQueue<TElement, TPriority>:

var pq = new PriorityQueue<string, int>();
pq.Enqueue("обикновен случай", 5);
pq.Enqueue("спешен случай", 1);    // по-малко число = по-висок приоритет
pq.Enqueue("прегледи", 3);

while (pq.Count > 0)
    Console.WriteLine(pq.Dequeue());
// спешен случай → прегледи → обикновен случай

Какво трябва да запомниш

Опашка = FIFO (първи влязъл, първи излязъл).
Операции: Enqueue (добави отзад), Dequeue (вземи отпред), Peek (погледни отпред).
Винаги проверявай Count > 0 преди Dequeue / Peek.
Опашка vs Стек: опашката взима от другия край, не от същия.
Класически приложения: BFS, симулация на чакане, задачи в принтер, „горещ картоф".
PriorityQueue — когато редът зависи от приоритет, а не от време на пристигане.