Стек, опашка и свързан списък

Проблем

„Отмени“ отменя не това

Текстовият редактор пази действията в списък. Ctrl+Z трябва да отмени последното, но отменя първото:

actions = []
actions.append("Въведе текст")
actions.append("Удебели заглавието")
actions.append("Вмъкна снимка")

# Ctrl+Z: отмени последното действие.
undone = actions.pop(0)
print("Отменено:", undone)
print("Остава:", actions)

Изход

Отменено: Въведе текст
Остава: ['Удебели заглавието', 'Вмъкна снимка']

Поправката е actions.pop(). Но всеки, който пипа този код, трябва да помни от кой край се маха. А при касата в магазина е обратното: обслужва се първият, който е дошъл. Има ли колекция, която сама знае от кой край?

Идеята

Стек: последното най-отгоре

Стекът е като купчина чинии. Слагаш отгоре и взимаш отгоре. Последното сложено излиза първо. На английски това е LIFO: last in, first out.

Бутонът „Назад“ в браузъра е стек:

history = []
history.append("Начало")
history.append("Лаптопи")
history.append("Лаптоп 14 инча")
print("Сега:", history[-1])

history.pop()
print("Назад:", history[-1])
print(history)

Изход

Сега: Лаптоп 14 инча
Назад: Лаптопи
['Начало', 'Лаптопи']

Отделен клас за стек в Python няма: списъкът е стек, ако слагаш и взимаш само от края.

• append слага отгоре, pop() без индекс маха и връща горния, history[-1] само поглежда горния.
• Отгоре е краят на списъка. И двете операции са бързи, защото в края нищо не се мести.
• print печата стека отдолу нагоре: горният е последен.

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

• pop() и [-1] на празен списък спират програмата с IndexError. Затова първо провери. if history: значи „ако списъкът не е празен“: празният списък в if и while е като False.

history = []
if history:
    print("Сега:", history[-1])
else:
    print("Няма предишна страница.")
try:
    history.pop()
except IndexError as e:
    print(f"IndexError: {e}")

Изход

Няма предишна страница.
IndexError: pop from empty list

Пробвай

Какво остава за отмяна?

Какво ще отпечата програмата?

undo = []
undo.append("шрифт")
undo.append("цвят")
undo.append("размер")
undo.pop()
undo.append("подчертаване")
while len(undo) > 0:
    print(undo.pop())

Отговор

подчертаване
цвят
шрифт

шрифт
цвят
подчертаване

подчертаване
размер
цвят
шрифт

шрифт
цвят
размер

Провери

Идеята

Опашка: първият дошъл

Опашката е като на касата. Нареждаш се отзад, обслужва се първият. На английски е FIFO: first in, first out.

Заявките към принтера чакат на опашка:

from collections import deque

printer = deque()
printer.append("фактура.pdf")
printer.append("договор.docx")
printer.append("снимка.jpg")
print("Следващ:", printer[0])

while len(printer) > 0:
    print("Печатам", printer.popleft())
print("Опашка:", printer)

Изход

Следващ: фактура.pdf
Печатам фактура.pdf
Печатам договор.docx
Печатам снимка.jpg
Опашка: deque([])

• deque е в модула collections, затова файлът започва с from collections import deque. Името идва от double-ended queue, опашка с два края.
• append слага отзад, popleft маха и връща първия, printer[0] поглежда първия.
• Защо не списък с pop(0)? pop(0) мести всички останали с едно място напред, като вмъкването отпред в урока за списъците. deque маха отпред, без да мести нищо.

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

• popleft на празна опашка спира програмата с IndexError. deque може и да е стек: append и pop работят от десния край.

from collections import deque

clients = deque()
clients.append("Клиент 1")
clients.append("Клиент 2")
print("Последен:", clients.pop())
print("Обслужен:", clients.popleft())
try:
    clients.popleft()
except IndexError as e:
    print(f"IndexError: {e}")

Изход

Последен: Клиент 2
Обслужен: Клиент 1
IndexError: pop from an empty deque

• Има и queue.Queue, но той е за програми с няколко нишки, които си подават задачи. За обикновена опашка ползвай deque.

Пробвай

Следващият на касата

Касиерката вика следващия клиент. Кой метод го взима от опашката?

from collections import deque

checkout = deque()
checkout.append("Иван")
checkout.append("Мария")
client = checkout.()
print(f"Заповядай, {client}")

Провери

Виж го

Свързан списък отвътре

Списъкът пази елементите един до друг в масив. Затова вмъкването отпред мести всички останали. Има и друг начин: всеки елемент е в отделен обект, който пази стойността и стрелка към следващия. Такъв обект се казва възел (node):

class Node:
    def __init__(self, value, next):
        self.value = value
        self.next = next

Списък от възли се казва свързан списък. Достатъчно е да пазиш първия възел, head. Всеки следващ се намира по стрелката next. Последният сочи None.

head = None
head = Node("Кафе", head)
head = Node("Мляко", head)
head = Node("Хляб", head)

n = head
while n is not None:
    print(n.value)
    n = n.next

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

1. Списъкът е празен: head е None.
2. Нов възел: next е старият head (None), а head се премества на възела.
3. Вторият възел сочи към първия. Нищо не се мести в паметта, сменят се само стрелките.
4. Третият възел също влиза отпред: последното добавено е първо.
5. n тръгва от head и печата всеки възел.
6. n стига None: цикълът спира.

• Вмъкване отпред: нов възел, чийто next сочи стария първи, и head сочи новия. Две стрелки, без да местиш нищо.
• Обхождане: тръгваш от head и минаваш по next, докато не стигнеш None.
• Цената: възлите нямат индекси. До петия елемент се стига, като минеш през първите четири.

Идеята

deque и кое кога

Готов свързан списък като класа Node в Python няма. Има deque: отвътре той е свързан списък, но всеки възел пази не един, а цял блок от елементи. Затова е бърз и в двата края: append и appendleft, pop и popleft, [0] и [-1]:

from collections import deque

route = deque()
route.append("Пловдив")
route.append("Стара Загора")
route.appendleft("София")
route.append("Бургас")
print(list(route))

route.remove("Стара Загора")
print("След промяната:", list(route))
print("От", route[0], "до", route[-1])

Изход

['София', 'Пловдив', 'Стара Загора', 'Бургас']
След промяната: ['София', 'Пловдив', 'Бургас']
От София до Бургас

Кое кога:

• Списък по номер: list. Това е обичайният избор.
• Стек: list с append и pop.
• Опашка: deque с append и popleft.

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

• list(route) прави обикновен списък от опашката, за да се отпечата като списък. Само print(route) дава deque([...]).
• В CPython всеки блок на deque пази 64 елемента, а блоковете са свързани в двете посоки, към следващия и към предишния. Затова route[0] и route[-1] са бързи, а елемент от средата на голяма опашка е бавен: до него се стига през блоковете.
• Възелът от тази карта има само next. Такъв списък се казва едносвързан.

Пробвай

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

Функцията трябва да преброи възлите. За списъка Хляб → Мляко → Кафе връща 2 вместо 3. А за празен списък спира с AttributeError. На кой ред е грешката?

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

1def count(head):2 count = 03 n = head4 while n.next is not None:5 count += 16 n = n.next7 return count

Провери

Упражнение

Стекове и опашки в работа

Реши задачите в редактора си. Колекцията е поле на класа с _ отпред.

1. Влакче. Клас Train с методи add_wagon(wagon) и remove_wagon(). Влакът е стек: откача се последният закачен вагон. remove_wagon() връща откачения вагон или None, ако няма. Добави count(). Закачи три вагона и откачи два.

Изход

Откачен: Вагон 3
Откачен: Вагон 2
Вагони: 1

2. Маршрут на автобус. Клас BusRoute с опашка от спирки и методи add_stop(stop) и get_next_stop(), който връща следващата спирка или None, ако маршрутът е свършил. Добави „Централна гара“, „НДК“, „Студентски град“ и обходи маршрута.

Изход

Следваща спирка: Централна гара
Следваща спирка: НДК
Следваща спирка: Студентски град
Край на маршрута.

3. Борсов тикер. Клас StockTicker пази последните N цени на една акция. Конструкторът получава символа и N. update_price(price) добавя цена, а ако цените станат повече от N, маха най-старата. Добави get_last_price() и average() за пазените цени. За SAP с N = 3 подай цените 150, 152, 149 и 155. Подсказка: deque(maxlen=3) сама маха най-старата, когато станат повече от 3. Цените печатай с два знака след точката.

Изход

SAP: последна цена 155.00 €
Средно за последните 3: 152.00 €

4. Скобите в баланс. Редакторът на код проверява дали скобите (), [] и {} са затворени в правилния ред. Напиши is_balanced(text) със стек: при отваряща скоба я слагаш в стека, при затваряща махаш горната и проверяваш дали е от същия вид. Накрая стекът трябва да е празен. Прочети три реда.

Вход

(1 + [2 * 3])
(1 + 2]
((5)

Изход

(1 + [2 * 3]) -> да
(1 + 2] -> не
((5) -> не

5. Свой свързан списък. Клас MyLinkedList с възлите от урока и методи add(value) (в края), remove(value), contains(value), size() и __str__(). При remove намери възела преди търсения и пренасочи неговия next. Отделно провери случая, когато се маха първият.

Изход

[Фактура, Отчет, Среща]
Има ли Отчет: True
След триене: [Фактура, Среща]
Размер: 2

Още задачи

• Отмени и Повтори. Пази два стека: undo и redo. Ново действие отива в undo и изчиства redo. „Отмени“ мести горното от undo в redo, а „Повтори“ го връща обратно.
• Думите наобратно. Прочети изречение и го отпечатай с думите в обратен ред, като минеш през стек: „Днес е петък“ става „петък е Днес“.
• Две каси. Клиентите идват един по един и отиват на касата с по-къса опашка. Отпечатай кой на коя каса е обслужен.
• Обърни свързания списък. Добави на MyLinkedList метод reverse(), който обръща стрелките, без да прави нови възли.

Тест

Провери се

1. В стек се слагат А, после Б, после В. Кое излиза първо при pop?

АБВ

2. Кое е за опашка?

Бутонът „Назад“ в браузъраЗаявките към принтер, които се печатат по реда на пристиганеОтмяната на последното действие

3. Какво става при popleft() на празна deque?

Програмата спира с IndexErrorВръща NoneВръща 0

4. Защо вмъкването в началото на свързан списък е бързо?

Защото списъкът се подрежда самЗащото се прави нов възел и се местят две стрелки, без да се пипат останалите елементиЗащото елементите стоят един до друг в паметта

5. Кое е бавно при свързан списък?

Взимане на елемент по номер, например петстотнияДобавяне в началотоМахане на първия елемент

Провери

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