Python中的队列实现

Python 3月前 4

我们在 Python 中使用队列来执行先进先出（FIFO）操作。本文将讨论在 Python 中实现队列的三种不同方式。

Python 中的队列实现

在一个队列中，我们可以执行不同的操作。让我们首先讨论所有操作背后的一般概念，然后，我们将使用各种构造来实现队列操作。

队列中的第一个元素被称为前置元素。同样地，队列中的最后一个元素被称为后方元素。

例如，把下面的数字序列看作是一个队列。1 是前面的元素，而6 是后面的元素。

1,2,3,4,5,6

向队列中添加一个元素：Enqueue操作

在enqueue操作中，我们将元素添加到队列中，就像一个人在售票处加入一个队列一样。新添加的元素总是成为后面的元素。

例如，如果我们把数字7 添加到上面给出的队列中，队列将看起来像下面这样。

1,2,3,4,5,6,7

需要注意的是，我们只能在队列的后面添加元素。

从队列中删除一个元素：去排队操作

在dequeue操作中，我们移除队列中最前面的元素，就像一个人从售票处拿到票后从队列中出来。

在脱队操作之后，前面的元素被从队列中移除，前面元素后面的元素成为新的前面元素。例如，在去排队操作后，前面例子中使用的队列将看起来像这样。

2,3,4,5,6,7

你只能在dequeue操作中删除前面的元素。队列总是遵循先入先出的顺序。因此，首先添加到队列中的元素也会首先被删除。

Python 中对队列的其它操作

如果一个队列没有任何元素，它就被称为空队列。在不同的实现中，我们可以使用不同的方法来确定一个队列是否为空。

有时，我们可能还需要找到队列的长度。我们还将讨论这个操作的实现。

在 Python 中使用列表实现队列

我们可以在 Python 中使用列表最简单地实现队列。要使用列表创建一个队列、

我们定义一个具有三个属性的类Queue 。
我们定义一个空列表data ，它将存储列表中的元素。
我们初始化两个变量，front 和rear 。
我们将这些变量初始化为-1 ，以表明队列是空的。

代码：

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

当创建一个Queue 对象时，一个空的列表被创建并分配给属性data 。然后该列表存储了队列的元素。

创建空队列后，我们将对队列实现不同的操作。

在 Python 中检查队列是否为空

为了检查队列是否为空，我们可以检查属性，前面和后面，是否初始化为-1 。为此，我们将定义一个方法isEmpty() 。

isEmpty() 方法，当在队列上被调用时，将检查前面和后面的属性是否有值-1 。如果有，它将返回True ，表示队列是空的；否则，它将返回False 。

代码：

    def isEmpty(self):
        if self.rear == -1 and self.front == -1:
            return True
        else:
            return False

Python中使用列表的Enqueue操作

要向队列中插入一个元素，我们首先要检查队列是否为空。我们可以使用上面定义的isEmpty() 方法。

如果队列是空的，我们将使用append() 方法将一个元素追加到data 属性包含的列表中。当在一个列表上调用时，append() 方法将一个元素作为其输入参数并将其添加到列表中。
现在列表中只有一个元素，我们将把属性front 和rear 的值更新为0 。front 和rear 元素都存在于列表0 的索引中data 。
如果列表不是空的，我们将首先使用append() 方法将该元素添加到列表中。
之后，我们将增加rear 属性中的值，显示一个额外的元素已经被添加到队列中。

在enqueue操作中，front 属性的值不会被改变，因为我们不会从队列中删除任何元素。

整个操作可以用Python实现，如下所示。

代码：

    def enQueue(self, element):
        if self.isEmpty():
            self.data.append(element)
            self.front = 0
            self.rear = 0
        else:
            self.data.append(element)
            self.rear += 1

在Python中使用列表的去排队操作

我们将首先检查队列是否是空的，以便进行脱队操作。如果是，我们就不能操作；否则，我们将执行以下操作。

我们将检查队列中是否只有一个元素。我们可以检查front 和rear 属性是否有相同的值，并且没有一个是-1 。
如果队列中只有一个元素，我们将使用pop() 方法删除队列中front 索引处的元素，并将其返回给用户。然后，我们将把属性front 和rear 更新为-1 ，表明队列已经变空。
如果上述条件中没有一个是True ，则队列中有两个或更多的元素。在这种情况下，我们将在一个临时变量中存储front 索引的元素。
之后，我们将增加属性front 中的值，表示列表中的下一个元素已经成为front 元素。
最后，我们将返回存储在临时变量中的值。

代码：

    def deQueue(self):
        if self.isEmpty():
            print("Queue is Empty. Cannot remove element")
        elif self.front == self.rear and self.front != -1:
            element = self.data[self.front]
            self.front = -1
            self.rear = -1
            return element
        else:
            element = self.data[self.front]
            self.front = self.front + 1
            return element

在 Python 中查找队列的长度

要在Python中找到队列的长度，我们可以执行以下步骤。

如果队列是空的，队列的长度将是0。因此，我们将首先使用isEmpty() 方法检查队列是否为空。
如果isEmpty() 方法返回True ，我们将返回0 作为队列长度。
否则，列表的长度将被计算为rear-front+1 。

如下所示，我们在length() 方法中实现了这一点。

代码：

    def length(self):
        if self.isEmpty():
            return 0
        return self.rear - self.front + 1

我们已经实现了所有的方法。现在让我们执行一次所有的操作。

完整的代码：

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1
    def isEmpty(self):
        if self.rear == -1 and self.front == -1:
            return True
        else:
            return False
    def enQueue(self, element):
        if self.isEmpty():
            self.data.append(element)
            self.front = 0
            self.rear = 0
        else:
            self.data.append(element)
            self.rear += 1
    def deQueue(self):
        if self.isEmpty():
            print("Queue is Empty. Cannot remove element")
        elif self.front == self.rear and self.front != -1:
            element = self.data[self.front]
            self.front = -1
            self.rear = -1
            return element
        else:
            element = self.data[self.front]
            self.front = self.front + 1
            return element
    def length(self):
        return self.rear - self.front + 1
myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

输出：

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is Empty. Cannot remove element

在这个例子中，我们在Python中使用列表实现队列后执行了一些方法。你可以复制代码，将其粘贴到你的IDE中，并对代码进行实验以更好地理解代码的工作原理。

在Python中使用链接列表实现队列

我们已经讨论了Python中对链表的不同操作。我们也可以使用链接列表的操作来实现Python中的队列。

我们将首先定义一个有两个属性的节点，即data 和next 。

代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

其中：

data 属性将被用来存储队列的元素。
next 属性将被用来指向队列中当前元素前面的元素。

在定义了Node 之后，我们将定义Queue 类，其中我们将有front 和rear 属性。

front 属性将指向队列的链接列表中包含front 元素的节点。同样地，rear 属性将指向包含队列的链接列表中包含rear 元素的节点。

front 和rear 属性将被初始化为None ，因为队列将是空的。

代码：

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

当Queue 类被初始化时，它只包含front 和rear 属性，其值为None 。

在 Python 中检查队列是否为空

为了检查队列是否为空，我们可以检查front 和rear 属性是否为None 。如果是，我们就可以说队列是空的。

我们将为这个操作定义isEmpty() 方法。当在一个队列上调用时，如果队列是空的，isEmpty() 方法将返回True ；否则，它将返回False 。

代码：

    def isEmpty(self):
        if self.front is None:
            return True
        return False

在Python中使用关联列表的Enqueue操作

为了执行enqueue操作，我们将首先检查队列是否为空。如果是，我们将把带有新元素的节点分配给front 和rear 两个属性。

否则，我们将把新元素添加到rear 节点的下一个节点。之后，我们将使新节点成为rear 节点。

通过这种方式，新元素将被添加到队列中。

代码：

    def enQueue(self, data):
        newNode = Node(data)
        if self.isEmpty():
            self.front = newNode
            self.rear = newNode
        else:
            self.rear.next = newNode

在Python中使用关联列表的去排队操作

我们将首先检查队列是否是空的，以便进行脱队操作。如果是，我们会说发生了下溢，我们不能删除任何元素。

否则，我们将首先把数据存储在front 节点的一个临时变量中。

之后，我们将把front 节点的next 节点作为新的front 节点。然后，我们将使用del 语句删除存储在临时变量中的前置节点。

这样一来，之前的前置节点将从队列中删除。最后，我们将返回存储在临时节点中的值。

代码：

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            element = self.front
            nextFront = self.front.next
            self.front = nextFront
            value = element.data
            del element
            return value

在Python中查找队列的长度

为了找到队列的长度，我们将首先初始化一个变量count为0 。
之后，我们将使用一个while 循环从front 节点开始遍历队列。当移动到下一个节点时，我们将用1 来增加count 。
一旦我们到达队列的终点，即None ，我们将从while 循环中退出。
最后，我们将返回count 的值，显示队列的长度。

代码：

    def length(self):
        count = 0
        if self.front is None:
            return count
        else:
            temp = self.front
            while temp is not None:
                count += 1
                temp = temp.next
            return count

我们已经用链表实现了所有的队列方法。现在让我们执行这些操作，以更好地理解其工作。

完整的代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Queue:
    def __init__(self):
        self.front = None
        self.rear = None
    def isEmpty(self):
        if self.front is None:
            return True
        return False
    def enQueue(self, data):
        newNode = Node(data)
        if self.isEmpty():
            self.front = newNode
            self.rear = newNode
        else:
            self.rear.next = newNode
    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            element = self.front
            nextFront = self.front.next
            self.front = nextFront
            value = element.data
            del element
            return value
    def length(self):
        count = 0
        if self.front is None:
            return count
        else:
            temp = self.front
            while temp is not None:
                count += 1
                temp = temp.next
            return count
myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

输出：

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

使用Python中的集合模块实现队列

我们也可以使用 Python 中的集合模块来实现队列。

集合模块提供了deque (doublely ended queue) 类来实现 Python 中的队列和栈。你可以在你的程序中使用下面的import 语句导入deque 类。

from collections import deque

我们将创建一个类，Queue ，来实现队列。如下所示，我们将在该类中创建一个deque 对象。

代码：

class Queue:
    def __init__(self):
        self.data = deque()

当Queue 类被实例化时，会创建一个空的deque 对象来存储队列的元素。

在Python中检查队列的长度

为了检查队列的长度，我们将定义一个length() 方法。在length() 方法中，我们将使用len() 函数计算deque 对象的长度。

len() 函数将把deque 对象作为输入，并返回deque 长度。我们将返回len() 函数的值作为队列的长度，如下所示。

代码：

    def length(self):
        return len(self.data)

在Python中检查队列是否是空的

如果队列的长度是0 ，我们将说队列是空的。我们可以定义isEmpty() 方法，如下图所示。

代码：

    def isEmpty(self):
        if self.length() == 0:
            return True
        return False

在Python中对一个元素进行排队

我们将定义enQueue() 方法来排队获取一个元素。enQueue() 方法将接受新的元素作为其输入参数。

在enQueue() 方法中，我们将使用append() 方法将该元素添加到deque 对象中。append() 方法，当在deque 对象上调用时，将新元素作为其输入参数，并将其添加到deque 对象中。

代码：

    def enQueue(self, x):
        self.data.append(x)

Python中的排队操作

我们将定义deQueue() 方法来从队列中删除一个元素。在deQueue() 方法里面，我们将在队列的deque 对象上调用popleft() 方法。

popleft() 方法，当在deque 对象上被调用时，将删除 deque 的前面元素。它还会返回从队列中移除的元素。

我们还将使用return 语句从deQueue() 方法返回由popleft() 方法返回的值。

代码：

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            return self.data.popleft()

现在我们已经使用集合模块在Python中实现了队列的所有方法。让我们观察一下整个执行过程。

完整的代码：

from collections import deque
class Queue:
    def __init__(self):
        self.data = deque()
    def length(self):
        return len(self.data)
    def isEmpty(self):
        if self.length() == 0:
            return True
        return False
    def enQueue(self, x):
        self.data.append(x)
    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            return self.data.popleft()
myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

输出：

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.