# ADT: Diccionario (interfaz)
# Operaciones: insert(), search(), delete()

# Implementación 1: Array ordenado

class DiccionarioArray:
def insert(self, key, value): pass
def search(self, key): pass
def delete(self, key): pass

# Implementación 2: Tabla Hash

class DiccionarioHash:
def insert(self, key, value): pass
def search(self, key): pass
def delete(self, key): pass

# Implementación 3: Árbol Binario de Búsqueda

class DiccionarioArbol:
def insert(self, key, value): pass
def search(self, key): pass
def delete(self, key): pass

# El programa usa la interfaz, no la implementación específica

diccionario = DiccionarioHash() # Podemos cambiar esto fácilmente
diccionario.insert("nombre", "Juan")
resultado = diccionario.search("nombre")

Array: [10, 20, 30, 40, 50]

Memoria:
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└────┴────┴────┴────┴────┘
↑
Dirección base: 1000

Acceso a arr[2]:
Dirección = 1000 + (2 × tamaño_elemento)
= 1000 + (2 × 4 bytes)
= 1008
Tiempo: O(1) - ¡Instantáneo!

class Nodo:
    def __init__(self, dato):
        self.dato = dato      # Campo de datos
        self.siguiente = None # Puntero al siguiente nodo

class ListaEnlazada:
def **init**(self):
self.cabeza = None

    def insertar_al_inicio(self, dato):
        nuevo_nodo = Nodo(dato)
        nuevo_nodo.siguiente = self.cabeza
        self.cabeza = nuevo_nodo

    def buscar(self, valor):
        actual = self.cabeza
        while actual is not None:
            if actual.dato == valor:
                return True
            actual = actual.siguiente
        return False

# Visualización:

# cabeza → [10|●] → [20|●] → [30|●] → [40|None]

# ↑ ↑ ↑ ↑

# dato=10 dato=20 dato=30 dato=40

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

# Uso:
stack = Stack()
stack.push(10)  # [10]
stack.push(20)  # [10, 20]
stack.push(30)  # [10, 20, 30]

print(stack.pop())   # 30 → [10, 20]
print(stack.peek())  # 20 (sin remover)
print(stack.pop())   # 20 → [10]

from collections import deque

class Queue:
def **init**(self):
self.items = deque()

    def enqueue(self, item):
        self.items.append(item)  # Agregar al final

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()  # Remover del frente
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        return None

    def is_empty(self):
        return len(self.items) == 0

# Uso:

queue = Queue()
queue.enqueue(10) # [10]
queue.enqueue(20) # [10, 20]
queue.enqueue(30) # [10, 20, 30]

print(queue.dequeue()) # 10 → [20, 30]
print(queue.peek()) # 20 (sin remover)
print(queue.dequeue()) # 20 → [30]

# Diccionario como ADT - puede tener múltiples implementaciones

# Implementación con tabla hash de Python

estudiantes = {}

# Insert

estudiantes["Juan"] = {"edad": 20, "carrera": "Ingeniería"}
estudiantes["María"] = {"edad": 22, "carrera": "Medicina"}
estudiantes["Pedro"] = {"edad": 21, "carrera": "Derecho"}

# Search

if "Juan" in estudiantes:
print(estudiantes["Juan"]) # {'edad': 20, 'carrera': 'Ingeniería'}

# Delete

del estudiantes["Pedro"]

# Iterar

for nombre, info in estudiantes.items():
print(f"{nombre}: {info['edad']} años")

def funcion_hash_simple(clave, tamano_tabla):
    """
    Convierte una clave (string, número, etc.) en un índice
    """
    # Para strings: suma de valores ASCII
    hash_value = sum(ord(c) for c in str(clave))
    # Módulo para mantenerlo dentro del rango
    return hash_value % tamano_tabla

# Ejemplo:
tabla_tamano = 10

hash("Juan") = (74+117+97+110) % 10 = 398 % 10 = 8
hash("María") = (77+97+114+105+97) % 10 = 490 % 10 = 0
hash("Pedro") = (80+101+100+114+111) % 10 = 506 % 10 = 6

# Tabla hash resultante:
# [0] → María
# [1] → (vacío)
# [2] → (vacío)
# ...
# [6] → Pedro
# [7] → (vacío)
# [8] → Juan
# [9] → (vacío)

class HashTableChaining:
    def __init__(self, tamano=10):
        # Tabla de listas enlazadas (cubetas)
        self.tamano = tamano
        self.tabla = [[] for _ in range(tamano)]
    
    def hash(self, clave):
        return hash(clave) % self.tamano
    
    def insert(self, clave, valor):
        indice = self.hash(clave)
        # Agregar a la lista en ese índice
        for i, (k, v) in enumerate(self.tabla[indice]):
            if k == clave:
                self.tabla[indice][i] = (clave, valor)
                return
        self.tabla[indice].append((clave, valor))
    
    def search(self, clave):
        indice = self.hash(clave)
        # Buscar en la lista
        for k, v in self.tabla[indice]:
            if k == clave:
                return v
        return None

# Visualización:

# [0] → []

# [1] → []

# [2] → [("Ana", 20), ("Luis", 22)] ← Colisión manejada

# [3] → []

# [4] → [("María", 25)]

# ...

class HashTableOpenAddressing:
    def __init__(self, tamano=10):
        self.tamano = tamano
        self.claves = [None] * tamano
        self.valores = [None] * tamano

    def hash(self, clave):
        return hash(clave) % self.tamano

    def insert(self, clave, valor):
        indice = self.hash(clave)

        # Sondeo lineal: buscar siguiente posición libre
        while self.claves[indice] is not None:
            if self.claves[indice] == clave:
                self.valores[indice] = valor
                return
            indice = (indice + 1) % self.tamano

        self.claves[indice] = clave
        self.valores[indice] = valor

    def search(self, clave):
        indice = self.hash(clave)

        while self.claves[indice] is not None:
            if self.claves[indice] == clave:
                return self.valores[indice]
            indice = (indice + 1) % self.tamano

        return None

# Si hash("Ana") = 2 y está ocupado:
# Intenta índice 3, 4, 5... hasta encontrar espacio libre