Стек и опашка

Код на:JavaC#PythonJavaScript

Накратко: Стекът дава последния добавен елемент (LIFO), а опашката първия (FIFO); стекът върху растящ масив и опашката като пръстенов буфер правят всяка операция за O(1), а добавянето е O(1) средно.

Проблем

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

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

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

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

Идеята

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

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

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

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

class CharStack:
    def __init__(self):
        self.items = [None] * 4
        self.size = 0

    def push(self, c):
        if self.size == len(self.items):
            self.items += [None] * self.size
        self.items[self.size] = c
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise IndexError("празен стек")
        self.size -= 1
        return self.items[self.size]

    def is_empty(self):
        return self.size == 0

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

В Python list вече е такъв растящ масив, а append и pop() са точно push и pop. Тук масивът е с фиксиран размер, [None] * 4, за да се види какво прави list вместо теб.

Виж го

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

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

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

def first_error(text):
    opened = CharStack()
    for i, c in enumerate(text):
        if c in "([{":
            opened.push(c)
        elif c in ")]}":
            if opened.is_empty():
                return i
            if "([{".index(opened.pop()) != ")]}".index(c):
                return i
    return -1 if opened.is_empty() else len(text)

templates = [
    "Поръчка {order}: [{items}] (общо {total} €)",
    "Поръчка {order}: [{items}) (общо {total} €)",
    "Поръчка {order}: [{items}] (общо {total} €",
]
for t in templates:
    at = first_error(t)
    print("OK" if at < 0 else f"грешка на позиция {at}")

Изход

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

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

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

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

Пробвай

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

print(first_error("({total)}"))

Отговор

-1

7

9

Провери

Проблем

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

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

jobs = []
for id in range(1, 10_001):
    jobs.append(f"#{id}")
done = 0
while jobs:
    job = jobs.pop(0)
    done += 1
print(f"обработени: {done}")

Изход

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

Изглежда невинно, но jobs.pop(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:
    def __init__(self):
        self.items = [None] * 4
        self.head = 0
        self.size = 0

    def enqueue(self, job):
        if self.size == len(self.items):
            self.grow()
        tail = (self.head + self.size) % len(self.items)
        self.items[tail] = job
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("празна опашка")
        job = self.items[self.head]
        self.items[self.head] = None
        self.head = (self.head + 1) % len(self.items)
        self.size -= 1
        return job

    def is_empty(self):
        return self.size == 0

    def grow(self):
        n = len(self.items)
        bigger = [None] * (n * 2)
        for i in range(self.size):
            bigger[i] = self.items[(self.head + i) % n]
        self.items = bigger
        self.head = 0

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

def __str__(self):
    shown = ", ".join(s or "-" for s in self.items)
    return f"[{shown}] head={self.head}"

Виж го

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

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

class JobQueue:
    def __init__(self):
        self.items = [None] * 4
        self.head = 0
        self.size = 0

    def enqueue(self, job):
        if self.size == len(self.items):
            self.grow()
        tail = (self.head + self.size) % len(self.items)
        self.items[tail] = job
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            raise IndexError("празна опашка")
        job = self.items[self.head]
        self.items[self.head] = None
        self.head = (self.head + 1) % len(self.items)
        self.size -= 1
        return job

    def is_empty(self):
        return self.size == 0

    def grow(self):
        n = len(self.items)
        bigger = [None] * (n * 2)
        for i in range(self.size):
            bigger[i] = self.items[(self.head + i) % n]
        self.items = bigger
        self.head = 0

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

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

q = JobQueue()
for id in range(101, 104):
    q.enqueue(f"#{id}")
print(q)
print(f"доставка: {q.dequeue()}")
print(f"доставка: {q.dequeue()}")
print(q)
for id in range(104, 107):
    q.enqueue(f"#{id}")
print(q)
q.enqueue("#107")
print(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?

q = JobQueue()
for id in range(201, 205):
    q.enqueue(f"#{id}")
q.dequeue()
q.dequeue()
q.dequeue()
q.enqueue("#205")
q.enqueue("#206")
print(q)

Отговор

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

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

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

Провери

Пробвай

Попълни

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

tail = (self.head + self.size) % 

Провери

Идеята

Колко струва

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

def shift_moves(n):
    items = [None] * 4
    size = 0
    moves = 0
    for job in range(1, n + 1):
        if size == len(items):
            moves += size
            items += [None] * size
        items[size] = job
        size += 1
    while size > 0:
        for i in range(1, size):
            items[i - 1] = items[i]
            moves += 1
        size -= 1
    return moves


def ring_moves(n):
    items = [None] * 4
    head = size = 0
    moves = 0
    for job in range(1, n + 1):
        if size == len(items):
            bigger = [None] * (size * 2)
            for i in range(size):
                bigger[i] = items[(head + i) % len(items)]
                moves += 1
            items = bigger
            head = 0
        items[(head + size) % len(items)] = job
        size += 1
    while size > 0:
        head = (head + 1) % len(items)
        size -= 1
    return moves

for n in [1000, 10000]:
    print(f"{n}: списък {shift_moves(n)}, пръстен {ring_moves(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 по-кратко. Поръчките до растенето излизат наред, а после разбъркано:

def grow(self):
    n = len(self.items)
    bigger = [None] * (n * 2)
    for i in range(self.size):
        bigger[i] = self.items[i]
    self.items = bigger
    self.head = 0

q = JobQueue()
for id in range(101, 104):
    q.enqueue(f"#{id}")
q.dequeue()
q.dequeue()
for id in range(104, 108):
    q.enqueue(f"#{id}")
order = []
while not q.is_empty():
    order.append(q.dequeue())
print(" ".join(order))

Изход

#105 #106 #103 #104 #107

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

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

1def grow(self):2 n = len(self.items)3 bigger = [None] * (n * 2)4 for i in range(self.size):5 bigger[i] = self.items[i]6 self.items = bigger7 self.head = 0

Провери

Упражнение

Последните 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 нататък

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Big-O: как расте работата · Сложност по памет · Амортизирана сложност · Динамичен масив отвътре
• Продължава в: Хеш таблица · BFS: най-малко спирки
• Задачи по темата: Структури от данни