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