我要评论python用数组和链表实现队列
题目描述:
实现一个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大 小 等功能。
方法一:数组实现
下图给出了 一种最简单的实现方式，用台ont来记录队列首元素的位置，用 rear来记录队 列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为 rear 的位置， 同时执行 rear+，出队列的时候只需要执行font+即可 。
class MyQueue:
def __init__(self):
self.arr=[]
self.front=0
self.rear=0
def isEmpty(self):
return self.front==self.rear
def size(self):
return self.rear-self.front
def getFront(self):
if self.isEmpty():
return None
return self.arr[self.front]
def getBack(self):
if self.isEmpty():
return None
return self.arr[self.rear-1]
def deQueue(self):
if self.rear>self.front:
self.front+=1
else:
print('队列已经为为空')
def enQueue(self,item):
self.arr.append(item)
self.rear+=1
if __name__=='__main__':
queue=MyQueue()
queue.enQueue(1)
queue.enQueue(2)
print('队列头元素为：'+str(queue.getFront))
print('队列的尾元素为：'+str(queue.getBack()))
print('队列大小为：'+str(queue.size()))
方法二:链表实现
采用链表实现队列的方法与实现拢的方法类似，分别用两个指针指向队列的首元素与尾
元素，如下图所示。用 pHead 来指向队列的首元素，用 pEnd 来指向队列的尾元素。
在上图中，刚开始队列中只有元素 l、 2 和 3， 当新元素 4 要进队列的时候 ，只 需要上图 中 (1)和( 2)两步，就可以把新结点连接到链表的尾部，同时修改 pEnd 指针指向新增加的 结点。 1±1队列的时候只需要步骤(刀，改变 pHead 指针使其指向 pHead.next，此外也需要考 虑结点所占空间释放的问题 。 在入队列与出队列的操作中也需要考虑队列尾空的时候的特殊 操作，实现代码如下所示 :
class LNode:
def __init__(self,x):
self.data=x
self.next=None
class MyQueue:
def __init__(self):
self.pHead=None
self.pEnd=None
def empty(self):
if self.pHead==None:
return True
else:
return False
def size(self):
size=0
p=self.pHead
while p!=None:
p=p.next
size+=1
return size
def enQueue(self,e):
p=LNode(0)
p.data=e
p.next=None
if self.pHead==None:
self.pHead=self.pEnd=p
else:
self.pEnd.next=p
self.pEnd=p
def deQueue(self):
if self.pHead==None:
print('出列失败，队列为空')
self.pHead=self.pHead.next
if self.pHead==None:
self.pEnd=None
def getFront(self):
if self.pHead==None:
print('获取队列首元素失败，队列为空')
return None
return self.pHead.data
def getBack(self):
if self.pEnd==None:
print('获取队尾的元素失败，队列尾空')
return None
return self.pEnd.data
if __name__=='__main__':
queue=MyQueue()
queue.enQueue(1)
queue.enQueue(2)
print('队列头元素为：'+str(queue.getFront))
print('队列的尾元素为：'+str(queue.getBack()))
print('队列大小为：'+str(queue.size()))
本文地址：https://blog.csdn.net/weixin_42813521/article/details/107670621
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论