Trabalhando com filas

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software Engineer

Filas

• FIFO: First-In First-Out

  • O primeiro inserido é o primeiro a ser removido

    

Filas

• FIFO: First-In First-Out

  • O primeiro inserido é o primeiro a ser removido

    

Filas

• FIFO: First-In First-Out

  • O primeiro inserido é o primeiro a ser removido

    

Filas - estrutura

Filas - estrutura

• Início: head

Filas - estrutura

• Início: head
• Fim: tail

Filas - características

Filas - características

• Só pode inserir no fim
  • Enqueue

Filas - características

• Só pode inserir no fim
  • Enqueue
• Só pode remover do início

Filas - características

• Só pode inserir no fim
  • Enqueue
• Só pode remover do início
  • Dequeue
• Outros tipos de filas:
  • Duplamente terminadas
  • Circulares
  • De prioridade

Filas - casos de uso reais

• Tarefas de impressão na impressora
  • Documentos são impressos na ordem de chegada
• Aplicações onde a ordem dos pedidos importa
  • Ingressos para shows
  • Serviços de táxi

Filas - implementação

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

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

Filas - enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Filas - enqueue

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

Filas - enqueue

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

  else:

Filas - 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

Filas - 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      

Filas - dequeue

def dequeue(self):

  if self.head:

Filas - dequeue

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

Filas - dequeue

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

Filas - dequeue

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

Filas - dequeue

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


    if self.head == None:

Filas - dequeue

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 em 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 praticar!

Estruturas de Dados e Algoritmos em Python