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

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

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

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

В лабораторной работе используем собственную реализацию стека на списках. Класс 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();`

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

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

В лабораторной работе используем собственную реализацию очереди на списках. Класс 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();`

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

Внимание

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

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

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

s = Stack()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

q = Queue();

q.enqueue("книга")
q.enqueue("тетрадь")
q.dequeue()
q.enqueue("ручка")
q.peek()
q.dequeue()

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

q.enqueue("документ")
q.enqueue("текст")
q.dequeue()
q.peek()
q.enqueue("изображение")
q.size()

q.enqueue("красный")
q.enqueue("синий")
q.enqueue("зелёный")
q.dequeue()
q.dequeue()
q.peek()

q.enqueue("кошка")
q.peek()
q.enqueue("собака")
q.dequeue()
q.enqueue("рыба")
q.size()

q.enqueue("яблоко")
q.dequeue()
q.enqueue("банан")
q.peek()
q.enqueue("вишня")
q.size()

q.enqueue("понедельник")
q.enqueue("вторник")
q.size()
q.dequeue()
q.peek()
q.enqueue("среда")

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

q.enqueue("хлеб")
q.enqueue("молоко")
q.dequeue()
q.enqueue("сыр")
q.peek()
q.enqueue("чай")

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

q.enqueue("золото")
q.enqueue("серебро")
q.dequeue()
q.enqueue("бронза")
q.dequeue()
q.size()

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

q.enqueue("дождь") 
q.dequeue() 
q.enqueue("солнце") 
q.size() 
q.enqueue("ветер") 
q.peek()

q.enqueue("футбол") 
q.enqueue("хоккей") 
q.dequeue() 
q.peek() 
q.size() 
q.enqueue("теннис")

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

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

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

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

Введите строку: один
Введите строку: два
Введите строку: три
Строки в обратном порядке
три
два
один

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

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

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

Введите команду: вверх
Введите команду: вправо
Введите команду: вправо
Выполнение команд
вверх
вправо
вправо

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

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

Рисунок 1

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

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

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

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

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

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

Рисунок 2

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

from ds import Stack

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

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

💻 Задание 7*. Универсальный баланс скобок (sam07.py)

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