欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python用数组和链表实现队列

程序员文章站 2022-04-03 10:13:42
python用数组和链表实现队列题目描述:实现一个队列的数据结构,使其具有入队列、出队列、查看队列首尾元素、查看队列大 小 等功能。方法一:数组实现下图给出了 一种最简单的实现方式,用台ont来记录队列首元素的位置,用 rear来记录队 列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为 rear 的位置, 同时执行 rear+,出队列的时候只需要执行font+即可 。class MyQueue: def __init__(self): self.arr...

python用数组和链表实现队列

题目描述:
实现一个队列的数据结构,使其具有入队列、出队列、查看队列首尾元素、查看队列大 小 等功能。

方法一:数组实现

下图给出了 一种最简单的实现方式,用台ont来记录队列首元素的位置,用 rear来记录队 列尾元素往后一个位置。入队列的时候只需要将待入队列的元素放到数组下标为 rear 的位置, 同时执行 rear+,出队列的时候只需要执行font+即可 。python用数组和链表实现队列

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 来指向队列的尾元素。python用数组和链表实现队列
在上图中,刚开始队列中只有元素 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

相关标签: leetcode