Att arbeta med köer

Datastrukturer och algoritmer i Python

Miriam Antona

Software Engineer

Köer

• FIFO: First-In First-Out

  • Det först tillagda elementet är det första som tas bort

    

Köer

• FIFO: First-In First-Out

  • Det först tillagda elementet är det första som tas bort

    

Köer

• FIFO: First-In First-Out

  • Det först tillagda elementet är det första som tas bort

    

Köer – struktur

Köer – struktur

• Början: head

Köer – struktur

• Början: head
• Slut: tail

Köer – egenskaper

Köer – egenskaper

• Kan bara lägga till i slutet
  • Enqueue

Köer – egenskaper

• Kan bara lägga till i slutet
  • Enqueue
• Kan bara ta bort från head

Köer – egenskaper

• Kan bara lägga till i slutet
  • Enqueue
• Kan bara ta bort från head
  • Dequeue
• Andra typer av köer:
  • Dubbeländade köer
  • Cirkulära köer
  • Prioritetsköer

Köer – användningsområden

• Utskriftsjobb i en skrivare
  • Dokument skrivs ut i den ordning de tas emot
• Tillämpningar där ordningen på förfrågningar spelar roll
  • Biljetter till en konsert
  • Taxitjänster

Köer – implementation

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

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

Köer – enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Köer – enqueue

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

Köer – enqueue

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

  else:

Köer – 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

Köer – 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      

Köer – dequeue

def dequeue(self):

  if self.head:

Köer – dequeue

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

Köer – dequeue

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

Köer – dequeue

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

Köer – dequeue

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


    if self.head == None:

Köer – 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 i Python

• Modul: 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

Nu kör vi en övning!

Datastrukturer och algoritmer i Python