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

Автор: Логан Янг Логан Янг
Hours обновлено

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

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

Python Очередь работает?

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

Вот схематическое представление очереди:

Python Работа в очереди

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

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

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

Python Работа в очереди

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

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

В основном существует два типа очередей. Python:

  • Очередь «Первый пришел — первый вышел». При этом элемент, который идет первым, будет выходить первым. Для работы с FIFO необходимо вызвать Очередь() класс из модуля очереди.
  • Очередь последним в первом выходе: здесь элемент, введенный последним, выйдет первым. Чтобы работать с LIFO, вам нужно вызвать ЛифоОчередь() класс из модуля очереди.

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

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

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

import queue

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

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

import queue
q1 = queue.Queue()

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

import queue
q1 = queue.LifoQueue()

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

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

  • положить (пункт): Это поместит элемент в очередь.
  • получать(): Это вернет вам элемент из очереди.
  • пустой(): Он вернет true, если очередь пуста, и false, если элементы присутствуют.
  • qразмер(): возвращает размер очереди.
  • полный(): возвращает true, если очередь заполнена, в противном случае — false.

СТАТЬИ ПО ТЕМЕ

Пример очереди «первым пришел — первым обслужен»

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

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

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

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

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

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

import queue
q1 = 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 queue
q1 = 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 queue
q1 = queue.LifoQueue()
q1.put(10)

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

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

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

import queue
q1 = 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 и LIFO. Теперь мы увидим, как добавить более одного элемента, а также удалить его.

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

import queue
q1 = queue.Queue()

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

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

import queue
q1 = queue.Queue()

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

while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Вывод:

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

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

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

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

import queue
q1 = queue.LifoQueue()

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


while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Вывод:

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

Сортировка очереди

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

import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

#using bubble sort on the queue
n =  q1.qsize()
for i in range(n):
    x = q1.get() # the element is removed
    for j in range(n-1):
        y = q1.get() # the element is removed
        if x > y :  
            q1.put(y)   #the smaller one is put at the start of the queue
        else:
            q1.put(x)  # the smaller one is put at the start of the queue
            x = y     # the greater one is replaced with x and compared again with nextelement
    q1.put(x)

while (q1.empty() == False): 
print(q1.queue[0], end = " ")  
        q1.get()

Вывод:

3 4 5 10 11 21

Revпросматривая очередь

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

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

Пример:

import queue
q1 = 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 recursion
    q2dest.put(buffer)
return q2dest

q2dest = 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().