Estructuras de datos: pilas y colas¶

Pilas¶

Método LIFO (Last in First out)

PUSH: agrega un elemento a la colección
POP: elimina el elemento agregado más recientemente

Ejemplo:

Una pila de libros puestos en vertical sobre una mesa

LIFO	PILA

In [1]:

# Se trabaja con listas.
libros = ["Quijote", "Celestina", "Principito"]
# si fuera una pila de libros puestos en vertical, abajo estaría el Quijote y arriba el Principito

Añadiendo elementos¶

Se añaden por la derecha con append.

In [2]:

libros.append("La Odisea")
libros

Out[2]:

['Quijote', 'Celestina', 'Principito', 'La Odisea']

Eliminando elementos¶

Se eliminan por la derecha con pop. El último en llegar es el primero en salir.

In [3]:

libros.pop()                              # devuelve el último elemento de la lista y lo elimina

Out[3]:

'La Odisea'

In [4]:

libros                                    # observamos que 'La Odisea' ha sido eliminada de la lista

Out[4]:

['Quijote', 'Celestina', 'Principito']

In [5]:

eliminado = libros.pop()                  # podemos guardar en una variable el elemento eliminado
print(libros)
eliminado

['Quijote', 'Celestina']

Out[5]:

'Principito'

Colas¶

Método FIFO (First in First out)
Ejemplo:

La cola de un establecimiento

FIFO	QUEUE

Crear una cola¶

Usamos deque de la librería collections.

In [6]:

from collections import deque
cola = deque()                    # creando una cola vacía
cola

Out[6]:

deque([])

Añadir elementos a la cola¶

Para añadir elementos a una cola podemos pasar una lista al objeto deque.

In [7]:

cola = deque(['Ana', 'Jose', 'Eva'])  # Primero llegó Ana a la cola

In [8]:

cola.append('Luis')
cola.append('Bea')                  # Bea es la última en llegar
cola

Out[8]:

deque(['Ana', 'Jose', 'Eva', 'Luis', 'Bea'])

Sacar elementos de la cola¶

El primer usuario al que atenderemos es al primero que llegó.
Los elementos se sacan por la izquierda con popleft.

El método popleft no funciona en las listas solo en las queue.

In [9]:

cola.popleft()                    # Atendemos a Ana

Out[9]:

'Ana'

In [10]:

cola

Out[10]:

deque(['Jose', 'Eva', 'Luis', 'Bea'])

In [11]:

atendido = cola.popleft()         # Podemos guardar en una variable los elementos eliminados
atendido

Out[11]:

'Jose'

In [12]:

cola

Out[12]:

deque(['Eva', 'Luis', 'Bea'])

Ejercicio¶

Nos proporcionan una lista con las fases para la creación de un proyecto tecnológico.

In [13]:

fases = ['Identificación','Exploración','Diseño','Planificación','Construcción','Evaluación','Divulgación']

Nos piden que asociemos cada fase con su número y las incorporemos a una lista para formar una matriz 7 x 2.

In [14]:

l=[[i+1,fases[i]]for i in range(len(fases))]
l

Out[14]:

[[1, 'Identificación'],
 [2, 'Exploración'],
 [3, 'Diseño'],
 [4, 'Planificación'],
 [5, 'Construcción'],
 [6, 'Evaluación'],
 [7, 'Divulgación']]

Desordenamos las fases.

In [15]:

from random import shuffle
shuffle(l)
l

Out[15]:

[[3, 'Diseño'],
 [1, 'Identificación'],
 [5, 'Construcción'],
 [6, 'Evaluación'],
 [7, 'Divulgación'],
 [4, 'Planificación'],
 [2, 'Exploración']]

Se pide:
usando colas, mostrar el listado de las fases ordenadas y sin número.

In [16]:

# primero ordenamos las fases
l.sort()
l

Out[16]:

[[1, 'Identificación'],
 [2, 'Exploración'],
 [3, 'Diseño'],
 [4, 'Planificación'],
 [5, 'Construcción'],
 [6, 'Evaluación'],
 [7, 'Divulgación']]

In [17]:

from collections import deque
cola = deque()                    # creando una cola vacía
for fase in fases:
    cola.append(fase)
cola

Out[17]:

deque(['Identificación',
       'Exploración',
       'Diseño',
       'Planificación',
       'Construcción',
       'Evaluación',
       'Divulgación'])

In [18]:

for fase in cola:
    print(fase)

Identificación
Exploración
Diseño
Planificación
Construcción
Evaluación
Divulgación

Ver que fase sería la que toca realizar.

In [19]:

cola.popleft()

Out[19]:

'Identificación'