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

Съдържание:

Anonim

Какво е Python Queue?

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

В този урок за Python ще научите:

  • Какво е Python Queue?
  • Как работи опашката на Python?
  • Видове опашка в Python
  • Инсталиране на опашка на Python
  • Налични методи в класа Queue и LifoQueue
  • Пример за първото излизане на опашката за първи изход
  • Пример за опашка „Последно влизане“
  • Добавете повече от 1 елемент в опашка
  • Опашка за сортиране
  • Реверсивна опашка

Как работи опашката на Python?

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

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

В Rear представлява точката, където са въведени елементите вътре в опашката. В този пример 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 (): връща true, ако опашката е пълна, иначе false.

Пример за първото излизане на опашката за първи изход

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

Добавяне и елемент в опашка

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

За да добавите елемент, можете да използвате метода 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

Резюме:

  • Опашката е контейнер, който съдържа данни. Има два вида Queue, FIFO и LIFO.
  • За FIFO (First in First out Queue) елементът, който отиде първи, ще бъде първият, който ще излезе.
  • За LIFO (Last in First out Queue) елементът, който е въведен последен, ще излезе първият.
  • Елемент в опашката се добавя по метода put (item).
  • За да премахнете елемент, се използва метод get ().