Lists.md

Домашнее задание к занятию 4. Списки

Инструкция по выполнению домашнего задания:

1. Зарегистрируйтесь на сайте repl.it;
2. Перейдите в раздел my repls;
3. Нажмите кнопку Start coding now! - если вы приступаете впервые, или New Repl - если у вас уже есть работы;
4. В списке языков выберите тот язык, который изучаете;
5. Код пишите в левой части окна - в редакторе кода;
6. Чтобы посмотреть результат выполнения файла, нажмите на кнопку Run. Результат появится в правой части окна;
7. После окончания работы скопируйте ссылку на ваш repl в адресной строке браузера;
8. Скопированную ссылку (ваше решение ДЗ) нужно отправить на проверку. Для этого перейдите в личный кабинет на сайте netology.ru, в поле комментария к домашней работе вставьте скопированную ссылку и отправьте работу на проверку;

---

Односвязный стек

Давайте реализуем стек на основе односвязного стека. Значения стека будем хранить в обёртке, где помимо значения будет указатель на ниже в стеке элемент, в самом же стеке будем хранить указатель на самый верхний элемент:

Node:
  value - значение в обёртке
  prev - элемент, ниже в стеке

Stack:
  head - указатель на обёртку с элементом, который надо вынуть следующим

Давайте реализуем две основные для стека операции. Для push создадим обёртку для нового значения, на который теперь будет указывать голова стека, а на старую голову будет указывать указатель на предыдущий элемент в обёртке. Для pop вынем значение из обёртки, на которую указывает голова стека, после чего передвиним голову стека на ту обёртку, на которую указывал указатель на предыдущий элемент в голове стека.

Stack:
  ...

  push(value):
    if head пустая
      head = Node(value=value, prev=пусто)
    else
      node = Node(value=value, prev=head)
      head = node
  
  def pop(self):
    if head пустая
      return нет элементов!
    else
      value = head.value
      head = head.prev
      return value

Теперь давайте добавим метод вывода стека на экран:

Stack:
  ...

  printme():
    if head пустая
      напечатаем "EMPTY"
    else
      node = head
      while node не пустой
        напечатаем node.value
        if у node есть предыдущий
          напечатаем " -> "
        node = node.prev

Дополнительно: reverse

Это необязательная часть. Можно сделать ещё один метод: reverse(), который бы возвращал новый стек, в котором те же элементы, но в другом порядке. Это сделаем рекурсивно, напишем вспомогательную функцию, которая будет принимать односвязный список и будет возвращать два значения: голову и хвост нового списка, который является ревёрсом (т.е. в обратном порядке) исходного списка. Для языков, где нельзя вернуть несколько значений, заведите, например, вспомогательный класс, объект которого вы заполните возвращаемыми значениями и вернёте как результат функции.

Stack:
  ...

  reverse():
    if head пустая: return Stack()

    reversed_head(node):
      new_node = Node(value=node.value)
      if node.prev пустая:
        return (new_node, new_node)
      else:
        head, tail = reversed_head(node.prev)
        tail.prev = new_node
        return (head, new_node)
    reversed_stack = Stack()
    new_head, new_tail = reversed_head(self.head)
    reversed_stack.head = new_head
    return reversed_stack

Демонстрация

Теперь протестируем наш стек:

stack = Stack()
stack.printme()
напечатаем 'Добавим 0'
stack.push(0)
stack.printme()
напечатаем 'Добавим 1'
stack.push(1)
stack.printme()
напечатаем 'Добавим 2'
stack.push(2)
stack.printme()
напечатаем 'Добавим 3'
stack.push(3)
stack.printme()
напечатаем 'Добавим 4'
stack.push(4)
stack.printme()
напечатаем 'Добавим 5'
stack.push(5)
stack.printme()
напечатаем 'Снимем со стека'
напечатаем stack.pop()
stack.printme()
напечатаем 'Снимем со стека'
напечатаем stack.pop()
stack.printme()
напечатаем 'Ревёрс!'
stack = stack.reverse()
stack.printme()
напечатаем 'Снимем со стека'
напечатаем stack.pop()
stack.printme()
напечатаем 'Снимем со стека'
напечатаем stack.pop()
stack.printme()
напечатаем 'Ревёрс!'
stack = stack.reverse()
stack.printme()
напечатаем 'Снимем со стека'
напечатаем stack.pop()
stack.printme()
напечатаем 'Снимем со стека'
напечатаем stack.pop()
stack.printme()

Должен получиться такой вывод:

EMPTY
Добавим 0
0
Добавим 1
1 -> 0
Добавим 2
2 -> 1 -> 0
Добавим 3
3 -> 2 -> 1 -> 0
Добавим 4
4 -> 3 -> 2 -> 1 -> 0
Добавим 5
5 -> 4 -> 3 -> 2 -> 1 -> 0
Снимем со стека
5
4 -> 3 -> 2 -> 1 -> 0
Снимем со стека
4
3 -> 2 -> 1 -> 0
Ревёрс!
0 -> 1 -> 2 -> 3
Снимем со стека
0
1 -> 2 -> 3
Снимем со стека
1
2 -> 3
Ревёрс!
3 -> 2
Снимем со стека
3
2
Снимем со стека
2
EMPTY

Реализация

1. Реализовать структуру данных на односвязном списке. Использовать встроенные структуры данных для хранения элементов (массивы, списки, коллекции и так далее) запрещено, список надо писать самому.
2. Протестировать работу со стеком командами из примера выше. Убедиться, что вывод совпадает с ответом.
3. Загрузите ваше решение на сайт repl.it, отправьте ссылку на него на проверку.