Python实现的队列数据结构详解
(一)队列的基本结构
队列是一种先进先出的数据结构(特殊的线性结构),在队列尾部插入新元素,在队列头部删除元素。
一般队列的基本操作如下:
-
create:创建空队列。
-
enqueue:将新元素加入队列的尾部,返回新队列。
-
dequeue:删除队列头部元素,返回新队列。
-
front:返回队列头部的元素值。
-
isempty:判断队列是否为空,若队列为空,返回True,否则返回False。
-
length:返回队列的长度。
队列基本操作可以通过列表或python中封装的queue类模块进行实现。
(二)队列的实现
(1)列表形式
利用列表来模拟队列的基本操作,列表的appen()方法相当于入队,在队列尾部插入一个新元素,pop()方法相当于入队,删除队列头部的元素。其实现代码如下:
class queue:
def __init__(self):
self.list = []
# 入队
def enqueue(self, item):
self.list.append(item)
# 出队
def dequeue(self):
self.list.pop(0)
# 判断是否为空
def isempty(self):
return len(self.list) == 0
# 队列长度
def length(self):
return len(self.list)
# 打印队列
def print_queue(self):
print(self.list)
# 从队头元素开始打印队列
def print_element(self):
for i in self.list:
print(i)
q = queue()
print('队列是否为空:', q.isempty())
q.enqueue('a')
q.enqueue('b')
q.enqueue('c')
q.print_queue()
q.dequeue()
q.print_element()
print('队列长度为:', q.length())
(2)queue模块
Python的queue类模块中提供了一种先进先出的队列类型Queue,同时在创建队列的过程中,队列的长队既可以限制也可以不限制,在创建队列时利用Queue(maxsize=0),maxsize小于等于0时,表示队列的长度不受限制,否则表示限制。Queue主要有以下几种方法:
put():在队列尾部添加元素。
get():从队列头部取出元素,返回队列头部元素。
empty():判断队列是否为空。
full():判断队列是否达到最大长度限制。
qsize():返回队列当前长度。
from queue import Queue
q = Queue(maxsize=0) # 创建队列
q.put(1) # 入队
q.put(2) # 入队
print(q.queue)
q.get() # 出队
print(q.queue)
print('队列长度:', q.qsize())
print('队列是否为空:', q.empty())
print('队列是否为满:', q.full())