Python Черга: FIFO, LIFO Приклад
Логан Янг
Що таке Python Черга?
Черга — це контейнер, у якому зберігаються дані. Дані, які вводяться першими, будуть видалені першими, тому чергу також називають «Першим прийшов, першим вийшов» (FIFO). Черга має два кінці: передній і задній. Предмети вводяться ззаду і виймаються з лицьового боку.
Як Python Робота в черзі?
Чергу можна легко порівняти з прикладом реального світу: черга людей, які чекають у черзі біля каси, людина, яка стоїть першою, отримає квиток першою, за нею наступна особа і так далі. Така ж логіка стосується і структури даних черги.
Ось схематичне зображення черги:
Команда Задній представляє точку, де елементи вставляються всередину черги. У цьому прикладі значенням є 7.
Команда передній представляє точку, де елементи з черги будуть видалені. Якщо ви видалите елемент із черги, перший елемент, який ви отримаєте, буде 1, як показано на малюнку.
Елемент 1 був першим, який було вставлено в чергу, а під час видалення він вийшов першим. Тому черга називається FIRST IN FIRST OUT (FIFO).
У черзі елементи видаляються за порядком і не можуть бути видалені між ними. Ви просто не можете випадковим чином видалити елемент 5 із черги, для цього вам доведеться видалити всі елементи до 5. Елементи в черзі буде видалено в тому порядку, в якому вони були вставлені.
Види черги в Python
В основному існує два типи черги Python:
- Перший у черзі «Перший вийшов»: для цього елемент, який йде першим, буде першим виходити. Щоб працювати з FIFO, вам потрібно викликати Черга() клас із модуля черги.
- Останній у черзі, першим вийшов: тут елемент, який введено останнім, буде першим, хто вийде. Щоб працювати з LIFO, вам потрібно викликати LifoQueue() клас із модуля черги.
Python установка черги
Працювати з чергою в Python дуже легко. Ось кроки, які слід виконати, щоб використовувати чергу у своєму коді.
Крок 1) Вам просто потрібно імпортувати модуль черги, як показано нижче:
import queue
Модуль доступний за замовчуванням з python, і вам не потрібно додатково встановлювати, щоб розпочати роботу з чергою. Існує 2 типи черги FIFO (перший прийшов, перший вийшов) і LIFO (останній прийшов, перший вийшов).
Крок 2) Щоб працювати з чергою FIFO, викличте клас Queue за допомогою імпортованого модуля черги, як показано нижче:
import queue q1 = queue.Queue()
Крок 3) Щоб працювати з чергою LIFO, викличте клас LifoQueue(), як показано нижче:
import queue q1 = queue.LifoQueue()
Методи, доступні в класі Queue і LifoQueue
Нижче наведено важливі методи, доступні в класі Queue і LifoQueue:
- put(item): Це помістить елемент у чергу.
- отримати(): Це поверне вам елемент із черги.
- порожній(): Він поверне true, якщо черга порожня, і false, якщо елементи присутні.
- qsize(): повертає розмір черги.
- повний(): повертає 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, як показано в прикладі вище.
Видалити елемент із черги
Щоб видалити елемент із черги LIFOqueue, ви можете скористатися методом 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 та LIFOqueue. Тепер ми побачимо, як додати більше одного елемента, а також видалити його.
Додати елемент у чергу 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
Reversing Queue
Щоб змінити чергу, ви можете скористатися іншою чергою та рекурсією.
У наступному прикладі показано, як повернути чергу.
приклад:
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 (First in First Out Queue) елемент, який йде першим, буде першим виходити.
- Для LIFO (Last in First Out Queue) елемент, який введено останнім, буде першим, хто вийде.
- Елемент у чергу додається за допомогою методу put(item).
- Щоб видалити елемент, використовується метод get().
