Лабораторная работа № 2. Стек и очередь

ПредупреждениеНеобходимые файлы

Перед началом работы, скачайте по ссылке файл ds.py с реализацией необходимых структур данных. Скачайте файл с заданиями, выполняемыми без компьютера.

Теоретические сведения

Тип данных Стек

Стек - это абстрактная структура данных, хранящая элементы, которые можно добавлять или извлекать из одного конца стека. Часть стека в которую помещаются или извлекаются элементы принято называть вершиной стека. Стек работает по принципу “Первым пришёл - последним ушёл”.

Кликните по изображению, чтобы перейти к интерактивной визуализации работы стека.

В лабораторной работе используем собственную реализацию стека на списках. Класс Stack будет храниться в файле ds.py. Чтобы создать новый объект класса Stack необходимо импортировать класс из файла ds.py:

# импорт класса Stack из файла ds.py
from ds import Stack

# создание нового объекта класса Stack
s = Stack()

В Таблице 1 перечислены методы класса Stack.

Таблица 1: Методы и свойства класса Stack

Метод/Свойство	Назначение	Пример
push(el)	Метод добавляет el на вершину стека.	s.push(4)
pop()	Метод удаляет элемент с вершины стека и возвращает его.	t = s.pop();
peek()	Метод возвращает элемент с вершины стека не удаляя его.	t = s.peek();
size()	Метод возвращает количество элементов в стеке.	c = s.size();

Рассмотрим пример использования методов:

from ds import Stack
s = Stack()

s.push(5)
s.push(7)
s.push(9)
s.peek()
s.pop()
s.size()

Выполнение кода проиллюстрировано на следующем изображении:

Иллюстрация работы кода

Тип данных Очередь

Очередь - абстрактная структура данных, элементы в которую добавляются с одного конца а извлекаются из другого. Очередь работает по принципу “Первым пришёл - первым вышел”. У очереди есть начало и конец. Новые элементы добавляются в конец очереди а извлекаются из начала очереди.

Кликните по изображению, чтобы перейти к интерактивной визуализации работы стека.

В лабораторной работе используем собственную реализацию очереди на списках. Класс Queue будет храниться в файле ds.py. Чтобы создать новый объект класса Queue необходимо импортировать класс из файла ds.py:

from ds import Queue

q = Queue()

В Таблице 2 перечислены методы класса Queue.

Таблица 2: Методы и свойства класса Queue

Метод/Свойство	Назначение	Пример
enqueue(el)	Метод добавляющий el в конец очереди.	q.enqueue("doc")
dequeue()	Метод удаляет элемент из начала очереди и возвращает его.	t = q.dequeue();
peek()	Метод возвращает элемент из начала очереди но не удаляет его.	t = q.peek();
size()	Метод возвращает количество элементов в очереди.	c = q.size();

Рассмотрим пример использования методов:

from ds import Queue
q = Queue()

q.enqueue(5)
q.enqueue(8)
q.enqueue(3)
q.dequeue()
q.peek()
q.size()

Выполнение кода проиллюстрировано на следующем изображении:

Иллюстрация работы кода

Задания для практической работы

УведомлениеВнимание

Задания обозначенные значком выполняются на распечатках или в тетради, обозначенные - на компьютере в среде программирования.

Задание 1. Интерфейс абстрактного типа данных «Стек»

Объявлена переменная s встроенного типа Stack. В стеке могут храниться только целые числа. Занесите в таблицу выполняемые инструкции, содержимое стека после выполнения инструкции и значение, которое возвращает инструкция (если таковое есть).

s = Stack()

Вариант 1

s.push(11)
s.push(8)
s.pop()
s.peek()
s.size()
s.pop()

2

s.push(5)
s.push(3)
s.pop()
s.push(7)
s.peek()
s.pop()

3

s.push(10)
s.push(20)
s.push(30)
s.pop()
s.pop()
s.peek()

4

s.push(-1)
s.push(0)
s.peek()
s.pop()
s.push(15)
s.size()

5

s.push(100)
s.pop()
s.push(200)
s.push(300)
s.pop()
s.size()

6

s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.pop()
s.pop()

7

s.push(9)
s.size()
s.push(7)
s.pop()
s.push(5)
s.peek()

8

s.push(12)
s.push(15)
s.pop()
s.push(18)
s.peek()
s.size()

9

s.push(6)
s.push(1)
s.pop()
s.pop()
s.push(8)
s.push(9)

10

s.push(0)
s.push(-5)
s.peek()
s.pop()
s.pop()
s.push(10)

11

s.push(25)
s.size()
s.pop()
s.push(35)
s.peek()
s.push(45)

12

s.push(3)
s.push(6)
s.pop()
s.push(9)
s.pop()
s.peek()

13

s.push(50)
s.push(60)
s.peek()
s.push(70)
s.pop()
s.pop()

14

s.push(2)
s.push(4)
s.push(6)
s.pop()
s.peek()
s.size()

Используйте Таблицу 1, если вам нужна подсказка.

Задание 2. Интерфейс абстрактного типа данных «Очередь»

Объявлена переменная q встроенного типа Queue. Занесите в таблицу выполняемые инструкции, содержимое очереди после выполнения инструкции и значение, которое возвращает инструкция (если таковое есть).

q = Queue();

Вариант 1

q.enqueue("book")
q.enqueue("pen")
q.dequeue()
q.enqueue("note")
q.peek()
q.dequeue()

2

q.enqueue("doc")
q.peek()
q.enqueue("mp3")
q.size()
q.dequeue()
q.enqueue("avi")

3

q.enqueue("Pb")
q.enqueue("Ag")
q.dequeue()
q.peek()
q.enqueue("U")
q.size()

4

q.enqueue("R")
q.enqueue("B")
q.enqueue("G")
q.dequeue()
q.dequeue()
q.peek()

5

q.enqueue("cat")
q.peek()
q.enqueue("dog")
q.dequeue()
q.enqueue("fish")
q.size()

6

q.enqueue("RAM")
q.dequeue()
q.enqueue("CPU")
q.peek()
q.enqueue("PCI")
q.size()

7

q.enqueue("Пн")
q.enqueue("Вт")
q.size()
q.dequeue()
q.peek()
q.enqueue("Ср")

8

q.enqueue("Минск")
q.peek()
q.dequeue()
q.enqueue("Брест")
q.enqueue("Гомель")
q.size();

9

q.enqueue("com")
q.enqueue("org")
q.dequeue()
q.enqueue("by")
q.peek()
q.enqueue("ru")

10

q.enqueue("кофе")
q.enqueue("сок")
q.size()
q.dequeue()
q.peek()
q.enqueue("вода")

11

q.enqueue("if")
q.enqueue("for")
q.dequeue()
q.enqueue("else")
q.dequeue()
q.size()

12

q.enqueue("Альфа")
q.peek()
q.enqueue("Бета")
q.enqueue("Гамма")
q.dequeue() 
q.peek()

13

q.enqueue("X") 
q.dequeue() 
q.enqueue("Y") 
q.size() 
q.enqueue("Z") 
q.peek()

14

q.enqueue("alt") 
q.enqueue("ctrl") 
q.dequeue() 
q.peek() 
q.size() 
q.enqueue("del")

Используйте Таблицу 2, если вам нужна подсказка.

Задание 3. Использование типа данных Stack

Составьте программу, которая позволяет вводить строки, добавляет их в стек и затем выводит строки в обратном порядке. Ввод прекращается после слова “стоп”.

Пример работы программы:

Введите строку: <{один}> ++enter++
Введите строку: <{два}> ++enter++
Введите строку: <{три}> ++enter++
Введите строку: <{четыре}> ++enter++
Введите строку: <{стоп}> ++enter++
Строки в обратном порядке
четыре
три
два
один

✔

Использовано попыток: 0

В коде есть ошибка.

---

Блок-схема решения

Задание 4. Использование типа данных Queue

Пользователь вводит три команды для робота. Команды добавляются в очередь и затем выводятся на экран в порядке ввода с клавиатуры. Вывод продолжается, пока очередь не станет пустой.

Пример работы программы:

Введите команду: <{вверх}> ++enter++
Введите команду: <{вправо}> ++enter++
Введите команду: <{вправо}> ++enter++
Выполнение команд
вверх
вправо
вправо

✔

Использовано попыток: 0

В коде есть ошибка.

---

Блок-схема решения

Задание 5. Из десятичной в двоичную (sam05.py)

Используйте стек для реализации перевода числа X из десятичной системы счисления в двоичную.

Рисунок 1

1

2

3

ПредупреждениеПуть сохранения программы

Сохраняйте решение этой и последующих программ в одной папке с файлом ds.py. Иначе инструкция импорта не будет работать.

Тестовые данные:

Ввод	Вывод
42	101010
73	1001001
255	11111111
0	"" (пустая строка)

Задание 6. Баланс скобок (sam06.py)

Опишите функцию balance(S), которая определяет сбалансированно ли расставлены круглые скобки в строке S.

Рисунок 2

1

2

Используйте следующий шаблон:

from ds import Stack

def balance(s):
    ... # тут запишите алгоритм из блок-схемы

# код для проверки функции (не редактируйте)
print(balance('((()))'))        # True
print(balance('((()()))'))      # True
print(balance('(()'))           # False
print(balance(')('))            # False

Задание 7* (sam07.py)

Решите задачу вашего варианта.

Вариант 1

С помощью стека реализуйте историю посещения сайтов в браузере. Пользователь вводит адреса сайтов до ввода слова "выход". Если было введено слово "назад" из стека извлекается адрес ранее посещённого сайта и выводится на экран.

Пример работы программы:

Адрес: <{adu.by}> ++enter++
Адрес: <{bspu.by}> ++enter++
Адрес: <{google.com}> ++enter++
Адрес: <{назад}> ++enter++
google.com
Адрес: <{назад}> ++enter++
bspu.by
Адрес: <{выход}> ++enter++

2

Робот получает последовательность из двух команд - "влево или "вправо". Команды вводятся с клавиатуры до слова "старт". После этого робот начинает выводить команды на экран в обратном порядке, при этом направление поворотов меняется на противоположное: "влево меняется на "вправо" и наоборот. Используйте стек для решения задачи.

Пример работы программы:

Команда: <{влево}> ++enter++
Команда: <{влево}> ++enter++
Команда: <{вправо}> ++enter++
Команда: <{старт}> ++enter++
Команды в обратном порядке:
влево
вправо
вправо

3

С помощью структуры данных Очередь изобразите работу очереди печати. Пользователь вводит с клавиатуры названия файлов, предназначенных для печати до ввода слова "печать". По чистому совпадению, количество страниц в документах равно длине их имён. Выведите документы в порядке их печати и посчитайте общее количество напечатанных страниц. Вывод имён документов начинайте после сообщения "Начало печати".

Пример работы программы:

Документ: <{реферат}> ++enter++
Документ: <{бланк}> ++enter++
Документ: <{акт}> ++enter++
Документ: <{печать}> ++enter++
Начало печати
реферат
бланк
акт
Всего страниц: 15

4

Робот может двигаться вверх и вниз на заданное количество сантиметров. Положительное значение - движение вверх, отрицательное - вниз. Сохраняйте в очереди числа - значения высот. После числа 0 ввод высот останавливается. После сообщения "Начало работы" выведите команды в формате, который показан в примере:

Высота: <{20}> ++enter++
Высота <{-5}> ++enter++
Высота <{-10}> ++enter++
Высота <{0}> ++enter++
Начало работы
вверх на 20 см
вниз на 5 см
вниз на 10 см

5

С помощью стека реализуйте перемещение по каталогам на компьютере. Пользователь вводит названия папок до ввода слова "exit". Если была введена комбинация символов "cd .." из стека извлекается название предыдущего каталога и выводится на экран.

Пример работы программы:

> <{документы}> ++enter++
> <{курсовые}> ++enter++
> <{2026}> ++enter++
> <{cd}> .. ++enter++
2026
> <{cd}> .. ++enter++
курсовые
> <{quit}> ++enter++

6

В очереди сохраняются названия запланированных на день задач. Ввод названий прекращается после слова "начать". Выведите последовательность задач из очереди, длина названия которых превышает 10 символов.

Пример работы программы:

Задача: <{конспект урока}> ++enter++
Задача: <{реферат}> ++enter++
Задача: <{контрольная работа}> ++enter++
Задача: <{начать}> ++enter++
Список дел:
конспект урока
контрольная работа

7

Товары складываются в грузовик и могут быть выгружены из него только в обратном порядке. Используйте стек для хранения порядка погрузки товаров. С клавиатуры вводятся названия товаров. Ввод останавливается после ввода слова "пуск". По чистой случайности, вес товара (в килограммах) совпадает с количеством букв в его названии. Выведите на экран порядок разгрузки товаров и общий вес перевозимых товаров.

Пример работы программы:

Товар: <{яблоки}> ++enter++
Товар: <{картошка}> ++enter++
Товар: <{сок}> ++enter++
Товар: <{пуск}> ++enter++
Товары:
сок
картошка
яблоки
Общий вес: 17 кг

8

С помощью стека реализуйте историю посещения сайтов в браузере. Пользователь вводит адреса сайтов до ввода слова "выход". Если было введено слово "назад" из стека извлекается адрес ранее посещённого сайта и выводится на экран.

Пример работы программы:

Адрес: <{adu.by}> ++enter++
Адрес: <{bspu.by}> ++enter++
Адрес: <{google.com}> ++enter++
Адрес: <{назад}> ++enter++
google.com
Адрес: <{назад}> ++enter++
bspu.by
Адрес: <{выход}> ++enter++

9

Робот получает последовательность из двух команд - "влево или "вправо". Команды вводятся с клавиатуры до слова "старт". После этого робот начинает выводить команды на экран в обратном порядке, при этом направление поворотов меняется на противоположное: "влево меняется на "вправо" и наоборот. Используйте стек для решения задачи.

Пример работы программы:

Команда: <{влево}> ++enter++
Команда: <{влево}> ++enter++
Команда: <{вправо}> ++enter++
Команда: <{старт}> ++enter++
Команды в обратном порядке:
влево
вправо
вправо

10

С помощью структуры данных Очередь изобразите работу очереди печати. Пользователь вводит с клавиатуры названия файлов, предназначенных для печати до ввода слова "печать". По чистому совпадению, количество страниц в документах равно длине их имён. Выведите документы в порядке их печати и посчитайте общее количество напечатанных страниц. Вывод имён документов начинайте после сообщения "Начало печати".

Пример работы программы:

Документ: <{реферат}> ++enter++
Документ: <{бланк}> ++enter++
Документ: <{акт}> ++enter++
Документ: <{печать}> ++enter++
Начало печати
реферат
бланк
акт
Всего страниц: 15

11

Робот может двигаться вверх и вниз на заданное количество сантиметров. Положительное значение - движение вверх, отрицательное - вниз. Сохраняйте в очереди числа - значения высот. После числа 0 ввод высот останавливается. После сообщения "Начало работы" выведите команды в формате, который показан в примере:

Высота: <{20}> ++enter++
Высота <{-5}> ++enter++
Высота <{-10}> ++enter++
Высота <{0}> ++enter++
Начало работы
вверх на 20 см
вниз на 5 см
вниз на 10 см

12

С помощью стека реализуйте перемещение по каталогам на компьютере. Пользователь вводит названия папок до ввода слова "exit". Если была введена комбинация символов "cd .." из стека извлекается название предыдущего каталога и выводится на экран.

Пример работы программы:

> <{документы}> ++enter++
> <{курсовые}> ++enter++
> <{2026}> ++enter++
> <{cd}> .. ++enter++
2026
> <{cd}> .. ++enter++
курсовые
> <{quit}> ++enter++

13

В очереди сохраняются названия запланированных на день задач. Ввод названий прекращается после слова "начать". Выведите последовательность задач из очереди, длина названия которых превышает 10 символов.

Пример работы программы:

Задача: <{конспект урока}> ++enter++
Задача: <{реферат}> ++enter++
Задача: <{контрольная работа}> ++enter++
Задача: <{начать}> ++enter++
Список дел:
конспект урока
контрольная работа

14

Товары складываются в грузовик и могут быть выгружены из него только в обратном порядке. Используйте стек для хранения порядка погрузки товаров. С клавиатуры вводятся названия товаров. Ввод останавливается после ввода слова "пуск". По чистой случайности, вес товара (в килограммах) совпадает с количеством букв в его названии. Выведите на экран порядок разгрузки товаров и общий вес перевозимых товаров.

Пример работы программы:

Товар: <{яблоки}> ++enter++
Товар: <{картошка}> ++enter++
Товар: <{сок}> ++enter++
Товар: <{пуск}> ++enter++
Товары:
сок
картошка
яблоки
Общий вес: 17 кг