什么是队列？

队列是保存数据的容器。 首先输入的数据将被首先删除，因此队列也称为“先进先出”（FIFO）。 队列有两端，元素是从后面输入的，并且是从前面删除的。

队列如何工作？

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

这是队列的示意图：

后方rear表示将元素插入队列中的位置，前方front表示从队列中删除元素的点。 如果从队列中删除一个项目，则您将获得的第一个元素为item1。

item1是要插入队列中的第一个元素，而删除也是第一个插入的元素。 因此，队列称被为先进先出（FIFO）

在队列中，元素是按顺序删除的，并且不能从两者之间删除。 您不能从队列中随机删除item5，如果想删除item5，您将必须删除item5之前的所有item（指1,2,3,4）。队列中的元素将按照插入顺序删除。

Python中的队列类型

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

• 先进先出队列：最先出去的元素将是第一个进来的元素。要使用FIFO，您必须从队列模块调用Queue（）类。
• 后进先出队列：最后进来的元素将是第一个出去的元素。要使用LIFO，必须从队列模块中调用LifoQueue（）类。

Python队列安装

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

步骤1）导入队列模块

import queue

默认情况下，该模块可用于python，并且不需要任何其他安装即可开始使用队列。

步骤2）要使用FIFO队列，请使用导入的queue模块调用Queue类，如下所示：

import queue
q1 = queue.Queue()

步骤3）要使用LIFO队列，请调用LifoQueue（）类，如下所示：

import queue
q1 = 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) #最大为 5.
q1.put(1)
q1.put(2)
q1.put(3)
q1.put(4)
q1.put(5)
print(q1.full()) # 是否满，这里会返回true.

输出:

True

从队列中删除元素

要从队列中删除元素，可以使用get（）的方法。

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

item1 = q1.get()  #队列删除了一个元素，并且把这个元素赋值给变量 item1

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

输出:

The item removed from the queue is  10

后进先出队列示例

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

要使用LIFO，即后进先出队列，我们需要导入queue模块并使用LifoQueue（）方法。

在队列中添加元素

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

从队列中删除元素

要从LIFOqueue中删除元素，可以使用get（）方法。

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

item1 = q1.get() #队列删除了一个元素，并且把这个元素赋值给变量 item1

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

输出:

The item removed from the LIFO queue is  10

在队列中添加多个元素

在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():  #判断队列是否为空empty
		print("The value is ", q1.get()) # 获取元素，并送给print，获取元素后，队列中该元素就会被删除

输出:

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

从LIFOqueue中移除元素

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():#判断队列是否为空empty
		print("The value is ", q1.get()) # 获取元素，并送给print，获取元素后，队列中该元素就会被删除

Output:

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

反转队列

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

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

示例:

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