Labs / Python OOP

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 41 Common Composite Data Types in Python - Queues (FIFO, LIFO, Priority Queue, Deque and Circular Queue)

Author: Li Zisheng · Source: FreakStudio open documentation · License: CC BY 4.0

Contents
The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 41 Common Composite Data Types in Python - Queues (FIFO, LIFO, Priority Queue, Deque and Circular Queue)

Abstract:

In Python, a queue is a commonly used data structure designed to store and access data in a specific order. The main types of queues include First-In-First-Out (FIFO), Last-In-First-Out (LIFO), priority queues, double-ended queues (Deque) and circular queues, each of which serves a unique purpose in different application scenarios.

FreakStudio's Blog

Previous Recommendations:

You who are learning embedded systems, don’t you still know Object Oriented yet? ?!

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 00 Introduction to Object Oriented Design Methodology

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 01 Basic Concepts of Object Oriented Programming

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 02 Python Implementation of Classes and Objects - Creating Classes with Python

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 03 Python Implementation of Classes and Objects – Adding Attributes to Custom Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 04 Python Implementation of Classes and Objects – Adding Methods to Custom Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 05 Python Implementation of Classes and Objects - PyCharm Code Tab

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 06 Python Implementation of Classes and Objects - Data Encapsulation of Custom Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 07 Python Implementation of Classes and Objects - Type Annotations

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 08 Python Implementation of Classes and Objects - @property Decorator

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 09 Python Implementation of Classes and Objects - Relationships Between Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 10 Python Implementation of Classes and Objects - Class Inheritance and Liskov Substitution Principle

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 11 Python Implementation of Classes and Objects - Subclass Calling Superclass Methods

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Network: 12 Python Implementation of Classes and Objects – Using Python's logging Module to Output Program Runtime Logs

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 13 Python Implementation of Classes and Objects - Installation and Usage of Sourcetrail, a Visual Code Reading Tool

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 14 Python Implementation of Classes and Objects – Static Methods and Class Methods of Classes

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 15 Python Implementation of Classes and Objects - the __slots__ Magic Method

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Network: 16 Python Implementation of Classes and Objects - Polymorphism, Method Overriding and Open Closed Principle

The most beginner-friendly Object Oriented programming tutorial on the entire network: 17 Python implementation of classes and objects - duck typing and "file-like object"

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 18 Python Implementation of Classes and Objects - Multiple Inheritance and Serial Port Data Curve Plotting with PyQtGraph

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 19 Python Implementation of Classes and Objects – Automatically Generate File Comments and function Comments with PyCharm

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 20 Python Implementation of Classes and Objects – Implementation of Composition Relationship and CSV File Saving

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 21 Python Implementation of Classes and Objects - Multi-File Organization: Module and Package

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 22 Python Implementation of Classes and Objects - Exceptions and Syntax Errors

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 23 Python Implementation of Classes and Objects - Throwing Exceptions

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 24 Python Implementation of Classes and Objects - Exception Catching and Handling

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 25 Python Implementation of Classes and Objects - Python Determines the Type of Input Data

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Network: 26 Python Implementation of Classes and Objects - Context Managers and the with Statement

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 27 Python Implementation of Classes and Objects - Exception Hierarchy and Custom Exception Class Implementation in Python

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 28 Python Implementation of Classes and Objects - A Comprehensive Summary of Python Programming Principles, Philosophy and Specifications

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 29 Python Implementation of Classes and Objects - Assertions, Defensive Programming and the Usage of the help function

The Best Entry-Level Object Oriented Programming Tutorial Across the Network: 30 Built-in Data Types in Python - The object Root Class

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 31 Python's Built-in Data Types - Object and Type

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 32 Python's Built-in Data Types - Class and Instance

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 33 Python's Built-in Data Types – The Relationship Between Object and Type

The Most Beginner-Friendly Object Oriented Programming Course on the Whole Network: 34 Python's Built-in Data Types - Common Composite Data Types in Python: Tuples and Named Tuples

The Most Beginner-Friendly Object Oriented Programming Tutorial Across the Web: 35 Python's Built-in Data Types – Docstrings and the __doc__ Attribute

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 36 Python's Built-in Data Type - Dictionary

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 37 Common Composite Data Types in Python - Lists and List Comprehensions

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 38 Common Composite Data Types in Python – Implementing stack, Queue and Deque with Lists

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 39 Common Composite Data Types in Python – Sets

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 40 Common Composite Data Types in Python - Enumerations and Usage of the enum Module

For more exciting content, you can check out:

Speed Up Your Python: A Quick Guide to Python Parallel Computing

Understand the Debugging Principle of CM3 Microcontrollers in One Article

After half a month of dedicated grinding, the ultimate summary of embedded technology stack is now released

The "Secret Martial Arts Manual" for Computer Science Competitions

Avnet ZUBoard 1CG Development Board — A New Choice for Deep learning

SenseCraft deploys models to the Grove Vision AI V2 image processing module

Document and Code Acquisition:

You can download the document via the following link:

https://github.com/leezisheng/Doc

v1.2 19 4 1 0

This document mainly introduces how to use Python for Object Oriented programming, which requires readers to have a basic understanding of Python syntax and microcontroller development. Compared with other blogs or books that explain Python Object Oriented programming, this document is more detailed and focuses on embedded host computer applications, taking the common serial port data transmission and reception, data processing, dynamic graph drawing and other functions between the host computer and the slave computer as application examples. Meanwhile, it uses the Sourcetrail code software to visualize the code for reading to facilitate readers' understanding.

The link to obtain the relevant sample code is as follows:

https://github.com/leezisheng/Python-OOP-Demo

Body Text

As a specific data structure, a queue, just like a set, can fully have its functions implemented via a list. A queue is a special linear list, whose particularity lies in that it only allows deletion operations at the front end and insertion operations at the rear end; similar to the behavior pattern of a stack, it is a restricted linear list. The end where insertion operations are performed is called the rear of the queue, the end where deletion operations are performed is called the front of the queue, and its core concept is "First-In, First-Out (FIFO)".

In Python, the Queue module provides a set of synchronized and thread-safe queue classes, including the common FIFO (First-In-First-Out) queue, LIFO (Last-In-First-Out) queue, PriorityQueue, as well as the SimpleQueue which is a FIFO-type simple queue.

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 41 Common Composite Data Types in Python - Queues (FIFO, LIFO, Priority Queue, Deque and Circular Queue)

The basic operation methods of the queue are as follows:

Method

Description

Q.qsize()

Returns the size of the queue.

Q.empty()

If the queue is empty, return True; otherwise, return False.

Q.full()

If the queue is full, return True; otherwise, return False.

Q.get([block[, timeout]])

Retrieve the queue, with the timeout as the waiting period.

Q.get_nowait()

Equivalent to Queue.get (False), a non-blocking method.

Q.put(item)

Write queue, timeout waiting period.

Q.task_done()

The task_done () call tells the queue that the task has been processed.

Q.join()

which actually means waiting until the queue is empty before performing other operations

FIFO queue

FIFO, short for First In First Out, is the most common definition we have for a queue. Imagine a line of people waiting at a bank or an ATM: the person at the front of the line is usually served first, and those behind follow in order. This is exactly how Python's Queue class works.

The Queue class is typically used as a communication medium when some objects generate data that other objects need to consume, potentially at different speeds. Imagine a messaging app that receives messages from the network but can only display one message to the user at a time; the remaining messages are cached in a queue in the order they are received.

The Queue class is an ideal choice when you only need to access the data in the data structure when the next object is to be consumed. In this case, using a list would be inefficient, as inserting (or removing) data at the head of the list requires shifting all the remaining elements.

import queue
# If no length is set, it is unbounded by default
q = queue.Queue(5)
# Note there are no parentheses
print(q.maxsize)
q.put(123)
q.put(456)
q.put(789)
q.put(100)
print(q.get())
print(q.get())
print(q.get())

The running results are as follows:

5 123 456 789 0

LIFO queue

LIFO stands for "Last In First Out", and a LIFO queue is commonly referred to as a stack. We can take a stack of papers as a vivid analogy: you can only take the top one each time. You can place another sheet on top to make it the new top layer, or remove the top sheet to reveal the one beneath it.

By convention, operations performed on a stack are referred to as push and pop, but Python's queue module uses exactly the same API as FIFO queues: put () and get (). The only difference is that in a LIFO queue, these methods operate on the "top" of the stack rather than on the front and rear of a queue.(In fact, both LIFO and FIFO queues inherit from the same parent class, implementing different operations within the same methods — which is a very good example of polymorphism in Object Oriented programming as we discussed earlier.)

The underlying implementation of a LIFO queue is a standard list; compared with a regular list, a LIFO queue supports concurrent access by multiple threads, and it enforces the use of a stack interface. You cannot arbitrarily insert a value into an incorrect position in a LIFO queue.

from queue import LifoQueue

# Create an object
lifoQueue = LifoQueue()
lifoQueue.put(1)
lifoQueue.put(2)
lifoQueue.put(3)
print(lifoQueue.queue)

# Return and remove the element at the tail of the queue
print(lifoQueue.get())

print(lifoQueue.queue)

The running results are as follows:

1 2 3 0

priority queue

Priority queues enforce a style of ordering that is drastically different from the queue implementations we have covered previously. They still use the same get () and put () function, but the difference is that instead of returning elements in the order they were added, they return the "most important" element first. By convention, the most important, or highest priority, element is the one that sorts lowest using the less-than operator.

Typically, a tuple is stored in a priority queue, where the first element of the tuple represents its priority and the second element is the data; another common paradigm is to implement the __lt__ method (it cannot be guaranteed which element will be returned first when multiple elements in the queue have the same priority).

Priority queues are extremely useful in many practical applications, such as task scheduling, network traffic control, and certain algorithms in Machine Learning. Taking task scheduling as an example, a priority queue can be used to manage a set of tasks. Each task has a priority value, and the task with the highest priority value is executed first. By using a priority queue, it can be ensured that high-priority tasks can be processed in a timely manner.

If the queue is empty, the get () method will block (by default); if the queue is non-empty, it will not block, nor will it wait for elements with higher priority to be added. The queue pays no attention to elements that have not yet been added (or even elements that have already been extracted), and only makes decisions based on the current contents of the queue.

import queue

# Create a priority queue
q = queue.PriorityQueue()
# put a tuple, in the format (priority, data)
# The smaller the number, the higher the priority
q.put((4,'aaaaa'))
q.put((3,'bbbbb'))
q.put((2,'ccccc'))
q.put((1,'ddddd'))
print(q.get())
print(q.get())
print(q.get())
print(q.get())

The following are the operation results:

1 2 3 4 0

Common implementations of priority queues are based on the heap data structure. The Python implementation leverages the heapq module to efficiently store a heap in an ordinary list. A detailed introduction to heaps will be provided later in this document.

Deque

A double-ended queue, abbreviated as Deque, shares the same name with the dequeue operation of a queue but refers to a different concept. In computer science, a double-ended queue (abbreviated as deque) is an abstract data type that generalizes a queue, where elements can be added or removed from either the front (head) or the back (tail). It is therefore also often referred to as a head-tail linked list.

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 41 Common Composite Data Types in Python - Queues (FIFO, LIFO, Priority Queue, Deque and Circular Queue)

There are two types of deques:

(1) Input-restricted deque: In this type of queue, input is restricted to one end, while deletion can be performed from both ends simultaneously;

(2) Output-restricted deque: This type of queue only allows deletion at one end, while elements can be inserted at both ends.

1

Deques have a wide range of practical applications, some of which include:

The following is sample code for deque-related operations. First, we need to import the collections module, which implements some specialized containers that provide supplements to Python's general built-in containers dict, list, set and tuple:

from collections import deque

# Create a double-ended queue
deque_obj = deque()

# Insert an element at the head
deque_obj.appendleft(10)
deque_obj.appendleft(15)
deque_obj.appendleft(20)

# Insert an element at the tail
deque_obj.append(25)
deque_obj.append(30)
print(deque_obj)

# Rotate right 2 times
deque_obj.rotate(2)
print(deque_obj)

# Delete an element from the head
front = deque_obj.popleft()
print(front)

#Delete an element from the tail
rear = deque_obj.pop()
print(rear)

print(deque_obj)

The following are the operation results:

20 15 10 25 30

circular queue

In a normal queue, once the queue becomes full, we cannot insert the next element even if there is still space at the front of the queue. In this case, we can use a circular queue to utilize the previously occupied space of the queue, and with a circular queue, we can use these spaces to store new values. A circular queue is a linear data structure whose operations follow the FIFO (First-In-First-Out) principle and has the rear of the queue connected to the front of the queue to form a loop. It is also known as a "ring buffer".

The Most Beginner-Friendly Object Oriented Programming Tutorial on the Whole Network: 41 Common Composite Data Types in Python - Queues (FIFO, LIFO, Priority Queue, Deque and Circular Queue)

A circular queue can be logically regarded as a ring: when the front pointer moves one position further after being equal to the queue length minus one unit, it will automatically return to 0, which is essentially the modulo operation. We can use the deque in Python's collections module to implement a circular queue. When creating a deque, you can specify the maximum length with collections.deque (maxlen= x); if maxlen is not specified or is set to None, the deque can grow to any length.Otherwise, the deque is limited to the specified maximum length. When the deque is full and new items are added, the same number of items will be popped from the other end. The sample code is as follows:

from collections import deque

# Create a circular queue of size 3
queue = deque(maxlen=3)

# Add elements
queue.append('a')
queue.append('b')
queue.append('c')

# Adding a fourth element causes the first element to be popped
queue.append('d')
print(queue) 

The following are the operation results:

3 0
347622978