3.12. 用Python实现队列¶
3.12. Implementing a Queue in Python
为抽象数据类型队列实现创建一个新的类是合适的。如之前所述，我们将利用列表集合的强大和简单来构建队列的内部表示。
我们需要决定列表的哪一端作为尾部，哪一端作为前端。在 Listing 1 中的实现假设尾部在列表的第 0 个位置。这允许我们使用列表的 insert 函数将新元素添加到队列的尾部。pop 操作可以用来移除前端元素（即列表的最后一个元素）。请记住，这也意味着 enqueue 的时间复杂度是 \(O(n)\)，而 dequeue 的时间复杂度是 \(O(1)\)。
class Queue:
"""使用列表实现的队列"""
def __init__(self):
"""创建新的队列"""
self._items = []
def is_empty(self):
"""检查队列是否为空"""
return not bool(self._items)
def enqueue(self, item):
"""将一个项添加到队列中"""
self._items.insert(0, item)
def dequeue(self):
"""从队列中移除一个项"""
return self._items.pop()
def size(self):
"""获取队列中项的数量"""
return len(self._items)
CodeLens 1 显示了 Queue 类的实际操作，展示了 Table 1 中操作序列的效果。
class Queue:
"""使用列表实现的队列"""
def __init__(self):
"""创建新的队列"""
self._items = []
def is_empty(self):
"""检查队列是否为空"""
return not bool(self._items)
def enqueue(self, item):
"""将一个项添加到队列中"""
self._items.insert(0, item)
def dequeue(self):
"""从队列中移除一个项"""
return self._items.pop()
def size(self):
"""获取队列中项的数量"""
return len(self._items)
q = Queue()
q.enqueue(4)
q.enqueue("dog")
q.enqueue(True)
print(q.size())
进一步操作该队列将得到以下结果：
>>> q.size()
3
>>> q.is_empty()
False
>>> q.enqueue(8.4)
>>> q.dequeue()
4
>>> q.dequeue()
'dog'
>>> q.size()
2
自检
假设你有以下一系列队列操作。
q = Queue()
q.enqueue("hello")
q.enqueue("dog")
q.enqueue(3)
q.dequeue()
队列中剩下哪些项？
- 答案 a: 'hello', 'dog'
- 答案 b: 'dog', 3
- 答案 c: 'hello', 3
- 答案 d: 'hello', 'dog', 3
正确答案: b
- 反馈 a: 记住，队列中第一个添加的项是第一个移除的。先进先出（FIFO）。
- 反馈 b: 是的，先进先出意味着 "hello" 已经被移除。
- 反馈 c: 队列和栈都是只能访问第一个和最后一个项的数据结构。
- 反馈 d: 哦，可能你错过了最后的
dequeue调用？
It is again appropriate to create a new class for the implementation of the abstract data type queue. As before, we will use the power and simplicity of the list collection to build the internal representation of the queue.
We need to decide which end of the list to use as the rear and which to use as the front. The implementation shown in Listing 1 assumes that the rear is at position 0 in the list. This allows us to use the insert function on lists to add new elements to the rear of the queue. The pop operation can be used to remove the front element (the last element of the list). Recall that this also means that enqueue will be \(O(n)\) and dequeue will be \(O(1)\).
class Queue:
"""Queue implementation as a list"""
def __init__(self):
"""Create new queue"""
self._items = []
def is_empty(self):
"""Check if the queue is empty"""
return not bool(self._items)
def enqueue(self, item):
"""Add an item to the queue"""
self._items.insert(0, item)
def dequeue(self):
"""Remove an item from the queue"""
return self._items.pop()
def size(self):
"""Get the number of items in the queue"""
return len(self._items)
CodeLens 1 shows the Queue class in action as we perform the sequence of operations from Table 1.
class Queue:
"""Queue implementation as a list"""
def __init__(self):
"""Create new queue"""
self._items = []
def is_empty(self):
"""Check if the queue is empty"""
return not bool(self._items)
def enqueue(self, item):
"""Add an item to the queue"""
self._items.insert(0, item)
def dequeue(self):
"""Remove an item from the queue"""
return self._items.pop()
def size(self):
"""Get the number of items in the queue"""
return len(self._items)
q = Queue()
q.enqueue(4)
q.enqueue("dog")
q.enqueue(True)
print(q.size())
Further manipulation of this queue would give the following results:
>>> q.size()
3
>>> q.is_empty()
False
>>> q.enqueue(8.4)
>>> q.dequeue()
4
>>> q.dequeue()
'dog'
>>> q.size()
2
Self Check
Suppose you have the following series of queue operations.
q = Queue()
q.enqueue("hello")
q.enqueue("dog")
q.enqueue(3)
q.dequeue()
What items are left on the queue?
- answer a: 'hello', 'dog'
- answer b: 'dog', 3
- answer c: 'hello', 3
- answer d: 'hello', 'dog', 3
correct: b
- feedback a: Remember the first thing added to the queue is the first thing removed. FIFO
- feedback b: Yes, first in first out means that hello is gone
- feedback c: Queues, and Stacks are both data structures where you can only access the first and the last thing.
- feedback d: Ooops, maybe you missed the dequeue call at the end?
创建日期: 2024年9月9日