Lucrul cu cozi

Structuri de date și algoritmi în Python

Miriam Antona

Software Engineer

Cozi

FIFO: First-In First-Out
- Primul element inserat este primul eliminat

Cozi

FIFO: First-In First-Out
- Primul element inserat este primul eliminat

Cozi

FIFO: First-In First-Out
- Primul element inserat este primul eliminat

Cozi - structură

Reprezentare schematică a unei cozi cu numele unor preparate internaționale.

Cozi - structură

Reprezentare schematică a unei cozi cu numele unor preparate internaționale. Cuvântul „head" indică începutul cozii.

Început: head

Cozi - structură

Reprezentare schematică a unei cozi cu numele unor preparate internaționale. Cuvântul „tail" indică sfârșitul cozii.

Început: head
Sfârșit: tail

Cozi - caracteristici

Reprezentare schematică a unei cozi cu numele a două preparate internaționale. Cuvântul „head" indică începutul cozii, iar „tail" - sfârșitul.

Cozi - caracteristici

Reprezentare schematică a unei cozi. Un nou element a fost inserat la sfârșitul cozii.

Inserarea se face doar la sfârșit
- Enqueue

Cozi - caracteristici

Reprezentare schematică a unei cozi. Primul element este tăiat deoarece va fi eliminat.

Inserarea se face doar la sfârșit
- Enqueue
Eliminarea se face doar din head

Cozi - caracteristici

Reprezentare schematică a unei cozi. Coada are doar două elemente deoarece primul a fost eliminat.

Inserarea se face doar la sfârșit
- Enqueue
Eliminarea se face doar din head
- Dequeue
Alte tipuri de cozi:
- Cozi cu două capete
- Cozi circulare
- Cozi cu priorități

Cozi - cazuri de utilizare reale

Sarcini de tipărire la imprimantă
- Documentele sunt tipărite în ordinea primirii
Aplicații în care ordinea cererilor contează
- Bilete pentru un concert
- Servicii de taxi

Cozi - implementare

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

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

Cozi - enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Reprezentare schematică a unei cozi cu un singur element, implementată cu un nod.

Cozi - enqueue

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

Reprezentare schematică a unei cozi cu un singur element, implementată cu un nod. Cuvintele „head" și „tail" indică nodul.

Cozi - enqueue

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

  else:

Reprezentare schematică a unei cozi cu două elemente. Un nod nou este pregătit pentru inserare.

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

Reprezentare schematică a unei cozi cu trei elemente. Cuvântul „tail" indică în continuare al doilea nod.

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

Reprezentare schematică a unei cozi cu trei elemente. Cuvântul „tail" indică ultimul nod inserat.

Cozi - dequeue

Reprezentare schematică a unei cozi cu trei elemente. „head" indică primul nod, „tail" indică ultimul nod.

def dequeue(self):

  if self.head:

Cozi - dequeue

Reprezentare schematică a unei cozi cu trei elemente. „head" și „current_node" indică primul nod, „tail" indică ultimul nod.

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

Cozi - dequeue

Reprezentare schematică a unei cozi cu trei elemente. „head" indică primul nod, „current_node" indică al doilea, „tail" indică ultimul nod.

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

Cozi - dequeue

Reprezentare schematică a unei cozi cu două elemente. „head" indică primul nod, „tail" indică ultimul. Un nod separat este indicat de „current_node".

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

Cozi - dequeue

Un nod indicat de „current_node" și „tail". „head" indică null.

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


    if self.head == None:

Cozi - dequeue

Un nod indicat de „current_node". „head" și „tail" indică 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 în 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

Ayo berlatih!

Structuri de date și algoritmi în Python