Working with queues

Strutture dati e algoritmi in Python

Miriam Antona

Software Engineer

Queues

FIFO: First-In First-Out
- First inserted item is the first to be removed

Queues

FIFO: First-In First-Out
- First inserted item is the first to be removed

Queues

FIFO: First-In First-Out
- First inserted item is the first to be removed

Queues - structure

Schematic representation of a queue with the names of some international dishes.

Queues - structure

Schematic representation of a queue with the names of some international dishes. The word "head" points at the beginning of the queue.

Beginning: head

Queues - structure

Schematic representation of a queue with the names of some international dishes. The word "tail" points at the end of the queue.

Beginning: head
End: tail

Queues - features

Schematic representation of a queue with the names of two international dishes. The word "head" points at the beginning of the queue and the word "tail" at the end.

Queues - features

Schematic representation of a queue. A new element has been inserted at the tail of the queue.

Can only insert at the end
- Enqueue

Queues - features

Schematic representation of a queue. The first element of the queue is crossed out because it will be removed.

Can only insert at the end
- Enqueue
Can only remove from the head

Queues - features

Schematic representation of a queue. The queue has only two elements because the first element has been removed.

Can only insert at the end
- Enqueue
Can only remove from the head
- Dequeue
Other kinds of queues:
- Doubly ended queues
- Circular queues
- Priority queues

Queues - real-world use cases use

Printing tasks in a printer
- Documents are printed in the order they are received
Applications where the order of requests matters
- Tickets for a concert
- Taxi services

Queues - implementation

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

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

Queues - enqueue

def enqueue(self,data):

  new_node = Node(data)

  if self.head == None:

Schematic representation of a queue that has one element. The queue has been implemented with a node.

Queues - enqueue

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

Schematic representation of a queue that has one element. The queue has been implemented with a node. The words "head" and "tail" point to the node.

Queues - enqueue

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

  else:

Schematic representation of a queue that has two elements. The queue has been implemented with nodes. A new node is prepared to be inserted.

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

Schematic representation of a queue that has three elements. The word "tail" still points to the second node.

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

Schematic representation of a queue that has three elements. The word "tail" points to the last inserted node.

Queues - dequeue

Schematic representation of a queue that has three elements. The word "head" points to the first node and the word "tail" points to the last node.

def dequeue(self):

  if self.head:

Queues - dequeue

Schematic representation of a queue that has three elements. The words "head" and "current_node" point to the first node and the word "tail" points to the last node.

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

Queues - dequeue

Schematic representation of a queue that has three elements. The word "head" points to the first node, the word "current_node" point to the second word, and the word "tail" points to the last node.

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

Queues - dequeue

Schematic representation of a queue that has two elements. The word "head" points to the first node, and the word "tail" points to the last node. There is another node apart from the queue with the word "current_node" pointing to it.

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

Queues - dequeue

A node with the words "current_node" and "tail" pointing to it. The word "head" points to null.

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


    if self.head == None:

Queues - dequeue

A node with the word "current_node" pointing to it. The word "head" and "tail" point to 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 in Python

Module: 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

Let's practice!

Strutture dati e algoritmi in Python