最专业的网站建设收费,广西壮锦网站建设策划书,芯片最新消息,做同城信息网站怎么赚钱5. 队列
队列#xff08;queue#xff09;是只允许在一端进行插入操作#xff0c;而在另一端进行删除操作的线性表。
队列是一种先进先出的#xff08;First In First Out#xff09;的线性表#xff0c;简称 FIFO。允许插入的一端为队尾#xff0c;允许删除的一端为队…5. 队列
队列queue是只允许在一端进行插入操作而在另一端进行删除操作的线性表。
队列是一种先进先出的First In First Out的线性表简称 FIFO。允许插入的一端为队尾允许删除的一端为队头。队列不允许在中间部位进行操作假设队列是qa1a2……an那么a1就是队头元素而an是队尾元素。这样我们就可以删除时总是从a1开始而插入时总是在队列最后。这也比较符合我们通常生活中的习惯排在第一个的优先出列最后来的当然排在队伍最后。
与栈一样队列可以通过顺序表或链表来实现。
5.1 单向队列
单向队列就像排队一样先进先出其结构如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iwv6VZyb-1676469300275)(https://hubery624.oss-cn-shenzhen.aliyuncs.com/排队.jpeg)]
单向队列操作
enqueue(item) 往队列中添加一个item元素dequeue() 从队列头部删除一个元素is_empty() 判断一个队列是否为空size() 返回队列的大小
同样地这里也以 list 实现单向队列当然你也可以使用链表实现。
class Queue(object):创建一个空的队列def __init__(self):用顺序表实现队列Python 中 list 是顺序表队列先进先出以列表尾部为队头appendO(1)就要从列表头就是队列尾部pop(0)O(n)以列表头部为队头insert(0, item)O(n)就要从列表就尾是队列尾部pop()O(1)所有哪种方法都可以# 定义一个列表用来存储元素self.__list []def enqueue(self, item):往队列中添加一个item元素self.__list.append(item)def dequeue(self):从队列头部删除一个元素return self.__list.pop(0)def is_empty(self):判断栈是否为空若 self.__list 为空则为 False[] 也是 False两者为真返回 Truereturn self.__list []def size(self):返回栈的元素个数return len(self.__list)if __name__ __main__:q Queue()print(q.is_empty())q.enqueue(1)q.enqueue(2)q.enqueue(3)print(q.size())print(q.is_empty())print(q.dequeue())print(q.dequeue())print(q.dequeue())print(q.is_empty())如果用 list 实现单向队列不管是以 list 头部作为队头还是队尾最终的结果都是有一个 O(n) 还有个 O(1。
运行结果如下
# 先进先出
True
3
False
1
2
3
True5.2 双端队列
双端队列deque全名double-ended queue是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9PGhQNjW-1676469300275)(https://hubery624.oss-cn-shenzhen.aliyuncs.com/20200613105121.png)]
操作
add_front(item) 从队头加入一个item元素add_rear(item) 从队尾加入一个item元素remove_front() 从队头删除一个item元素remove_rear() 从队尾删除一个item元素is_empty() 判断双端队列是否为空size() 返回队列的大小
class Deque(object):创建一个空的双端队列def __init__(self):用顺序表实现栈Python 中 list 是顺序表栈先进先出以列表尾部为队头appendO(1)就要从列表头就是队列尾部pop(0)O(n)以列表头部为队头insert(0, item)O(n)就要从列表就尾是队列尾部pop()O(1)所有哪种方法都可以# 定义一个列表用来存储元素self.__list []def add_front(self, item):从队头加入一个item元素self.__list.insert(0, item) # O(n)# self.__list.append(item) # O(1)def add_rear(self, item):从队尾加入一个item元素self.__list.append(item) # O(1)# self.__list.insert(0, item) # O(n)def remove_front(self):从队头删除一个item元素return self.__list.pop(0) # O(n)# return self.__list.pop() # O(1)def remove_rear(self):从队尾删除一个item元素return self.__list.pop() # O(1)# return self.__list.pop(0) # O(n)def is_empty(self):判断栈是否为空若 self.__list 为空则为 False[] 也是 False两者为真返回 Truereturn self.__list []def size(self):返回栈的元素个数return len(self.__list)if __name__ __main__:q Deque()print(q.is_empty())q.add_front(1) # 1q.add_front(2) # 2 1q.add_rear(3) # 2 1 3print(q.size()) # 3print(q.is_empty()) # Falseprint(q.remove_front()) # 2print(q.remove_front()) # 1print(q.remove_rear()) # 3print(q.is_empty()) # True运行结果如下
True
3
False
2
1
3
True
