Python Опашка: FIFO, LIFO Пример

Какво е Python Опашка?

Опашката е контейнер, който съдържа данни. Данните, които са въведени първи, ще бъдат премахнати първи и следователно опашката се нарича още „Първи влезли първи“ (FIFO). Опашката има два края отпред и отзад. Артикулите се влизат отзад и се изваждат от предната страна.

Как действа Python Работа на опашка?

Опашката може лесно да се сравни с примера от реалния свят, опашката от хора, чакащи на опашка на гишето за билети, лицето, което стои първо, ще получи билета първо, последвано от следващия човек и т.н. Същата логика важи и за структурата на данните на опашката.

Ето схематично представяне на опашка:

- Заден представлява точката, в която елементите се вмъкват в опашката. В този пример 7 е стойност за това.

- преден представлява точката, където елементите от опашката ще бъдат премахнати. Ако премахнете елемент от опашката, първият елемент, който ще получите, е 1, както е показано на фигурата.

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

В опашката елементите се премахват по ред и не могат да се премахват между тях. Просто не можете да премахнете елемент 5 произволно от опашката, за да направите това, ще трябва да премахнете всички елементи преди 5. Елементите в опашката ще бъдат премахнати в реда, в който са вмъкнати.

Видове опашка в Python

Има основно два вида опашка Python:

• First in First out Queue: За това елементът, който отива първи, ще бъде първият, който излиза. За да работите с FIFO, трябва да извикате опашка() клас от модула за опашка.
• Last in First out Queue: Тук елементът, който е въведен последен, ще бъде първият, който ще излезе. За да работите с 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:

• постави (елемент): Това ще постави елемента в опашката.
• получи(): Това ще ви върне елемент от опашката.
• празен(): Ще върне 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

Премахване на елемент от FIFOqueue

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

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

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 опашка

За да обърнете опашката, можете да използвате друга опашка и рекурсия.

Следващият пример показва как да върнете опашката.

Пример:

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

Въпроси и Отговори