Алгоритмы и структуры данных в Python, стек. Лабораторная работа 4 Стек, очередь, связанный список Факультет фикт группа К3143 Студент Чаптыков Н. В
 Скачать 208.44 Kb.
|
|
Министерство образования и науки РФ Университет ИТМО Дисциплина – Алгоритмы и структуры данных Лабораторная работа №4 Стек, очередь, связанный список Факультет: ФИКТ Группа: К3143 Студент: Чаптыков Н.В. Преподаватель: Харьковская Т.А. Дата выполнения: 25.11.21 Санкт-Петербург 2021
Стек — это массив элементов, организованный таким образом, что при удалении элемента удаляется последний, а при добавлении элемент попадает в конец массива. Python позволяет реализовать стек используя лишь методы списков append() и pop(). В задании требуется вывести удаленные элементы. Для этого создадим результативный список b. Программа:  С  корость выполнения кода, 106 операций:
Задание аналогично предыдущему, только в отличие от стека, в очереди удаляется первый вошедший элемент. Для решения задачи я использую deque и метод popleft() для удаления элементов.  Программа:Скорость выполнения кода, 106 операций. 
В задании необходимо определить строки с закрытыми и не пересекающимися скобками. Чтобы выполнить данную задачу можно применить стек, состоящий из открывающихся скобок. Если в строке встречается закрывающая скобка, то элемент из стека удаляется. В последней итерации необходимо проверить размер стека. Если все скобки закрыты, т. е. длина стека равна нулю, то скобочная последовательность правильная, в ином случае в выводе будет “No”.  Программа:Скорость выполнения программы, 5*106 операций: 
Необходимо реализовать очередь с опцией вывода минимального значения. Операции “+” и “-” выполняются так же, как и в задании 2. Для решения задачи создадим две функции queue() и deque(). Первая функция формирует очередь из элементов в стеке с помощью методов pop() и append(). Данная функция необходима для удаления элементов в очереди. Работа функции deque() аналогична queue(), только она преоразует очередь в стек. Deque() необходима для добавления элементов в очередь. В данные функции встроен поиск минимального элемента – это обеспечивает линейное время выполнения алгоритма. При удалении элементов необходимо реализовать сброс минимума. Для этого вводится проверка на заполненность очереди и равенство последнего удаленного элемента и минимума.  Программа: Скорость выполнения программы, 106 операций: 
В задании необходимо вычислить значение выражения, представленного в постфиксной записи. Пусть полученные числовые данные формируют стек. Если в строке попадаются знаки умножения, деления и сложения, то алгоритм соответственно выполняет эти действия с двумя последними элементами стека, а результат записывается также в этот стек.  Код:11 задание, бюрократия В задании необходимо вывести состояние очереди и количество требуемых для каждого посетителя справок, при известном количестве выдаваемых справок и при условии, что, получая документ, посетитель встает в конец очереди и уходит только если получил все бумаги. Мой алгоритм решения последовательно декрементирует элементы, отправляя каждое полученное значение в конец очереди. Если элемент равен нулю, то  он удаляется из списка. Очередь реализована с помощью библиотеки deque. |