Trabajar con colas

Estructuras de datos y algoritmos en Python

Miriam Antona

Software Engineer

Colas

FIFO: First-In First-Out
- El primero en entrar es el primero en salir

Colas

FIFO: First-In First-Out
- El primero en entrar es el primero en salir

Colas

FIFO: First-In First-Out
- El primero en entrar es el primero en salir

Colas: estructura

Representación esquemática de una cola con nombres de platos internacionales.

Colas: estructura

Representación esquemática de una cola con nombres de platos internacionales. La palabra "head" señala el inicio de la cola.

Inicio: head

Colas: estructura

Representación esquemática de una cola con nombres de platos internacionales. La palabra "tail" señala el final de la cola.

Inicio: head
Final: tail

Colas: características

Representación esquemática de una cola con los nombres de dos platos internacionales. La palabra "head" señala el inicio de la cola y la palabra "tail" el final.

Colas: características

Representación esquemática de una cola. Se ha insertado un nuevo elemento al final de la cola.

Solo se inserta al final
- Enqueue

Colas: características

Representación esquemática de una cola. El primer elemento de la cola está tachado porque se eliminará.

Solo se inserta al final
- Enqueue
Solo se elimina desde el inicio

Colas: características

Representación esquemática de una cola. La cola tiene solo dos elementos porque se eliminó el primero.

Solo se inserta al final
- Enqueue
Solo se elimina desde el inicio
- Dequeue
Otros tipos de colas:
- Doble extremo
- Circulares
- De prioridad

Colas: casos de uso reales

Tareas de impresión en una impresora
- Se imprimen en el orden de llegada
Aplicaciones donde importa el orden de las solicitudes
- Entradas para un concierto
- Servicios de taxi

Colas: implementación

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

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

Colas: enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Representación esquemática de una cola con un elemento. La cola se implementó con un nodo.

Colas: enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

Representación esquemática de una cola con un elemento. La cola se implementó con un nodo. Las palabras "head" y "tail" señalan el nodo.

Colas: enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:

Representación esquemática de una cola con dos elementos. La cola se implementó con nodos. Un nuevo nodo está listo para insertarse.

Colas: enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node

Representación esquemática de una cola con tres elementos. La palabra "tail" aún señala al segundo nodo.

Colas: enqueue

def enqueue(self,data):
  new_node = Node(data)
  if self.head == None:
    self.head = new_node
    self.tail = new_node

  else:
    self.tail.next = new_node
    self.tail = new_node

Representación esquemática de una cola con tres elementos. La palabra "tail" señala al último nodo insertado.

Colas: dequeue

Representación esquemática de una cola con tres elementos. La palabra "head" señala al primer nodo y la palabra "tail" al último.

def dequeue(self):

  if self.head:

Colas: dequeue

Representación esquemática de una cola con tres elementos. Las palabras "head" y "current_node" señalan al primer nodo y la palabra "tail" al último.

def dequeue(self):
  if self.head:
    current_node = self.head

Colas: dequeue

Representación esquemática de una cola con tres elementos. La palabra "head" señala al primer nodo, "current_node" al segundo y "tail" al último.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next

Colas: dequeue

Representación esquemática de una cola con dos elementos. La palabra "head" señala al primer nodo y "tail" al último. Hay otro nodo fuera de la cola con la palabra "current_node" señalándolo.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

Colas: dequeue

Un nodo con las palabras "current_node" y "tail" señalándolo. La palabra "head" señala a null.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None


    if self.head == None:

Colas: dequeue

Un nodo con la palabra "current_node" señalándolo. Las palabras "head" y "tail" señalan a null.

def dequeue(self):
  if self.head:
    current_node = self.head
    self.head = current_node.next
    current_node.next = None

    if self.head == None:
      self.tail = None

SimpleQueue en Python

Módulo: queue
- Queue
- SimpleQueue

import queue


orders_queue = queue.SimpleQueue()


orders_queue.put("Sushi")
orders_queue.put("Lasagna")
orders_queue.put("Paella")


print("The size is: ", orders_queue.qsize())

The size is: 3

print(orders_queue.get())
print(orders_queue.get())
print(orders_queue.get())

Sushi
Lasagna
Paella

print("Empty queue: ", orders_queue.empty())

Empty queue: True

¡Vamos a practicar!

Estructuras de datos y algoritmos en Python