Menu Close

Python队列:FIFO,LIFO

什么是Python队列?

队列是保存数据的容器。首先输入的数据将被首先删除,因此队列也称为“先进先出”(FIFO)。队列有两个前端。这些项目是从背面输入的,并且是从正面移除的。

在此Python教程中,您将学习:

  • 什么是Python队列?
  • Python队列如何工作?
  • Python中的队列类型
  • Python队列安装
  • Queue和LifoQueue类中可用的方法
  • 先进先出队列示例
  • 后进先出队列示例
  • 在队列中添加多个项目
  • 排序队列
  • 反转队列

Python队列如何工作?

可以将队列与现实世界中的示例进行轻松比较,例如排队的人在售票柜台排队,首先站着的人将首先获得车票,然后是下一个人,依此类推。队列数据结构也采用相同的逻辑。

这是队列的示意图:

%title插图%num

在后面表示其中的项被插入队列中的位置。在此示例中,7是该值。

前面表示其中从队列中的项目将被删除的点。如果从队列中删除一个项目,则您将获得的第一个元素为1,如图所示。

项目1是要插入队列中的第一个项目,而删除则是第一个出现在队列中的项目。因此,该队列称为FIRST IN FIRST OUT(FIFO)

%title插图%num

在队列中,项目是按顺序删除的,并且不能从两者之间删除。您只是不能从队列中随机删除项目5,为此,您将必须删除5之前的所有项目。队列中的项目将按照插入顺序删除。

Python中的队列类型

Python中主要有两种类型的队列:

  • 先进先出队列:为此,最先出现的元素将是第一个出现的元素。要使用FIFO,必须从队列模块调用Queue()类。
  • 后进先出队列:在这里,最后输入的元素将是第一个出现的元素。要使用LIFO,必须从队列模块中调用LifoQueue()类。

Python队列安装

在python中使用队列非常容易。以下是在代码中使用队列的步骤。

步骤1)您只需导入队列模块,如下所示:

import queue

该模块默认在python中可用,并且您不需要任何其他安装即可开始使用队列。队列FIFO有2种类型(先进先出)和LIFO(先进先出)。

步骤2)要使用FIFO队列,请使用导入的队列模块调用Queue类,如下所示:

import queue
q1 = queue.Queue()

步骤3)要使用LIFO队列,请调用LifoQueue()类,如下所示:

import queue
q1 = queue.LifoQueue()

Queue和LifoQueue类中可用的方法

以下是Queue和LifoQueue类中可用的重要方法:

  • put(item):这会将项目放入队列中。
  • get():这将从队列中返回一个项目。
  • empty():如果队列为空,则返回true;如果存在项目,则返回false。
  • qsize():返回队列的大小。
  • full():如果队列已满,则返回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.

Output:

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)

Output:

The item removed from the queue is  10

后进先出队列示例

对于后进先出队列,最后输入的元素将是第一个出现的元素。

要使用LIFO,即先进先出队列,我们​​需要导入队列模块并使用LifoQueue()方法。

在队列中添加和项

在这里,我们将了解如何向LIFO队列添加项目。

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

如上例所示,您必须在LifoQueue上使用put()方法。

从队列中删除项目

要从LIFOqueue中删除项目,可以使用get()方法。

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

item1 = q1.get()

print('The item removed from the LIFO queue is ', item1)

Output:

The item removed from the LIFO queue is  10

在队列中添加多个项目

在上面的示例中,我们已经看到了如何添加单个项并为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(9):
    q1.put(i) 

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

Output:

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

在LIFOqueue中添加项

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

从LIFOqueue中移除项

import queue
q1 = queue.LifoQueue()

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


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

Output:

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

排序队列

以下示例显示了队列排序。用于排序的算法是冒泡排序。

导入队列
q1 = queue.Queue()
#将项目添加到队列
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)
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)

#使用冒泡排序
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()

Output:

3 4 5 10 11 21

反转队列

要反转队列,可以使用另一个队列和递归。

以下示例显示如何使队列反向。

Example:

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()

Output:

10 3 21 4 5 11

概括:

  • 队列是保存数据的容器。队列有两种类型,即FIFO和LIFO。
  • 对于FIFO(先进先出队列),最先出现的元素将是第一个出现的元素。
  • 对于LIFO(后进先出队列),最后输入的元素将是第一个出现的元素。
  • 使用put(item)方法添加队列中的项目。
  • 要删除项目,请使用get()方法。
Posted in Python

发表评论

相关链接