Working with queues

Data Structures and Algorithms in Python

Miriam Antona

Software Engineer

Queues

  • FIFO: First-In First-Out

    • First inserted item is the first to be removed

      A picture of a supermarket line with three persons in it.

Data Structures and Algorithms in Python

Queues

  • FIFO: First-In First-Out

    • First inserted item is the first to be removed

      A picture of a supermarket line with two persons in it because the first person left the queue.

Data Structures and Algorithms in Python

Queues

  • FIFO: First-In First-Out

    • First inserted item is the first to be removed

      A picture of a supermarket line with one person in it because the first and the second people left the queue.

Data Structures and Algorithms in Python

Queues - structure

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

Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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.

Data Structures and Algorithms in Python

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:
Data Structures and Algorithms in Python

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





Data Structures and Algorithms in Python

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




Data Structures and Algorithms in Python

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




Data Structures and Algorithms in Python

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:
Data Structures and Algorithms in Python

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    
Data Structures and Algorithms in Python

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
Data Structures and Algorithms in Python

Let's practice!

Data Structures and Algorithms in Python

Preparing Video For Download...