Стек и опашка в C#

Проблем

Имейлът за поръчката излиза празен

Магазинът праща имейл за всяка поръчка по шаблон: Поръчка {order}: [{items}] (общо {total} €). Шаблоните се пишат на ръка и понякога една скоба не се затваря или се затваря с грешната. Тогава програмата за имейли не попълва нищо и клиентът получава празно писмо.

Искаш преди изпращане да кажеш: „шаблонът е наред“ или „грешка на позиция 25“. Броенето на скобите не стига: в [{items}) отворените са две и затворените са две, а грешката е там.

В урока за колекциите „Стек, опашка и свързан списък“ стекът и опашката бяха готови: Stack<T> и Queue<T>. Тук ги правиш сам, за да видиш какво струва всяка операция и къде е капанът.

Идеята

Стек върху растящ масив

Скобите се затварят в обратен ред: последната отворена се затваря първа. Това е стек: слагаш отгоре и взимаш отгоре.

Отвътре стекът е масив и брояч size:

push пише на място size и увеличава брояча;
pop намалява брояча и връща това, което е там;
когато масивът се напълни, става два пъти по-голям, както в амортизираната сложност.

class CharStack
{
    private char[] items = new char[4];
    private int size = 0;

    public void Push(char c)
    {
        if (size == items.Length)
        {
            Array.Resize(ref items, size * 2);
        }
        items[size] = c;
        size++;
    }

    public char Pop()
    {
        if (size == 0) throw new InvalidOperationException("празен стек");
        size--;
        return items[size];
    }

    public bool IsEmpty => size == 0;
}

И push, и pop работят само с края на масива. Нищо не се мести, затова двете са O(1) (push е O(1) средно заради растенето).

Виж го

Проверката на шаблона

Минаваш по шаблона знак по знак:

отваряща скоба отива в стека;
затваряща взима горната от стека и проверява, че е от същия вид;
ако стекът е празен при затваряща или не е празен накрая, шаблонът е грешен.

static int FirstError(string text)
{
    var opened = new CharStack();
    for (int i = 0; i < text.Length; i++)
    {
        char c = text[i];
        if ("([{".Contains(c))
        {
            opened.Push(c);
        }
        else if (")]}".Contains(c))
        {
            if (opened.IsEmpty) return i;
            if ("([{".IndexOf(opened.Pop()) != ")]}".IndexOf(c)) return i;
        }
    }
    return opened.IsEmpty ? -1 : text.Length;
}

string[] templates =
[
    "Поръчка {order}: [{items}] (общо {total} €)",
    "Поръчка {order}: [{items}) (общо {total} €)",
    "Поръчка {order}: [{items}] (общо {total} €"
];
foreach (string t in templates)
{
    int at = FirstError(t);
    Console.WriteLine(at < 0 ? "OK" : $"грешка на позиция {at}");
}

OK
грешка на позиция 25
грешка на позиция 42

Във втория шаблон ) идва, когато отгоре в стека е [: грешка на позиция 25. В третия ( не се затваря и грешката е в края, на позиция 42, колкото е дължината на текста.

По-точно, за любопитните

Истински проверител на JSON прескача и скобите вътре в текст в кавички: "[1" не отваря нищо. Тогава стекът пази и „сега съм в текст“. Същото е с таговете в HTML: стекът пази имената на отворените тагове, а </div> трябва да срещне отгоре div.

Пробвай

Предвиди изхода

Console.WriteLine(FirstError("({total)}"));

Отговор

-1

Проблем

Сутрешната опашка за доставки

В 8 сутринта в системата чакат 10 000 заявки за доставка. Куриерите ги взимат една по една, най-старата първа: това е опашка. Някой я е написал с обикновен списък:

var jobs = new List<string>();
for (int id = 1; id <= 10_000; id++)
{
    jobs.Add("#" + id);
}
int done = 0;
while (jobs.Count > 0)
{
    string job = jobs[0];
    jobs.RemoveAt(0);
    done++;
}
Console.WriteLine($"обработени: {done}");

обработени: 10000

Изглежда невинно, но jobs.RemoveAt(0) маха от място 0 на масив. Всички след първия се местят с едно място напред. При 10 000 чакащи първото вземане мести 9 999, второто 9 998… Заедно са около 50 милиона премествания само за да вземеш всеки по веднъж.

Идеята

Пръстенов буфер: мести се head, не поръчките

Не мести поръчките. Мести показалеца към първата.

head е мястото на първата поръчка, а size е колко чакат.
Вземането чете items[head], изчиства мястото и мести head с едно напред. Никой друг не се мести.
Новата поръчка отива на tail = (head + size) % места. Остатъкът при деление прави масива на кръг: след последното място идва първото. Празните места отпред, които вземането е освободило, се ползват пак.
Когато всички места са заети, grow прави масив два пъти по-голям и копира поръчките в реда на опашката, от head нататък. После head е 0.

Такъв масив, в който краят продължава от началото, се казва пръстенов буфер (ring buffer или circular buffer).

class JobQueue
{
    private string?[] items = new string?[4];
    private int head = 0;
    private int size = 0;

    public void Enqueue(string job)
    {
        if (size == items.Length) Grow();
        int tail = (head + size) % items.Length;
        items[tail] = job;
        size++;
    }

    public string Dequeue()
    {
        if (size == 0)
            throw new InvalidOperationException();
        string job = items[head]!;
        items[head] = null;
        head = (head + 1) % items.Length;
        size--;
        return job;
    }

    public bool IsEmpty => size == 0;

    private void Grow()
    {
        var bigger = new string?[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[(head + i) % items.Length];
        }
        items = bigger;
        head = 0;
    }
}

За да виждаш какво е вътре, класът има и метод за печат:

public override string ToString() =>
    $"[{string.Join(", ", items.Select(s => s ?? "-"))}] head={head}";

Виж го

head, tail и връщането в началото

Три поръчки влизат, две излизат, после още три. Последната от тях не е след края на масива, а на място 0. После масивът е пълен и седмата поръчка го кара да расте:

class JobQueue
{
    private string?[] items = new string?[4];
    private int head = 0;
    private int size = 0;

    public void Enqueue(string job)
    {
        if (size == items.Length) Grow();
        int tail = (head + size) % items.Length;
        items[tail] = job;
        size++;
    }

    public string Dequeue()
    {
        if (size == 0)
            throw new InvalidOperationException();
        string job = items[head]!;
        items[head] = null;
        head = (head + 1) % items.Length;
        size--;
        return job;
    }

    public bool IsEmpty => size == 0;

    private void Grow()
    {
        var bigger = new string?[items.Length * 2];
        for (int i = 0; i < size; i++)
        {
            bigger[i] = items[(head + i) % items.Length];
        }
        items = bigger;
        head = 0;
    }
}

Стъпка по стъпка, с думи

Опашка за доставки върху масив с 4 места. head е мястото на първата поръчка, size е колко чакат.
Enqueue: новата поръчка отива на (head + size) % 4. Три поръчки заемат места 0, 1 и 2.
Dequeue взима поръчката на head и мести head напред. Никой друг не се мести: #103 си стои на място 2.
#104: (2 + 1) % 4 = 3, последното място на масива.
#105: (2 + 2) % 4 = 0. Краят на масива се връща в началото и празните места отпред се ползват пак.
#106 отива на място 1. Вече са 4 от 4: масивът е пълен, а първият на опашката е на място 2.
#107 не се побира. Grow прави 8 места и копира в реда на опашката, от head нататък: #103, #104, #105, #106. head става 0.
#107 отива на място 4. Едно копиране на поръчка при растене и нито едно при вземане отпред.

var q = new JobQueue();
for (int id = 101; id <= 103; id++) q.Enqueue("#" + id);
Console.WriteLine(q);
Console.WriteLine($"доставка: {q.Dequeue()}");
Console.WriteLine($"доставка: {q.Dequeue()}");
Console.WriteLine(q);
for (int id = 104; id <= 106; id++) q.Enqueue("#" + id);
Console.WriteLine(q);
q.Enqueue("#107");
Console.WriteLine(q);

[#101, #102, #103, -] head=0
доставка: #101
доставка: #102
[-, -, #103, -] head=2
[#105, #106, #103, #104] head=2
[#103, #104, #105, #106, #107, -, -, -] head=0

Виж третия ред на изхода: [#105, #106, #103, #104] head=2. Първата на опашката е #103, на място 2, а #105 и #106 са отпред, защото там е имало свободни места. Подредбата в масива не е подредбата на опашката. Затова grow не копира едно към едно.

Пробвай

Къде отиват #205 и #206?

var q = new JobQueue();
for (int id = 201; id <= 204; id++) q.Enqueue("#" + id);
q.Dequeue();
q.Dequeue();
q.Dequeue();
q.Enqueue("#205");
q.Enqueue("#206");
Console.WriteLine(q);

Отговор

[#204, #205, #206, -] head=0

[-, -, -, #204, #205, #206, -, -] head=3

[#205, #206, -, #204] head=3

Пробвай

Попълни

Новата поръчка отива на място:

int tail = (head + size) % ;

Идеята

Колко струва

Броим преместванията на вече записани заявки: копията при растене и местенето напред при вземане от място 0. И двете опашки започват с 4 места и се удвояват. 10 000 заявки влизат, после всички излизат:

static long ShiftMoves(int n)
{
    int[] items = new int[4];
    int size = 0;
    long moves = 0;
    for (int job = 1; job <= n; job++)
    {
        if (size == items.Length)
        {
            moves += size;
            Array.Resize(ref items, size * 2);
        }
        items[size++] = job;
    }
    while (size > 0)
    {
        for (int i = 1; i < size; i++)
        {
            items[i - 1] = items[i];
            moves++;
        }
        size--;
    }
    return moves;
}

static long RingMoves(int n)
{
    int[] items = new int[4];
    int head = 0, size = 0;
    long moves = 0;
    for (int job = 1; job <= n; job++)
    {
        if (size == items.Length)
        {
            int[] bigger = new int[size * 2];
            for (int i = 0; i < size; i++)
            {
                bigger[i] = items[(head + i) % items.Length];
                moves++;
            }
            items = bigger;
            head = 0;
        }
        items[(head + size) % items.Length] = job;
        size++;
    }
    while (size > 0)
    {
        head = (head + 1) % items.Length;
        size--;
    }
    return moves;
}

foreach (int n in new[] { 1000, 10000 })
{
    Console.WriteLine($"{n}: списък {ShiftMoves(n)}, пръстен {RingMoves(n)}");
}

1000: списък 500520, пръстен 1020
10000: списък 50011380, пръстен 16380

Пусни го и до 100 000:

Списък: махни от място 0 O(n²)
Пръстенов буфер O(n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Списък: махни от място 0	57	500 520	50 011 380	≈ 5 001 138 000
Пръстенов буфер	12	1020	16 380	131 068

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

При 10 000 заявки списъкът прави 50 011 380 премествания, а пръстенът 16 380, и всички те са от растенето. Вземане от място 0 е O(n), затова n вземания са O(n²). В пръстена вземането е O(1), а добавянето е O(1) средно, като стека.

По-точно, за любопитните

Как е в езиците:

Java: ArrayDeque е пръстенов буфер: масив elements и индекси head и tail. Едно място винаги остава празно, за да се различи „празна“ (head == tail) от „пълна“, затова масивът отначало е с 17 места за 16 елемента. Когато се напълни, при малък масив расте малко над два пъти, а при голям с 50%.
C#: Queue<T> е пръстенов буфер с _array, _head, _tail и _size. Започва с 4 места и при пълен масив го удвоява. Stack<T> е масив, който също се удвоява.
Python: collections.deque не е пръстенов буфер, а свързан списък от блокове по 64 места. Затова и двата края са O(1). list.pop(0) е O(n), точно като в проблема.
JavaScript: вградена опашка няма. shift() мести всички елементи на масива. V8 понякога го прави бързо, като премества началото на масива, вместо да мести елементите, но при големи масиви не, и не е обещано. За голяма опашка се пише пръстен като тук или опашка от възли.

Някои пръстени пазят tail вместо size, а други и двете. Това е само друг запис на същото: tail = (head + size) % места.

Пробвай

Намери грешката

Някой е написал Grow по-кратко. Поръчките до растенето излизат наред, а после разбъркано:

private void Grow()
{
    var bigger = new string?[items.Length * 2];
    for (int i = 0; i < size; i++)
    {
        bigger[i] = items[i];
    }
    items = bigger;
    head = 0;
}

var q = new JobQueue();
for (int id = 101; id <= 103; id++) q.Enqueue("#" + id);
q.Dequeue();
q.Dequeue();
for (int id = 104; id <= 107; id++) q.Enqueue("#" + id);
var order = new List<string>();
while (!q.IsEmpty) order.Add(q.Dequeue());
Console.WriteLine(string.Join(" ", order));

#105 #106 #103 #104 #107

На кой ред е грешката?

Избери реда с грешката.

Упражнение

Последните 5 реда от лога

Реши задачата в редактора си.

Последните 5 реда. Сървърът на магазина пише ред в лога за всяко действие. При грешка искаш да видиш последните 5 реда, а не целия лог. Напиши LastLines с пръстен от 5 места, който никога не расте: докато има място, редът влиза на (head + size) % 5; когато е пълен, новият ред пише върху най-стария (на head), а head се мести напред. Метод Lines() връща редовете от най-стария към най-новия. Подай му осемте реда:

09:00 вход: ана
09:02 кошница: +2
09:03 плащане: 48 €
09:05 изход: ана
09:07 вход: иво
09:08 търсене: кафе
09:09 кошница: +1
09:11 плащане: 12 €

Последните 5:
09:05 изход: ана
09:07 вход: иво
09:08 търсене: кафе
09:09 кошница: +1
09:11 плащане: 12 €

Още задачи

Скоби и тагове. Разшири проверката на шаблона и за таговете <b>…</b> и <i>…</i>: стекът пази имената на отворените тагове.
Опашка, която се свива. Ако след сутрешния пик в опашката с 8192 места чакат 10 заявки, паметта стои празна. Накарай опашката да намалява масива наполовина, когато е пълна под една четвърт. Защо не под половината?
Стек от две опашки. Направи стек само с две свои опашки. Колко струва pop?

Тест

Провери се

1. Защо стекът проверява скобите, а не просто брои отворените и затворените?Защото броенето е по-бавноЗащото броят не работи с повече от 10 скобиЗащото последната отворена скоба трябва да се затвори първа, а броят не знае коя е последната

2. Опашка с 10 000 чакащи е върху обикновен списък и всяко вземане е от място 0. Колко премествания струва едно вземане отпред?Около толкова, колкото чакат след него: всички се местят с едно място напредЕдноНито едно

3. Пръстенов буфер с 8 места: head = 6, size = 3. На кое място отива новата поръчка?На 0На 9На 1

4. Пръстеновият буфер е пълен и трябва да расте. Защо grow не може просто да копира items[0], items[1]… в новия масив?Защото новият масив е по-малъкМоже: местата са същитеЗащото първият на опашката е на head, не на 0; копирането трябва да е в реда на опашката, от head нататък

Стек и опашка

Бисквитки