队列
队列抽象数据类型由下面的结构和操作定义。如前所述,队列是元素的有序集合,添加操作
发生在其尾部,移除操作则发生在头部。队列的操作顺序是 FIFO,它支持以下操作。
Queue()创建一个空队列。它不需要参数,且会返回一个空队列。
enqueue(item)在队列的尾部添加一个元素。它需要一个元素作为参数,不返回任何值。
dequeue()从队列的头部移除一个元素。它不需要参数,且会返回一个元素,并修改队
列的内容。
isEmpty()检查队列是否为空。它不需要参数,且会返回一个布尔值。
size()返回队列中元素的数目。它不需要参数,且会返回一个整数。
假设 q 是一个新创建的空队列。表 3-5 展示了对 q 进行一系列操作的结果。在“队列内容”一
列中,队列的头部位于右端。4 是第一个被添加到队列中的元素,因此它也是第一个被移除的元素。
q.isEmpty() [] True
q.enqueue(4) [4]
q.enqueue('dog') ['dog', 4]
q.enqueue(True) [True, 'dog', 4]
q.size() [True, 'dog', 4] 3
q.isEmpty() [True, 'dog', 4] False
q.enqueue(8.4) [8.4, True, 'dog', 4]
q.dequeue() [8.4, True, 'dog'] 4
q.dequeue() [8.4, True] 'dog'
q.size() [8.4, True] 2
用 Python 实现队列
创建一个新类来实现队列抽象数据类型是十分合理的。像之前一样,我们利用简洁强大的列
表来实现队列。
需要确定列表的哪一端是队列的尾部,哪一端是头部。代码清单 3-9 中的实现假设队列的尾
部在列表的位置 0 处。如此一来,便可以使用 insert 函数向队列的尾部添加新元素。pop 则可
用于移除队列头部的元素(列表中的最后一个元素)。这意味着添加操作的时间复杂度是O n( ) ,
移除操作则是O(1) 。
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return 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)
双端队列抽象数据类型
双端队列抽象数据类型由下面的结构和操作定义。如前所述,双端队列是元素的有序集合,
其任何一端都允许添加或移除元素。双端队列支持以下操作。
Deque()创建一个空的双端队列。它不需要参数,且会返回一个空的双端队列。
addFront(item)将一个元素添加到双端队列的前端。它接受一个元素作为参数,没有
返回值。
addRear(item)将一个元素添加到双端队列的后端。它接受一个元素作为参数,没有返
回值。
removeFront()从双端队列的前端移除一个元素。它不需要参数,且会返回一个元素,
并修改双端队列的内容。
removeRear()从双端队列的后端移除一个元素。它不需要参数,且会返回一个元素,
并修改双端队列的内容。
isEmpty()检查双端队列是否为空。它不需要参数,且会返回一个布尔值。
size()返回双端队列中元素的数目。它不需要参数,且会返回一个整数。
假设 d 是一个新创建的空双端队列,表 3-6 展示了对 d 进行一系列操作的结果。注意,前端
在列表的右端。记住前端和后端的位置可以防止混淆。
d.isEmpty() [] True
d.addRear(4) [4]
d.addRear('dog') ['dog', 4]
d.addFront('cat') ['dog', 4, 'cat']
d.addFront(True) ['dog', 4, 'cat', True]
d.size() ['dog', 4, 'cat', True] 4
d.isEmpty() ['dog', 4, 'cat', True] False
d.addRear(8.4) [8.4, 'dog', 4, 'cat', True]
d.removeRear() ['dog', 4, 'cat', True] 8.4
d.removeFront() ['dog', 4, 'cat'] True
用 Python 实现双端队列
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0, item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/76920.html