Стеки в Python

1.

СТЕКИ В PYTHON
Материал подготовили:
Будник И.А.
Волков А.Ю.
Лошанков А.О.

2.

ПОНЯТИЕ СТЕКА
Стек в Python – это линейная структура данных, в которой данные
расположены объектами друг над другом.
Он хранит данные в режиме LIFO (Last in First Out – Последний
зашел - первый вышел).
Данные хранятся в том же порядке, в каком на кухне тарелки располагаются одна
над другой. Мы всегда выбираем последнюю тарелку из стопки тарелок.
В стеке новый элемент вставляется с одного конца, и элемент может быть удален
только с этого конца.
2

3.

ПОНЯТИЕ СТЕКА
Простым примером стека является функция «Отменить» в редакторе
(CTRL+Z для Windows или COMMAD+Z для Мас).
Функция отмены работает с последним выполненным нами событием.
Мы можем выполнять две операции в стеке – PUSH (добавить
элемент) и POP (удалить элемент).
3

4.

РЕАЛИЗАЦИЯ СТЕКА
Python предлагает различные способы
реализации стека:
1. список;
2. Класс deque из библиотеки collections;
3. Класс LifoQueue из библиотеки queue.
4

5.

РЕАЛИЗАЦИЯ СТЕКА:
СПИСОК
Список Python можно использовать как стек. Он
использует метод append() для вставки
элементов, где стек использует метод push().
Для списков также есть метод pop() для удаления
последнего элемента.
Но в списке есть недостаток: он становится
медленнее по мере роста.
Если список растет и выходит за пределы блока
памяти, Python выделяет некоторую память.
5

6.

РЕАЛИЗАЦИЯ СТЕКА:
СПИСОК
Пример:
Объявляем список, который будем
использовать в качестве стека
Добавляем в стек элементы
Выводим стек
Последовательно очищаем стек
Выводим стек
6

7.

РЕАЛИЗАЦИЯ СТЕКА:
DEQUE
Модуль collections предоставляет класс deque,
который используется для создания стеков Python.
Deque (дек) переводится как «колода», что
означает «двусторонняя очередь».
Двухсторонняя очередь может быть
предпочтительнее списка, поскольку она
выполняет операции добавления и извлечения
быстрее, чем список.
7

8.

РЕАЛИЗАЦИЯ СТЕКА:
DEQUE
Пример:
Из библиотеки collections
импортируем класс deque
Объявляем переменную в качестве
класса deque – это и будет стек
Добавляем в стек элементы
Выводим стек
Последовательно очищаем стек
8

9.

РЕАЛИЗАЦИЯ СТЕКА:
LIFOQUEUE
Модуль очереди queue имеет очередь LIFO,
которая совпадает по структуре со стеком.
Используют класс LifoQueue
Обычно очередь использует метод put() для
добавления данных (соответствует push) и
метод get() (соответствует pop) для
получения данных.
9

10.

РЕАЛИЗАЦИЯ СТЕКА:
LIFOQUEUE
Методы:
empty() – если очередь пуста, возвращает true; в противном случае
вернется false.
maxsize() – этот метод используется для установки максимального
количества элементов, разрешенных в очереди.
get() – возвращает и удаляет элемент из очереди. Очередь может быть
пустой; он ждет, пока элемент не станет доступным.
full() – возвращает True, если очередь заполнена. По умолчанию
очередь определяется как maxsize = 0. В этом случае он не вернет True.
put(item) – добавляет элемент в очередь; если очередь заполнена,
ожидает, пока освободится место.
put_nowait(item) – добавляет элемент в очередь без задержки.
qsize() – возвращает размер очереди.
10

11.

РЕАЛИЗАЦИЯ СТЕКА:
LIFOQUEUE
Пример:
Из библиотеки queue
импортируем класс LifoQueue
Объявляем переменную в качестве
класса LifoQueue с максимальным
размером 5 – это и будет стек
Добавляем в стек элементы
Выводим
статус стека
Последовательно очищаем стек
Выводим
статус стека
11

12.

РЕАЛИЗАЦИЯ СТЕКА:
LIFOQUEUE
Класс LifoQueue работает так же, как
стек, но этот модуль включает некоторые
дополнительные методы, упомянутые
выше. Мы определили стек с
максимальным размером, что означает,
что он может содержать максимум пять
значений в нем.
12

13.

ОЧЕРЕДИ В
PYTHON

14.

ПОНЯТИЕ ОЧЕРЕДИ
Очередь – это линейный тип структуры данных,
используемый для последовательного хранения данных. Ее
концепция основана на FiFO («First in First Out»), что
означает «первый пришел – первый вышел».
Очередь имеет два конца – спереди и сзади. Следующий
элемент вставляется с заднего конца и снимается с переднего
конца.
14

15.

ПОНЯТИЕ ОЧЕРЕДИ
Например, в классе
информатики несколько
компьютеров, подключенных
к одному принтеру.
Учащиеся хотят напечатать
свою работу; принтер
напечатает первое задание,
второе и так далее. Если мы
будем последними, нам
нужно дождаться
завершения всех других
задач, которые опережают
нашу.
15

16.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:
СПИСКИ
Список можно использовать как очередь, но он не
подходит с точки зрения производительности.
Python предоставляет встроенные методы insert()
и функцию pop() для добавления и удаления
элементов.
Списки довольно медленные, потому что, если мы
вставляем новый элемент в список, все элементы
требуют сдвига на один.
16

17.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:
СПИСОК
Пример:
Объявляем список, который будем
использовать в качестве очереди
Добавляем в очередь
элементы
Выводим очередь
Последовательно очищаем
очередь
Выводим
очередь
17

18.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:
DEQUE
Класс deque реализует двухконечную
очередь, которая поддерживает
добавление и удаление элементов с обоих
концов. Объекты deque представлены в
виде двусвязных списков (хранят ссылки
не только на следующий, но и на
предыдущий элемент)
18

19.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:
DEQUE
Двусвязность дает им превосходную
производительность для входящих и выходящих
элементов, но при этом у него плохая
производительность при работе со случайно
принимаемыми элементами в середине очереди.
В связи с тем, что deque поддерживает вставку и
удаление элементов одинаково хорошо, они могут
поддерживать и очереди, и стеки
19

20.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:
DEQUE
Пример:
Из библиотеки collections
импортируем класс deque
Объявляем переменную в качестве
класса deque – это и будет очередь
Добавляем в очередь
элементы
Выводим очередь
Последовательно очищаем очередь
Выводим очередь
20

21.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:
QUEUE.QUEUE
Python предоставляет модуль для
реализации очередей с помощью
класса Queue.
Применяется при параллельных
вычислениях и
мультипрограммировании.
21

22.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ:
QUEUE.QUEUE
Пример:
Из библиотеки queue
импортируем класс Queue
Объявляем переменную в качестве
класса Queue – это и будет очередь
Добавляем в очередь
элементы
Выводим очередь
Последовательно очищаем очередь
22
22

23.

ПРИОРИТЕТНАЯ ОЧЕРЕДЬ
Очередь с приоритетом – это особый тип
очереди в структуре данных. Она сортирует
элементы и удаляет их в соответствии с
приоритетами.
В отличие от обычной, она извлекает элемент с
наивысшим приоритетом вместо следующего
элемента. Приоритет отдельных элементов
определяется порядком их ключей.
23

24.

ПРИОРИТЕТНАЯ ОЧЕРЕДЬ
Очереди приоритетов наиболее полезны для
решения проблем планирования, когда
некоторые задачи будут выполняться на основе
приоритетов.
Например, задачи ОС – лучший пример очереди
с приоритетом. Она выполняет высокий приоритет
над задачами с более низким приоритетом (не
загружать обновления ОС, когда пользователь
выполняет рендер видео)
24

25.

ПРИОРИТЕТНАЯ ОЧЕРЕДЬ
В СПИСКЕ
Мы можем использовать
отсортированный список в
качестве очереди
приоритетов, чтобы быстро
идентифицировать и удалять
элементы. Но вставка нового
элемента происходит
медленно. Следовательно,
отсортированный список
может быть эффективным,
когда в приоритетную очередь
будет сделано мало вставок.
25

26.

ПРИОРИТЕТНАЯ ОЧЕРЕДЬ
В QUEUE.PRIORITYQUEUE
Существует класс
queue.PriorityQueue,
который лучше
оптимизирован под задачи
приоритетного списка.
Особенность в том, что
приоритетная очередь
скоординирована и
работает лучше для
нескольких одновременных
событий и потребителей,
по сравнению со списками
26