Подібно до стека, черга — це лінійна структура даних, яка зберігає елементи в системі «Першим прийшов, першим вийшов» ( FIFO ) способом. У черзі спочатку видаляється останній нещодавно доданий елемент. Хорошим прикладом черги є будь-яка черга споживачів для ресурсу, де споживач, який був першим, обслуговується першим.

Операції, пов’язані з чергою:

• Поставити в чергу: Додає елемент до черги. Якщо черга заповнена, це вважається умовою переповнення – Часова складність: O(1)
• Відповідно: Вилучає елемент із черги. Елементи висуваються в тому самому порядку, в якому вони натискаються. Якщо черга порожня, то це вважається умовою недостатнього переповнення – Часова складність: O(1)
• Спереду: Отримати перший елемент із черги – Часова складність: O(1)
• задній: Отримати останній елемент із черги – Часова складність: O(1)

Реалізація черги в Python

Існують різні способи реалізації черги Python. У цій статті розглядається реалізація черги з використанням структур даних і модулів із бібліотеки Python. Черга Python може бути реалізована такими способами:

• список
• колекції.deque
• хвіст.хвіст

Реалізація за допомогою списку

Список — це вбудована структура даних Python, яку можна використовувати як чергу. Замість enqueue() і відповідно () , додати() і поп() використовується функція. Однак списки досить повільні для цієї мети, тому що вставлення або видалення елемента на початку вимагає зсуву всіх інших елементів на один, вимагаючи O(n) часу.
Код імітує чергу за допомогою списку Python. Це додає елементи 'а' , «б» , і «c» до черги, а потім вилучає їх із черги, що призводить до порожньої черги в кінці. Вихідні дані показують початкову чергу, елементи, вилучені з черги ( 'а' , «б» , «c» ), і стан черги порожній.

Python3

>

>

Вихід:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements []>

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list>

Реалізація за допомогою collections.deque

Черга в Python може бути реалізована за допомогою класу deque з модуля collections. Deque є кращим над списком у випадках, коли нам потрібні швидші операції додавання та висування з обох кінців контейнера, оскільки deque забезпечує O(1) часову складність для операцій додавання та витягування порівняно зі списком, який забезпечує O(n) часову складність . Замість enqueue і deque використовуються функції append() і popleft().
Код використовує adeque>відcollections>модуль для представлення черги. Це додається 'а' , «б» , і «c» до черги та вилучає їх із черги q.popleft()> , що призводить до порожньої черги. Розкоментування q.popleft()> після того, як черга спорожніє, буде створено anIndexError>. Код демонструє операції з чергою та обробляє сценарій порожньої черги.

Python3

java упс поняття

>

>

Вихід:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([])>

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque>

Реалізація за допомогою queue.Queue

Queue — це вбудований модуль Python, який використовується для реалізації черги. queue.Queue(maxsize) ініціалізує змінну до максимального розміру maxsize. Максимальний розмір нуля «0» означає нескінченну чергу. Ця черга відповідає правилу FIFO.
У цьому модулі доступні різні функції:

• максимальний розмір – Кількість елементів, дозволених у черзі.
• порожній() – Повертає True, якщо черга порожня, False в іншому випадку.
• повний() – Повертає True, якщо в черзі є елементи максимального розміру. Якщо чергу було ініціалізовано з maxsize=0 (за замовчуванням), то full() ніколи не повертає True.
• отримати() – Видалення та повернення елемента з черги. Якщо черга порожня, зачекайте, поки елемент стане доступним.
• get_nowait() – Повернути елемент, якщо він одразу доступний, інакше підняти QueueEmpty.
• поставити (пункт) – Покладіть товар у чергу. Якщо черга заповнена, зачекайте, поки з’явиться вільне місце, перш ніж додавати елемент.
• put_nowait(елемент) – Помістіть елемент у чергу без блокування. Якщо вільного місця немає, підніміть QueueFull.
• qsize() – Повернути кількість елементів у черзі.

приклад: Цей код використовуєQueue>класу від стqueue>модуль. Він починається з порожньої черги та заповнює її ' а', «б» , і «c» . Після вилучення з черги черга стає порожньою та додається «1». Незважаючи на те, що раніше він був порожнім, він залишається заповненим, оскільки максимальний розмір встановлено на 3. Код демонструє операції з чергою, включаючи перевірку заповненості та порожнечі.

Python3

>

>

Вихід:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False>