迹忆客 专注技术分享

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

Python 中的队列实现

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

队列中的第一个元素称为前端元素。 同样，队列的最后一个元素称为后元素。

例如，将以下数字序列视为队列。 1 是前部元件，6 是后部元件。

1,2,3,4,5,6

向队列添加元素：入队操作

在入队操作中，我们将元素添加到队列中，就像一个人在售票柜台加入队列一样。 新添加的元素始终成为后面的元素。

例如，如果我们将数字 7 添加到上面给出的队列中，队列将如下所示。

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

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

从队列中删除元素：出队操作

在出队操作中，我们删除队列的前面元素，就像一个人从售票柜台收到票后离开队列一样。

出队操作后，前面的元素会从队列中移除，前面元素后面的元素将成为新的前面元素。 例如，在出队操作之后，上一个示例中使用的队列将如下所示。

2,3,4,5,6,7

您只能在出队操作中删除前面的元素。 队列始终遵循先进先出的顺序。 因此，首先添加到队列中的元素也会首先被删除。

Python 中队列的其他操作

如果队列没有元素，则称其为空。 在不同的实现中，我们可以使用不同的方法来确定队列是否为空。

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

在Python中使用列表实现队列

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

1. 我们定义一个具有三个属性的类 Queue。
2. 我们定义一个空列表数据来存储列表的元素。
3. 我们初始化两个变量，front和rear。
4. 我们将变量初始化为-1 以表明队列为空。

代码：

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

创建队列对象时，会创建一个空列表并将其分配给属性数据。 然后列表存储队列的元素。

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

在Python中检查队列是否为空

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

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

代码：

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

在Python中使用列表进行入队操作

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

1. 如果队列为空，我们将使用 append() 方法将一个元素追加到数据属性中包含的列表中。 当在列表上调用时，append() 方法将一个元素作为其输入参数并将其添加到列表中。
2. 现在列表中只有一个元素，我们将把属性 front 和 back 的值更新为 0。 front 和 after 元素都出现在列表数据中的索引 0 处。
3. 如果列表不为空，我们将首先使用 append() 方法将元素添加到列表中。
4. 之后，我们将增加后属性中的值，表明队列中已添加了额外的元素。

在入队操作中，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 中使用列表进行出队操作

我们将首先检查队列是否为空以进行出队操作。 如果是，我们无法运营； 否则，我们将执行以下操作。

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

代码：

    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 中查找队列的长度，我们可以执行以下步骤。

1. 如果队列为空，则队列的长度将为0。因此，我们首先使用 isEmpty() 方法检查队列是否为空。
2. 如果 isEmpty() 方法返回 True，我们将返回 0 作为队列长度。
3. 否则，列表的长度将计算为后-前+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 和 back 属性。

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

由于队列为空，因此 front 和 after 属性将被初始化为 None。

代码：

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

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

在Python中检查队列是否为空

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

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

代码：

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

Python中使用链表进行入队操作

要执行入队操作，我们首先检查队列是否为空。 如果是，我们会将带有新元素的节点分配给 front 和 after 属性。

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

这样，新的元素就会被添加到队列中。

代码：

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

Python中使用链表进行出队操作

我们将首先检查队列是否为空以进行出队操作。 如果是，我们会说发生了下溢，并且我们无法删除任何元素。

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

之后，我们将前节点的下一个节点作为新的前节点。 然后，我们将使用 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中查找队列的长度

1. 为了找到队列的长度，我们首先将变量 count 初始化为 0。
2. 之后，我们将使用 while 循环从前端节点开始遍历队列。 当移动到下一个节点时，我们会将计数加 1。
3. 一旦到达队列末尾，即 None，我们将从 while 循环中退出。
4. 最后，我们将返回 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 中的 Collections 模块实现队列

我们还可以使用Python中的collections模块来实现队列。

Collections模块提供了deque（双端队列）类来实现Python中的队列和堆栈。 您可以使用下面的 import 语句在程序中导入 deque 类。

from collections import deque

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

代码：

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

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

在Python中检查队列的长度

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

len() 函数将以双端队列对象作为输入并返回双端队列长度。 我们将返回 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 对象中。

代码：

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

Python中的出队操作

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

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

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

代码：

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

现在我们已经使用collections模块在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.

Python 中最高效的队列实现

本文讨论了 Python 中队列实现的三种方法。

在这里讨论的所有方法中，使用列表来存储队列元素是最糟糕的。 在这种方法中，元素永远不会从列表中删除。

因此，我们建议您永远不要在您的程序中使用它。 仅当您是 Python 初学者并且对链表一无所知时才使用它。

如果不允许使用外部模块，则可以使用使用链表的 Python 队列实现，因为它节省时间和内存。 然而，它比使用双端队列的方法慢。

我们应该使用 deque 模块方法来实现 Python 最高效的队列实现。 它在时间和内存方面具有最好的效率，因为该模块的源代码是用C编写的，并且实现使用双端链表来实现双端队列对象。

我们希望本文能帮助您了解 Python 中的队列实现。 请继续关注更多信息丰富的文章。