Стек и опашка в Java

Проблем

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

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

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

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

Идеята

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

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

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

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

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

    void push(char c) {
        if (size == items.length) {
            items = Arrays.copyOf(items, size * 2);
        }
        items[size] = c;
        size++;
    }

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

    boolean isEmpty() {
        return size == 0;
    }
}

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

Виж го

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

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

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

static int firstError(String text) {
    CharStack opened = new CharStack();
    for (int i = 0; i < text.length(); i++) {
        char c = text.charAt(i);
        if ("([{".indexOf(c) >= 0) {
            opened.push(c);
        } else if (")]}".indexOf(c) >= 0) {
            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} €"
};
for (String t : templates) {
    int at = firstError(t);
    System.out.println(at < 0 ? "OK" : "грешка на позиция " + at);
}

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

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

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

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

Пробвай

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

System.out.println(firstError("({total)}"));

Отговор

-1

Проблем

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

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

List<String> jobs = new ArrayList<>();
for (int id = 1; id <= 10_000; id++) {
    jobs.add("#" + id);
}
int done = 0;
while (!jobs.isEmpty()) {
    String job = jobs.remove(0);
    done++;
}
System.out.println("обработени: " + done);

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

Изглежда невинно, но jobs.remove(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;

    void enqueue(String job) {
        if (size == items.length) grow();
        int tail = (head + size) % items.length;
        items[tail] = job;
        size++;
    }

    String dequeue() {
        if (size == 0) throw new IllegalStateException();
        String job = items[head];
        items[head] = null;
        head = (head + 1) % items.length;
        size--;
        return job;
    }

    boolean isEmpty() {
        return size == 0;
    }

    private void grow() {
        String[] 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 String toString() {
    String[] shown = new String[items.length];
    for (int i = 0; i < items.length; i++) {
        shown[i] = items[i] == null ? "-" : items[i];
    }
    return "[" + String.join(", ", shown) + "] head=" + head;
}

Виж го

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

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

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

    void enqueue(String job) {
        if (size == items.length) grow();
        int tail = (head + size) % items.length;
        items[tail] = job;
        size++;
    }

    String dequeue() {
        if (size == 0) throw new IllegalStateException();
        String job = items[head];
        items[head] = null;
        head = (head + 1) % items.length;
        size--;
        return job;
    }

    boolean isEmpty() {
        return size == 0;
    }

    private void grow() {
        String[] 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. Едно копиране на поръчка при растене и нито едно при вземане отпред.

JobQueue q = new JobQueue();
for (int id = 101; id <= 103; id++) q.enqueue("#" + id);
System.out.println(q);
System.out.println("доставка: " + q.dequeue());
System.out.println("доставка: " + q.dequeue());
System.out.println(q);
for (int id = 104; id <= 106; id++) q.enqueue("#" + id);
System.out.println(q);
q.enqueue("#107");
System.out.println(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?

JobQueue 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");
System.out.println(q);

Отговор

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

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

[#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;
            items = Arrays.copyOf(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;
}

for (int n : new int[] {1000, 10000}) {
    System.out.println(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() {
    String[] bigger = new String[items.length * 2];
    for (int i = 0; i < size; i++) {
        bigger[i] = items[i];
    }
    items = bigger;
    head = 0;
}

JobQueue 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);
List<String> order = new ArrayList<>();
while (!q.isEmpty()) order.add(q.dequeue());
System.out.println(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 нататък

Стек и опашка

Бисквитки