简说Python，号主老表，Python终身学习者，数据分析爱好者，从18年开始分享Python知识，原创文章227篇，写过Python、SQL、Excel入门文章，也写过Web开发、数据分析文章，老表还总结整理了一份2022Python学习资料和电子书资源，关注后私信回复：2022 即可领取。
今天给大家分享的书籍《Python程序员面试算法宝典》第二章第二小节：如何实现队列。
如果你是第一次看，也许，你可以看看本系列下面的文章：
Python数据结构：链表合集（12+7），复现几遍，包你学会
Smaller And Smarter Python数据结构：自己动手实现栈
今日问题
""" 目标：实现队列，使其具有方法：入队列（push_queue）、出队列（pop_queue）、 取队列首元素（get_top）、取队列尾元素（get_tail）、判断队列是否为空（is_empty）、 获取队列中元素个数（size） 为后面操作打基础 Goal: To implement the queue, there are methods: push queue, pop queue, get top, get tail, judge whether the queue is empty, and get the number of elements in the queue Lay a foundation for later operations """
解题
方法一：数组（列表）实现队列
""" Method One : 数组（列表）实现队列 核心思想：以数组（列表）作为存储队列数据的数据结构，Python里本身 对列表有着丰富的内置操作，比如pop,append,len等等，列表是顺序 存储，并且在Python初始化一个列表时，不一定非要指定列表长度，这 使得Python列表实现起来非常简单和方便。 注意：一般在C、Java中初始化数组(列表)时，是必须声明数组（列表） 长度的，而在Python中，可以不限定，但append添加的效率很明显要比 直接赋值（比如：list[1] = "Python"）的低很多。 问题：用数组实现队列最大的问题就是，当出队列时，front是只向后移的， 所以会浪费前面的空间，对于这个问题，我们可以把数组看成一个环状的空 间，我记得当时我学数据结构的时候是固定数组长度，然后取余来判断数组 队列是否溢出或者该循环了。 Method one: array (list) implementation queue Core idea: Taking array (list) as the data structure of queue data storage, python itself has rich built-in operations on list, such as pop, append, len, etc. list is sequential storage, and when Python initializes a list, it is not necessary to specify the length of list, which makes Python list implementation very simple and convenient. Note: when initializing arrays (lists) in C and Java, the length of arrays (lists) must be declared. In Python, there is no limit, but the efficiency of adding append is obviously lower than that of direct assignment (for example: list [1] = "Python"). Problem: the biggest problem of using array to realize queue is that when out of queue, front only moves backward, so it will waste the previous space. For this problem, we can regard array as a circular space. I remember that when I studied data structure, I fixed the length of array, and then took the remainder to judge whether the array queue overflowed or the cycle was over. """
代码
class ListQueue: def __init__(self): self.queue = [] self.front = 0 # 队列头 self.rear = 0 # 队列尾 # 新元素进入队列 def queue_push(self, x): self.queue.append(x) # 入队列 self.rear += 1 # 有新数据进队列，尾元素往后一个位置后移一位 print("********入队列成功********") # 删除队头元素 def queue_pop(self): if self.front < self.rear: self.front += 1 # 出队列，把队首元素记录位置后移一位 print("********出队列成功********") else: print("********队列已空********") # 获取队列首元素 def get_queue_top(self): if self.front == self.rear: print("********空队列********") return None else: return self.queue[self.front] # 获取队列尾元素 def get_queue_tail(self): if self.front == self.rear: print("********空队列********") return None else: return self.queue[self.rear - 1] # 判断队列是否为空 def queue_is_empty(self): if self.front == self.rear: return True else: return False # 队列长度 def queue_len(self): return self.rear - self.front
方法二：链表实现队列
""" Method Two : 链表实现队列 核心思想：以链表作为存储队列数据的数据结构，Python里本身 是不含链表这种数据结构的，所以需要我们自己去写对链表的基 本操作，当然在上一章中我们已经非常熟悉链表了，所以操作起 来还是很简单。 注意：Python内置的数据结构里没有链表，我们一般用引用实现 链表这一数据结构，创建一个类LinkNode，包含两个属性，data 为数据域，存放当前结点数据，next为指针域。存放下一个结点的 地址（指针）。 Method two: linked list implementation queue Core idea: take linked list as the data structure to store queue data. Python itself does not contain linked list, so we need to write the basic operation of linked list. Of course, in the previous chapter, we are very familiar with linked list, so the operation is very simple. Note: there is no linked list in Python's built-in data structure. Generally, we use reference to implement the linked list data structure. We create a linknode class, which contains two attributes. Data is the data field, which stores the current node data, and next is the pointer field. Store the address (pointer) of the next node. """
代码
class LinkNode: def __init__(self, x): self.data = x # 数据域 self.next = None # 指针域 class LinkQueue: def __init__(self): self.pHead = None # 队列头指针 self.pEnd = None # 队列尾指针 # 入队列 def queue_push(self, x): node = LinkNode(x) # 新建一个结点 if not self.pHead: # 第一次有元素入队列 self.pHead = node self.pEnd = node else: self.pEnd.next = node # 添加队列末尾 self.pEnd = node # 尾指针后移 print("********入队列成功********") # 出队列 def queue_pop(self): if self.pHead: self.pHead = self.pHead.next print("********出队列成功********") else: print("********队列已空********") # 获取队列顶元素 def get_queue_top(self): if not self.pHead: print("********空队列********") return None else: return self.pHead.data # 判断队列是否为空 def queue_is_empty(self): if not self.pHead: return True else: return False # 获取队列尾元素 def get_queue_tail(self): if not self.pHead: print("********空队列********") return None else: return self.pEnd.data # 队列长度 def queue_len(self): link_len = 0 cur_node = self.pHead while cur_node: # 遍历计算链表长，即队列长 cur_node = cur_node.next link_len = link_len + 1 return link_len
测试代码
# 当然，也许还有别的方法，比如建一个辅助的链表 # 欢迎你说出你的想法 # 程序入口，测试函数功能 if __name__ == "__main__": # 初始化一个队列 # my_queue = ListQueue() # 列表队列测试 my_queue = LinkQueue() # 链表队列测试 # 入队列 my_queue.queue_push(1) my_queue.queue_push(2) my_queue.queue_push(4) # 获取队列顶 print("当前队列顶为：", my_queue.get_queue_top()) # 获取队列尾 print("当前队列尾为：", my_queue.get_queue_tail()) # 出队列 my_queue.queue_pop() # 判断队列是否为空 if my_queue.queue_is_empty(): print("********队列已空********") else: print("********队列没空********") # 队列长 print("队列长为：", my_queue.queue_len()) # 出队列 my_queue.queue_pop() my_queue.queue_pop() # 判断队列是否为空 if my_queue.queue_is_empty(): print("********队列已空********") else: print("********队列没空********")
运行结果
本文代码思路来自书籍《Python程序员面试宝典》，书中部分代码有问题，文中已经修改过了，并添加上了丰厚的注释，方便大家学习，后面我会把所有内容开源放到Github上，包括代码，思路，算法图解（手绘或者电脑画），时间充裕的话，会录制视频。希望大家多多支持。
大家好，我是老表
觉得本文不错的话，转发、留言、点赞，是对我最大的支持。
欢迎关注微信公众号：简说Python
关注后回复：1024，可以领取精选编程学习电子书籍。
