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

Какво е стек

Стекът е структура от данни с принцип LIFO (Last In, First Out) — последният влязъл е първият излязъл. Представи си купчина чинии: новата сложена най-отгоре, вземаш първо нея.

Фиг. 1 — Push добавя нов елемент отгоре; Pop връща и маха най-горния

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

Push(x) — слага x отгоре.
Pop() — маха и връща най-горния.
Peek() — само поглежда най-горния, без да го маха.
Count — колко елемента има в стека.
Clear() — изпразва стека.

using System.Collections.Generic;

var stack = new Stack<int>();
stack.Push(10);
stack.Push(20);
stack.Push(30);

Console.WriteLine(stack.Peek());  // 30 (не го маха)
Console.WriteLine(stack.Pop());   // 30 (маха го)
Console.WriteLine(stack.Pop());   // 20
Console.WriteLine(stack.Count);   // 1

Внимание

Pop и Peek хвърлят грешка при празен стек. Винаги проверявай stack.Count > 0 преди извикване.

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

1. Обръщане на низ

var stack = new Stack<char>();
foreach (char c in "програма") stack.Push(c);

while (stack.Count > 0)
    Console.Write(stack.Pop());
// амаргорп

2. Балансирани скоби — ( ), [ ], { }

Класически алгоритъм: за всяка отваряща скоба — push; за всяка затваряща — pop и сравни. Накрая стекът трябва да е празен.

static bool IsBalanced(string s)
{
    var st = new Stack<char>();
    foreach (char c in s)
    {
        if (c == '(' || c == '[' || c == '{') st.Push(c);
        else if (c == ')' || c == ']' || c == '}')
        {
            if (st.Count == 0) return false;
            char open = st.Pop();
            bool match =
                (c == ')' && open == '(') ||
                (c == ']' && open == '[') ||
                (c == '}' && open == '{');
            if (!match) return false;
        }
    }
    return st.Count == 0;
}

Console.WriteLine(IsBalanced("(a+b)*[c-d]"));     // true
Console.WriteLine(IsBalanced("(a+b]"));           // false
Console.WriteLine(IsBalanced("(()"));             // false

3. Undo / Redo

Текстовите редактори пазят историята на действията в стек. Ctrl+Z прави Pop и връща предишното състояние.

4. Извиквания на методи

Зад кулисите процесорът пази информация за всеки извикан метод в стек (call stack). Когато метод приключи — pop, и се връщаме на предишното място. Това е защо рекурсията може да доведе до StackOverflowException!

Стек vs опашка (Queue)

За пълнота: Queue<T> е „опашка" — принцип FIFO (First In, First Out). Първият дошъл е първият обслужен. Ще се занимаваме повече с нея в 12. клас.

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

Стек = LIFO (последен влязъл, първи излязъл).
Операции: Push (добави отгоре), Pop (вземи отгоре), Peek (погледни).
Проверявай Count > 0 преди Pop/Peek.
Класически приложения: undo, балансирани скоби, обхождане наобратно, рекурсия.