Praca z kolejkami

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software Engineer

Kolejki

FIFO: First-In First-Out
- Element dodany jako pierwszy jest pierwszy do usunięcia

Kolejki

FIFO: First-In First-Out
- Element dodany jako pierwszy jest pierwszy do usunięcia

Kolejki

FIFO: First-In First-Out
- Element dodany jako pierwszy jest pierwszy do usunięcia

Kolejki – struktura

Schematyczne przedstawienie kolejki z nazwami międzynarodowych potraw.

Kolejki – struktura

Schematyczne przedstawienie kolejki z nazwami międzynarodowych potraw. Słowo "head" wskazuje początek kolejki.

Początek: head

Kolejki – struktura

Schematyczne przedstawienie kolejki z nazwami międzynarodowych potraw. Słowo "tail" wskazuje koniec kolejki.

Początek: head
Koniec: tail

Kolejki – właściwości

Schematyczne przedstawienie kolejki z nazwami dwóch międzynarodowych potraw. Słowo "head" wskazuje początek kolejki, a słowo "tail" jej koniec.

Kolejki – właściwości

Schematyczne przedstawienie kolejki. Nowy element został wstawiony na końcu kolejki.

Wstawianie tylko na końcu
- Enqueue

Kolejki – właściwości

Schematyczne przedstawienie kolejki. Pierwszy element jest przekreślony, ponieważ zostanie usunięty.

Wstawianie tylko na końcu
- Enqueue
Usuwanie tylko z początku

Kolejki – właściwości

Schematyczne przedstawienie kolejki z dwoma elementami, ponieważ pierwszy element został usunięty.

Wstawianie tylko na końcu
- Enqueue
Usuwanie tylko z początku
- Dequeue
Inne rodzaje kolejek:
- Kolejki dwustronne
- Kolejki cykliczne
- Kolejki priorytetowe

Kolejki – zastosowania w praktyce

Zadania drukowania w drukarce
- Dokumenty są drukowane w kolejności wpłynięcia
Aplikacje, w których kolejność żądań ma znaczenie
- Bilety na koncert
- Usługi taksówkowe

Kolejki – implementacja

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

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

Kolejki – enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Schematyczne przedstawienie kolejki z jednym elementem zaimplementowanym jako węzeł.

Kolejki – enqueue

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

Schematyczne przedstawienie kolejki z jednym węzłem. Słowa "head" i "tail" wskazują na węzeł.

Kolejki – enqueue

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

  else:

Schematyczne przedstawienie kolejki z dwoma elementami. Nowy węzeł jest przygotowany do wstawienia.

Kolejki – 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

Schematyczne przedstawienie kolejki z trzema elementami. Słowo "tail" nadal wskazuje na drugi węzeł.

Kolejki – 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

Schematyczne przedstawienie kolejki z trzema elementami. Słowo "tail" wskazuje na ostatnio wstawiony węzeł.

Kolejki – dequeue

Schematyczne przedstawienie kolejki z trzema elementami. Słowo "head" wskazuje pierwszy węzeł, a słowo "tail" ostatni.

def dequeue(self):

  if self.head:

Kolejki – dequeue

Schematyczne przedstawienie kolejki z trzema elementami. Słowa "head" i "current_node" wskazują pierwszy węzeł, a słowo "tail" ostatni.

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

Kolejki – dequeue

Schematyczne przedstawienie kolejki z trzema elementami. Słowo "head" wskazuje pierwszy węzeł, "current_node" drugi, a "tail" ostatni.

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

Kolejki – dequeue

Schematyczne przedstawienie kolejki z dwoma elementami. Słowo "head" wskazuje pierwszy węzeł, a "tail" ostatni. Poza kolejką znajduje się węzeł ze słowem "current_node".

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

Kolejki – dequeue

Węzeł ze słowami "current_node" i "tail" wskazującymi na niego. Słowo "head" wskazuje null.

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


    if self.head == None:

Kolejki – dequeue

Węzeł ze słowem "current_node" wskazującym na niego. Słowa "head" i "tail" wskazują 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 w Pythonie

Moduł: 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

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie