---

# ============================================================
# БИЛЕТ 7 — ГОТОВАЯ ПРОГРАММА
# Просто запусти. Она сама всё сделает и всё выведет.
# ============================================================


# ---------- 1. ХЭШИРОВАНИЕ ----------

def hash_function(s, size):
    """Превращает строку в число от 0 до size-1."""
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % size
    return h


class HashTable:
    """Хэш-таблица: хранит ключ -> значение."""
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]

    def put(self, key, value):
        index = hash_function(key, self.size)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])

    def get(self, key):
        index = hash_function(key, self.size)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        return None


# ---------- 2. ДВУСВЯЗНЫЙ СПИСОК С __getitem__ ----------

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None


class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node

    def __getitem__(self, index):
        if index < 0:
            return None
        current = self.head
        i = 0
        while current is not None:
            if i == index:
                return current.data
            current = current.next
            i += 1
        return None


# ---------- 3. ЗАДАЧА 232: ОЧЕРЕДЬ НА СТЕКАХ ----------

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x):
        self.stack_in.append(x)

    def pop(self):
        self.peek()
        return self.stack_out.pop()

    def peek(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out[-1]

    def empty(self):
        return len(self.stack_in) == 0 and len(self.stack_out) == 0


# ============================================================
# ЗАПУСК И ВЫВОД
# ============================================================

print("=" * 55)
print("ПУНКТ 1: ХЭШИРОВАНИЕ")
print("=" * 55)

print("Хэш-функция превращает строку в число:")
print("  hash('hello')  =", hash_function("hello", 10))
print("  hash('world')  =", hash_function("world", 10))
print("  hash('hello')  =", hash_function("hello", 10), "(то же самое — это правильно)")

print("\nХэш-таблица (ключ -> значение):")
ht = HashTable()
ht.put("apple", 100)
ht.put("banana", 200)
ht.put("apple", 999)
print("  apple  =", ht.get("apple"), "(было 100, стало 999 — перезапись работает)")
print("  banana =", ht.get("banana"))
print("  cherry =", ht.get("cherry"), "(нет такого ключа)")

print()
print("=" * 55)
print("ПУНКТ 2: __getitem__ ДВУСВЯЗНОГО СПИСКА")
print("=" * 55)

lst = DoublyLinkedList()
for x in [10, 20, 30, 40, 50]:
    lst.add(x)

print("Список: 10 <-> 20 <-> 30 <-> 40 <-> 50")
print("  lst[0] =", lst[0])
print("  lst[2] =", lst[2])
print("  lst[4] =", lst[4])
print("  lst[99] =", lst[99], "(за границей — None)")

print()
print("=" * 55)
print("ПУНКТ 3: ЗАДАЧА 232 — ОЧЕРЕДЬ НА СТЕКАХ")
print("=" * 55)

q = MyQueue()
q.push(1)
print("  push(1)")
q.push(2)
print("  push(2)")
print("  peek()  =", q.peek())
print("  pop()   =", q.pop())
print("  empty() =", q.empty())
print("  pop()   =", q.pop())
print("  empty() =", q.empty())

print()
print("=" * 55)
print("ВСЁ РАБОТАЕТ. ПРОГРАММА ЗАВЕРШЕНА.")
print("=" * 55)