Слайд 2: Основные структуры данных

Стек (Stack)

Принцип: LIFO (Last In, First Out) - последним пришёл, первым вышел

Сложность операций: O(1) для push/pop

# Реализация стека для отмены действий
class ActionStack:
    def __init__(self):
        self.actions = []
    
    def push(self, action):
        """Добавить действие"""
        self.actions.append(action)
    
    def pop(self):
        """Отменить последнее действие"""
        if not self.is_empty():
            return self.actions.pop()
    
    def is_empty(self):
        return len(self.actions) == 0

# Пример использования
undo_stack = ActionStack()
undo_stack.push({"type": "upgrade_artifact", "level": 4})
undo_stack.push({"type": "add_character", "name": "Венти"})
last_action = undo_stack.pop()  # Получаем последнее действие

Очередь (Queue)

Принцип: FIFO (First In, First Out) - первым пришёл, первым вышел

Сложность операций: O(1) для enqueue/dequeue

from collections import deque

# Реализация очереди для обработки боевых эффектов
class EffectQueue:
    def __init__(self):
        self.effects = deque()
    
    def enqueue(self, effect):
        """Добавить эффект в очередь"""
        self.effects.append(effect)
    
    def dequeue(self):
        """Применить следующий эффект"""
        if not self.is_empty():
            return self.effects.popleft()
    
    def is_empty(self):
        return len(self.effects) == 0

# Пример использования
battle_queue = EffectQueue()
battle_queue.enqueue({"type": "burning", "duration": 3})
battle_queue.enqueue({"type": "healing", "amount": 1000})
next_effect = battle_queue.dequeue()  # Получаем первый эффект

Связный список (Linked List)

Сложность операций:

  • Доступ к элементу: O(n)
  • Вставка/удаление в начало: O(1)
  • Вставка/удаление в произвольное место: O(n)
# Реализация связного списка для цепочки квестов
class QuestNode:
    def __init__(self, quest_data):
        self.quest = quest_data
        self.next = None
        self.prev = None

class QuestChain:
    def __init__(self):
        self.head = None
        self.tail = None
    
    def add_quest(self, quest_data):
        """Добавить квест в цепочку"""
        new_node = QuestNode(quest_data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
    
    def get_next_quest(self, current_quest):
        """Получить следующий квест в цепочке"""
        node = self.head
        while node:
            if node.quest["id"] == current_quest["id"]:
                return node.next.quest if node.next else None
            node = node.next

# Пример использования
quest_line = QuestChain()
quest_line.add_quest({
    "id": 1,
    "name": "Встреча с Эмбер",
    "location": "Мондштадт"
})
quest_line.add_quest({
    "id": 2,
    "name": "Полёт с Эмбер",
    "location": "Мондштадт"
})

Важно помнить:

  • Стек удобен для отмены действий и рекурсивных алгоритмов
  • Очередь хороша для обработки событий в порядке их появления
  • Связный список эффективен при частых вставках/удалениях
  • В Python list часто эффективнее самописного связного списка

Задача: Система боевых эффектов

Создайте систему для управления боевыми эффектами в игре:

Подсказка: Пример структуры эффекта:

class Effect:
    def __init__(self, type_name, duration, value):
        self.type = type_name
        self.duration = duration
        self.value = value
        
class EffectSystem:
    def __init__(self):
        self.active_effects = deque()  # Текущие эффекты
        self.history = []  # История эффектов
        
    def apply_effect(self, effect):
        self.active_effects.append(effect)
        self.history.append(effect)
        
    def update(self):
        # Обновление эффектов каждый тик