Python3 Estructuras de datos

En este capítulo presentamos las estructuras de datos de Python combinando los puntos de conocimiento aprendidos anteriormente.

Listas

En Python, las listas son mutables, que es la característica más importante que las distingue de las cadenas y las tuplas. En una frase: las listas se pueden modificar, mientras que las cadenas y las tuplas no.

A continuación se muestran los métodos de las listas en Python:

Método Descripción
list.append(x) Añade un elemento al final de la lista, equivalente a a[len(a):] = [x].
list.extend(L) Extiende la lista añadiendo todos los elementos de la lista especificada, equivalente a a[len(a):] = L.
list.insert(i, x) Inserta un elemento en una posición especificada. El primer parámetro es el índice del elemento delante del cual se va a insertar; por ejemplo, a.insert(0, x) inserta al principio de la lista, mientras que a.insert(len(a), x) equivale a a.append(x).
list.remove(x) Elimina el primer elemento de la lista cuyo valor sea x. Si no existe tal elemento, se produce un error.
list.pop([i]) Elimina el elemento de la lista en la posición especificada y lo devuelve. Si no se especifica un índice, a.pop() devuelve el último elemento. El elemento se elimina inmediatamente de la lista. (Los corchetes alrededor de i en el método indican que este parámetro es opcional, no que debas escribir un par de corchetes; verás esta notación a menudo en el manual de referencia de la biblioteca de Python).
list.clear() Elimina todos los elementos de la lista, equivalente a del a[:].
list.index(x) Devuelve el índice del primer elemento de la lista cuyo valor sea x. Si no hay ningún elemento coincidente, se produce un error.
list.count(x) Devuelve el número de veces que aparece x en la lista.
list.sort() Ordena los elementos de la lista.
list.reverse() Invierte los elementos de la lista.
list.copy() Devuelve una copia superficial de la lista, equivalente a a[:].

El siguiente ejemplo demuestra la mayoría de los métodos de las listas:

Ejemplo

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print(a.count(333), a.count(66.25), a.count('x'))
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.sort()
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]

Nota: los métodos que modifican la lista, como insert, remove o sort, no devuelven un valor.

Usar la lista como una pila

En Python, puede usar una lista para implementar la funcionalidad de una pila. Una pila es una estructura de datos de último en entrar, primero en salir (LIFO, Last-In-First-Out), lo que significa que el último elemento añadido es el primero en ser eliminado. La lista proporciona algunos métodos que la hacen muy adecuada para operaciones de pila, especialmenteappend()ypop()Método.

Con el método append() puede añadir un elemento a la cima de la pila, y con el método pop() sin índice puede extraer un elemento de la cima.

Operaciones de pila

  • Apilar (Push): Añade un elemento a la cima de la pila.
  • Desapilar (Pop): Elimina y devuelve el elemento superior de la pila.
  • Ver el elemento superior de la pila (Peek/Top): Devuelve el elemento superior de la pila sin eliminarlo.
  • Comprobar si está vacía (IsEmpty): Comprueba si la pila está vacía.
  • Obtener el tamaño de la pila (Size): Obtiene el número de elementos en la pila.

A continuación se explica en detalle cómo usar listas en Python para implementar estas operaciones:

1. Crear una pila vacía

Ejemplo

stack = []

2. Operación de apilar (Push)

Use el método append() para añadir un elemento a la cima de la pila:

Ejemplo

stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # Salida: [1, 2, 3]

3. Operación de desapilar (Pop)

Use el método pop() para eliminar y devolver el elemento superior de la pila:

Ejemplo

top_element = stack.pop()
print(top_element)  # Salida: 3
print(stack)        # Salida: [1, 2]

4. Ver el elemento superior de la pila (Peek/Top)

Acceda directamente al último elemento de la lista (sin eliminarlo):

Ejemplo

top_element = stack[-1]
print(top_element)  # Salida: 2

5. Comprobar si está vacía (IsEmpty)

Compruebe si la lista está vacía:

Ejemplo

is_empty = len(stack) == 0
print(is_empty)  # Salida: False

6. Obtener el tamaño de la pila (Size)

Use la función len() para obtener el número de elementos de la pila:

Ejemplo

size = len(stack)
print(size)  # Salida: 2

Ejemplo

El siguiente es un ejemplo completo que muestra cómo usar las operaciones anteriores para implementar una pila simple:

Ejemplo

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

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

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("peek from empty stack")

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

    def size(self):
        return len(self.stack)

# Ejemplo de uso
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Elemento superior:", stack.peek())  # Salida: Elemento superior: 3
print("Tamaño de la pila:", stack.size())    # Salida: Tamaño de la pila: 3

print("Elemento desapilado:", stack.pop())  # Salida: Elemento desapilado: 3
print("¿Está vacía la pila?:", stack.is_empty())  # Salida: ¿Está vacía la pila?: False
print("Tamaño de la pila:", stack.size())    # Salida: Tamaño de la pila: 2

En el código anterior, definimos una clase Stack que encapsula una lista como estructura de datos subyacente e implementa las operaciones básicas de una pila.

El resultado de salida es el siguiente:

栈顶元素: 3
栈大小: 3
弹出元素: 3
栈是否为空: False
栈大小: 2

Usar la lista como una cola

En Python, una lista puede usarse como cola, pero debido a las características de la lista, usar una lista directamente para implementar una cola no es la opción óptima.

Una cola es una estructura de datos de primero en entrar, primero en salir (FIFO, First-In-First-Out), lo que significa que el elemento agregado primero es el primero en ser eliminado.

Al usar una lista, si se insertan o eliminan elementos con frecuencia al principio de la lista, el rendimiento se verá afectado, porque estas operaciones tienen una complejidad temporal de O(n). Para resolver este problema, Python proporciona collections.deque, que es una cola doblemente terminada que puede añadir y eliminar elementos de manera eficiente en ambos extremos.

Implementar una cola con collections.deque

collections.deque es parte de la biblioteca estándar de Python y es muy adecuado para implementar colas.

A continuación se muestra un ejemplo de cómo usar deque para implementar una cola:

Ejemplo

from collections import deque

# Crear una cola vacía
queue = deque()

# Añadir elementos al final de la cola
queue.append('a')
queue.append('b')
queue.append('c')

print("Estado de la cola:", queue)  # Salida: Estado de la cola: deque(['a', 'b', 'c'])

# Eliminar un elemento del frente de la cola
first_element = queue.popleft()
print("Elemento eliminado:", first_element)  # Salida: Elemento eliminado: a
print("Estado de la cola:", queue)            # Salida: Estado de la cola: deque(['b', 'c'])

# Ver el elemento del frente de la cola (sin eliminarlo)
front_element = queue[0]
print("Elemento del frente:", front_element)    # Salida: Elemento del frente: b

# Comprobar si la cola está vacía
is_empty = len(queue) == 0
print("¿Está vacía la cola?:", is_empty)     # Salida: ¿Está vacía la cola?: False

# Obtener el tamaño de la cola
size = len(queue)
print("Tamaño de la cola:", size)            # Salida: Tamaño de la cola: 2
```

Implementar una cola con una lista

Aunque deque es más eficiente, si insistes en usar una lista para implementar una cola, también puedes hacerlo. A continuación se muestra un ejemplo de cómo usar una lista para implementar una cola:

1. Crear la cola

Ejemplo

queue = []

2. Añadir elementos al final de la cola

Usa el método append() para agregar elementos al final de la cola:

Ejemplo

queue.append('a')
queue.append('b')
queue.append('c')
print("Estado de la cola:", queue)  # Salida: Estado de la cola: ['a', 'b', 'c']

3. Eliminar elemento del frente de la cola

Usa el método pop(0) para eliminar el elemento del frente de la cola:

Ejemplo

first_element = queue.pop(0)
print("Elemento eliminado:", first_element)  # Salida: Elemento eliminado: a
print("Estado de la cola:", queue)            # Salida: Estado de la cola: ['b', 'c']

4. Ver el elemento del frente de la cola (sin eliminarlo)

Accede directamente al primer elemento de la lista:

Ejemplo

front_element = queue[0]
print("Elemento del frente:", front_element)    # Salida: Elemento del frente: b

5. Comprobar si la cola está vacía

Comprueba si la lista está vacía:

Ejemplo

is_empty = len(queue) == 0
print("¿Está vacía la cola?", is_empty)     # Salida: ¿Está vacía la cola? False

6. Obtener el tamaño de la cola

Usa la función len() para obtener el tamaño de la cola:

Ejemplo

size = len(queue)
print("Tamaño de la cola:", size)            # Salida: Tamaño de la cola: 2

Ejemplo (implementando una cola con una lista)

Ejemplo


class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("dequeue from empty queue")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("peek from empty queue")

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

    def size(self):
        return len(self.queue)

# Ejemplo de uso
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')

print("Elemento del frente:", queue.peek())    # Salida: Elemento del frente: a
print("Tamaño de la cola:", queue.size())    # Salida: Tamaño de la cola: 3

print("Elemento eliminado:", queue.dequeue())  # Salida: Elemento eliminado: a
print("¿Está vacía la cola?", queue.is_empty())  # Salida: ¿Está vacía la cola? False
print("Tamaño de la cola:", queue.size())    # Salida: Tamaño de la cola: 2

Aunque se puede usar una lista para implementar una cola, usar collections.deque es más eficiente y conciso. Proporciona operaciones de inserción y eliminación con complejidad temporal O(1), muy adecuado para este tipo de estructura de datos.

Comprensión de listas

La comprensión de listas proporciona una forma sencilla de crear listas a partir de secuencias. Normalmente, las aplicaciones realizan algunas operaciones sobre cada elemento de una secuencia y utilizan los resultados obtenidos como elementos para generar una nueva lista, o crean subsecuencias según una condición determinada.

Cada comprensión de listas consiste en una expresión seguida de una cláusula for, y luego cero o más cláusulas for o if. El resultado es una lista que se genera a partir de la expresión en el contexto de las cláusulas for e if posteriores. Si se desea que la expresión produzca una tupla, se deben usar paréntesis.

Aquí multiplicamos por tres cada valor de la lista para obtener una nueva lista:

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

Ahora hagamos algo un poco más ingenioso:

>>> [[x, x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]

Aquí invocamos un método sobre cada elemento de la secuencia uno por uno:

Ejemplo

>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']

Podemos usar la cláusula if como filtro:

>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]

A continuación se muestran algunas demostraciones sobre bucles y otras técnicas:

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

La comprensión de listas puede usar expresiones complejas o funciones anidadas:

>>> [str(round(355/113, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

Comprensión de listas anidadas

Las listas de Python también se pueden anidar.

El siguiente ejemplo muestra una lista de matriz de 3X4:

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

El siguiente ejemplo convierte una lista de matriz de 3X4 en una lista de 4X3:

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

El ejemplo anterior también se puede implementar con el siguiente método:

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Otro método de implementación:

>>> transposed = []
>>> for i in range(4):
...     # the following 3 lines implement the nested listcomp
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

La sentencia del

La sentencia del se usa para eliminar un elemento de una lista según su índice, no según su valor. Esto es diferente de pop(), que devuelve un valor. Se puede usar del para eliminar una rebanada de una lista, o vaciar toda la lista (el método que presentamos antes es asignar una lista vacía a esa rebanada). Por ejemplo:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

También se puede usar del para eliminar variables:

>>> del a

Tuplas y secuencias

Una tupla se compone de varios valores separados por comas, por ejemplo:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

Como puedes ver, las tuplas siempre se muestran entre paréntesis al imprimirlas, para expresar correctamente la estructura anidada. Al escribir una tupla, esta puede llevar o no paréntesis, aunque los paréntesis suelen ser necesarios (si la tupla forma parte de una expresión más grande).

Conjuntos

Un conjunto es una colección desordenada de elementos únicos. Sus funcionalidades básicas incluyen la prueba de pertenencia y la eliminación de duplicados.

Se pueden crear conjuntos con llaves ({}). Nota: para crear un conjunto vacío debes usar set() en lugar de {}; esto último crea un diccionario vacío, estructura de datos que presentaremos en la siguiente sección.

La siguiente es una demostración sencilla:

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # Eliminar duplicados
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # Verificar pertenencia
True
>>> 'crabgrass' in basket
False

>>> # Lo siguiente demuestra operaciones con dos conjuntos
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # Letras únicas en a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # Letras en a, pero no en b
{'r', 'd', 'b'}
>>> a | b                              # Letras en a o en b
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # Letras que están tanto en a como en b
{'a', 'c'}
>>> a ^ b                              # Letras en a o en b, pero no en ambas
{'r', 'd', 'b', 'm', 'z', 'l'}

Los conjuntos también admiten comprensiones:

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

Diccionarios

Otro tipo de dato incorporado muy útil en Python es el diccionario.

Las secuencias se indexan mediante enteros consecutivos; a diferencia de estas, los diccionarios se indexan por claves, que pueden ser de cualquier tipo inmutable, normalmente cadenas o números.

La mejor manera de entender un diccionario es verlo como un conjunto desordenado de pares clave=>valor. Dentro de un mismo diccionario, las claves deben ser distintas entre sí.

Un par de llaves crea un diccionario vacío: {}.

Este es un ejemplo sencillo del uso de diccionarios:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

El constructor dict() construye un diccionario directamente a partir de una lista de pares clave-valor como tuplas. Si hay un patrón fijo, la comprensión de listas puede especificar pares clave-valor concretos:

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}

Además, la comprensión de diccionarios se puede usar para crear diccionarios cuyas claves y valores se definen mediante expresiones arbitrarias:

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

Si las claves son simplemente cadenas, a veces es más cómodo usar argumentos de palabra clave para especificar los pares clave-valor:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}

Técnicas de iteración

Al iterar sobre un diccionario, se pueden obtener simultáneamente las claves y sus valores correspondientes usando el método items():

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad the pure
robin the brave

Al iterar sobre una secuencia, se pueden obtener a la vez el índice y el valor correspondiente usando la función enumerate():

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

Para iterar sobre dos o más secuencias a la vez, se puede usar zip() para combinarlas:

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print('What is your {0}?  It is {1}.'.format(q, a))
...
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

Para iterar sobre una secuencia en orden inverso, especifica la secuencia y luego llama a la función reversed():

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

Para iterar sobre una secuencia en orden, usa la función sorted(), que devuelve una secuencia ordenada sin modificar el valor original:

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
apple
banana
orange
pear

Ver documentación

Otras extensiones