Очередь Python: пример FIFO, LIFO

Содержание:

Anonim

Что такое очередь Python?

Очередь - это контейнер, в котором хранятся данные. Данные, которые вводятся первыми, будут удалены первыми, поэтому очередь также называется «Первым пришел - первым ушел» (FIFO). Очередь имеет два конца спереди и сзади. Предметы вводятся сзади и удаляются с лицевой стороны.

В этом руководстве по Python вы узнаете:

  • Что такое очередь Python?
  • Как работает очередь Python?
  • Типы очередей в Python
  • Установка очереди Python
  • Методы, доступные внутри класса Queue и LifoQueue
  • Пример очереди "первым пришел - первым обслужен"
  • Пример очереди "последний вошел - первым ушел"
  • Добавить более 1 элемента в очередь
  • Очередь сортировки
  • Реверсивная очередь

Как работает очередь Python?

Очередь можно легко сравнить с реальным примером: очередь людей ждет в очереди у билетной кассы, первый человек получит билет, затем следующий человек и так далее. Та же логика применима и к структуре данных очереди.

Вот схематическое изображение очереди:

Задняя представляет собой точку , в которой элементы вставлены внутри очереди. В этом примере для этого стоит 7.

Фронт представляет собой точку , в которой будут удалены элементы из очереди. Если вы удалите элемент из очереди, первый элемент, который вы получите, будет равен 1, как показано на рисунке.

Элемент 1 был первым, который был вставлен в очередь, а при удалении он первым вышел. Следовательно, очередь называется FIRST IN FIRST OUT (FIFO).

В очереди элементы удаляются по порядку и не могут быть удалены между ними. Вы просто не можете случайно удалить элемент 5 из очереди, для этого вам придется удалить все элементы до 5. Элементы в очереди будут удалены в том порядке, в котором они были вставлены.

Типы очередей в Python

В Python есть в основном два типа очереди:

  • Очередь «первым пришел - первым обслужен»: для этого первым выйдет элемент, который идет первым.

    Для работы с FIFO необходимо вызвать класс Queue () из модуля очереди.

  • Последний в очереди, первый ушел: здесь элемент, который был введен последним, будет первым, который выйдет.

    Для работы с LIFO необходимо вызвать класс LifoQueue () из модуля очереди.

Установка очереди Python

Работать с очередью в python очень просто. Вот шаги, которые необходимо выполнить, чтобы использовать очередь в вашем коде.

Шаг 1) Вам просто нужно импортировать модуль очереди, как показано ниже:

import queue

Модуль по умолчанию доступен с python, и вам не нужна дополнительная установка, чтобы начать работу с очередью. Существует 2 типа очереди FIFO (первым пришел - первым ушел) и LIFO (последний пришел - первым ушел).

Шаг 2) Для работы с очередью FIFO вызовите класс Queue, используя импортированный модуль очереди, как показано ниже: 

import queueq1 = queue.Queue()

Шаг 3) Для работы с очередью LIFO вызовите класс LifoQueue (), как показано ниже: 

import queueq1 = queue.LifoQueue()

Методы, доступные внутри класса Queue и LifoQueue

Ниже приведены важные методы, доступные в классах Queue и LifoQueue:

  • put (item): это поместит элемент в очередь.
  • get (): это вернет вам элемент из очереди.
  • empty (): он вернет true, если очередь пуста, и false, если элементы присутствуют.
  • qsize (): возвращает размер очереди.
  • full (): возвращает истину, если очередь заполнена, в противном случае - ложь.

Пример очереди "первым пришел - первым обслужен"

В случае «первым пришел - первым ушел» первым выйдет элемент, который идет первым.

Добавить и поставить в очередь

Давайте поработаем на примере добавления элемента в очередь. Чтобы начать работу с очередью, сначала импортируйте очередь модулей, как показано в примере ниже.

Чтобы добавить элемент, вы можете использовать метод put (), как показано в примере:

import queueq1 = queue.Queue()q1.put(10) #this will additem 10 to the queue.

По умолчанию размер очереди бесконечен, и вы можете добавлять в нее любое количество элементов. Если вы хотите определить размер очереди, то же самое можно сделать следующим образом.

import queueq1 = queue.Queue(5) #The max size is 5.q1.put(1)q1.put(2)q1.put(3)q1.put(4)q1.put(5)print(q1.full()) # will return true.

Выход:

True

Теперь размер очереди 5, и она займет не более 5 элементов, а метод q1.full () вернет true. Добавление дополнительных элементов больше не приведет к выполнению кода.

Удалить элемент из очереди

Чтобы удалить элемент из очереди, вы можете использовать метод get (). Этот метод разрешает элементы из очереди при вызове.

В следующем примере показано, как удалить элемент из очереди.

import queueq1 = queue.Queue()q1.put(10)item1 = q1.get()print('The item removed from the queue is ', item1)

Выход:

The item removed from the queue is 10

Пример очереди "последний вошел - первым ушел"

В случае, если последний в очереди отправляется первым, элемент, который был введен последним, выйдет первым.

Чтобы работать с LIFO, то есть последним в очереди первым, нам нужно импортировать модуль очереди и использовать метод LifoQueue ().

Добавить и поставить в очередь

Здесь мы разберемся, как добавить элемент в очередь LIFO.

import queueq1 = queue.LifoQueue()q1.put(10)

Вы должны использовать метод put () для LifoQueue, как показано в приведенном выше примере.

Удалить элемент из очереди

Чтобы удалить элемент из LIFOqueue, вы можете использовать метод get ().

import queueq1 = queue.LifoQueue()q1.put(10)item1 = q1.get()print('The item removed from the LIFO queue is ', item1)

Выход:

The item removed from the LIFO queue is 10

Добавить более 1 элемента в очередь

В приведенных выше примерах мы видели, как добавить один элемент и удалить элемент для FIFO и LIFOqueue. Теперь посмотрим, как добавить более одного элемента, а также удалить его.

Добавить и поместить в FIFOqueue

import queueq1 = queue.Queue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queue

Удалить элемент из FIFOqueue

import queueq1 = queue.Queue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.

Выход:

The value is 0The value is 1The value is 2The value is 3The value is 4The value is 5The value is 6The value is 7The value is 8The value is 9The value is 10The value is 11The value is 12The value is 13The value is 14The value is 15The value is 16The value is 17The value is 18The value is 19

Добавить и элемент в LIFOqueue

import queueq1 = queue.LifoQueue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queue

Удалить элемент из LIFOqueue

import queueq1 = queue.LifoQueue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.

Выход:

The value is 19The value is 18The value is 17The value is 16The value is 15The value is 14The value is 13The value is 12The value is 11The value is 10The value is 9The value is 8The value is 7The value is 6The value is 5The value is 4The value is 3The value is 2The value is 1The value is 0

Очередь сортировки

В следующем примере показана сортировка очереди. Алгоритм сортировки - пузырьковая сортировка.

import queueq1 = queue.Queue()#Addingitems to the queueq1.put(11)q1.put(5)q1.put(4)q1.put(21)q1.put(3)q1.put(10)#using bubble sort on the queuen = q1.qsize()for i in range(n):x = q1.get() # the element is removedfor j in range(n-1):y = q1.get() # the element is removedif x> y :q1.put(y) #the smaller one is put at the start of the queueelse:q1.put(x) # the smaller one is put at the start of the queuex = y # the greater one is replaced with x and compared again with nextelementq1.put(x)while (q1.empty() == False):print(q1.queue[0], end = " ")q1.get()

Выход:

3 4 5 10 11 21

Реверсивная очередь

Чтобы перевернуть очередь, вы можете использовать другую очередь и рекурсию.

В следующем примере показано, как перевернуть очередь.

Пример:

import queueq1 = queue.Queue()q1.put(11)q1.put(5)q1.put(4)q1.put(21)q1.put(3)q1.put(10)def reverseQueue (q1src, q2dest) :buffer = q1src.get()if (q1src.empty() == False) :reverseQueue(q1src, q2dest) #using recursionq2dest.put(buffer)return q2destq2dest = queue.Queue()qReversed = reverseQueue(q1,q2dest)while (qReversed.empty() == False):print(qReversed.queue[0], end = " ")qReversed.get()

Выход:

10 3 21 4 5 11

Резюме:

  • Очередь - это контейнер, в котором хранятся данные. Существует два типа очереди: FIFO и LIFO.
  • Для FIFO (очереди «первым пришел - первым ушел») первым выйдет элемент, который идет первым.
  • Для LIFO (очереди «последним пришел - первым ушел») элемент, который был введен последним, будет первым, который выйдет.
  • Элемент в очередь добавляется с помощью метода put (item).
  • Для удаления элемента используется метод get ().