python实现队列

雨点打透心脏的1/2处 2022-10-28 10:23 3阅读 0赞

队列(Queue):和栈一样，也是一种操作受限的线性表，但它只允许在表的一端进行插入，在另一端进行删除。操作特征是先进先出(FIFI,First In First Out)  
队头(Front):允许删除的一端，又称为队首  
队尾(Rear):允许删除的一端  
空队列：不含有任何元素的空表  
![在这里插入图片描述][20210206090742135.png]

队列常见操作：  
IniQueue():初始化队列，构造一个空队列  
isempty():判空  
isfull():判满  
EnQueue():若队列未满，从队尾入队  
DeQueue():若队列非空，从队首出队  
GetHead():获取队首元素  
**顺序队列：**  
分配一块连续的存储单元，并附带两个指针front和rear分别指示队首元素和队尾元素，一般队首指针指向队首元素，队尾指针指向队尾元素的下一个位置。  
![在这里插入图片描述][20210206091459896.png]

class myQueue():
    
        def __init__(self, size):#初始化一个空队列
            self.size = size
            self.front =0
            self.rear = 0
            self.queue = []
    
        def enqueue(self, x):  # 入队操作
            if self.isfull():
                print("queue is full")
                return False
            else:
                self.queue.append(x)
                self.rear = self.rear + 1
                return True
    
        def dequeue(self):  # 出队操作
            if self.isempty():
                print("queue is empty")
                return False
            else:
                duiwei = self.queue[self.front]
                self.front = self.front + 1
                self.queue.pop(self.front)
                return duiwei
    
        def isfull(self):
            return self.rear - self.front + 1 == self.size
        def isempty(self):
            return self.front == self.rear
    
        def gethead(self):
            if self.isempty():
                return False
            else:
                return self.queue[self.front]
    
        def show(self):
            print(self.queue)
    
    qq= myQueue(10)
    print("初始化队列为空",qq.isempty())
    
    for i in range(10):
        qq.enqueue(i)
    qq.show()
    print("插入十个元素后，队满",qq.isfull())
    print(qq.dequeue())

输出为：

初始化队列为空 True
    queue is full
    [0, 1, 2, 3, 4, 5, 6, 7, 8]
    插入十个元素后，队满 True
    0

需要注意的地方：  
1)初始状态(队列为空):front==rear=0  
2)入队：队不满时，先送值到队尾元素，然后rear加1  
3)出队：队非空时，先取队首元素的值，然后front加1  
4)不可以用"rear=size"来判断队列是否为满，上图(d)也满足"rear=size"，但不是队列为满，这是一种假溢出。

**循环队列**  
顺序队列存在缺点，元素出队后该位置就空着而没有被利用，最终造成假溢出，新的元素也无法入队。使用循环队列来解决这个问题：即把存储队列元素的表从逻辑上看作一个环。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70]

初始时：front=rear=0  
出队时：front=(front+1)%size  
入队时：rear=(rear+1)%size  
元素个数：(rear+size-front)%size  
队空的条件：rear=front  
队满的条件：rear=front,如图所示，将会导致无法判断队空或者队满。  
三种方式来区分队空还是队满：  
1)牺牲一个单元，入队时少用一个队列单元，即队列的元素个数最大为size-1  
元素个数：(rear+size-front)%size  
队空的条件：rear=front  
队满的条件：(rear+1)%size=front  
2)队列增加一个元素个数的数据成员，elenum=0时队列为空，elenum=size时队列为满。  
3)类型中增加一个tag数据成员，出队导致rear=front，tag=0,表示队空；入队导致rear=front,tag=1，表示队满  
第一种方式的代码实现如下：

class myCycleQueue():
        def __init__(self,size):  #初始化
            self.rear=0
            self.front=0
            self.size=size
            self.queue=[]
        def isempty(self): #判空
            return True if self.front==self.rear else False
        def isfull(self): #判满
            return True if (self.rear+1)%self.size==self.front else False
        def elenum(self): #获取元素个数
            return (self.rear + self.size - self.front)%self.size
        def enqueue(self,x): #入队
            if self.isfull():
                print("queue is full")
                return False
            else:
                self.queue.append(x)
                self.rear=(self.rear+1)%self.size
        def dequeue(self): #出队
            if self.isempty():
                print("queue is empty")
                return False
            else:
                x=self.queue[self.front]
                self.front=(self.front+1)%self.size
                self.queue.pop(self.front)
                return x

链队列：  
同时带有队头指针和队尾指针的单链表，头指针指向队头节点，队尾指针指向队尾结点。  
![在这里插入图片描述][20210206115034227.png]

[20210206090742135.png]: /images/20221024/4703bede7e854178a9c670ac0234a429.png
[20210206091459896.png]: /images/20221024/627a083a8c114f1eb79460cafa15d6b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70]: /images/20221024/89fd945dfd9048728eb11d972744982f.png
[20210206115034227.png]: /images/20221024/c94667e4b48a4379b8979ba5a8a7d231.png