python初步了解队列

python初步了解队列

队列

是一种先入先出的数据结构

单纯用列表来实现队列运用pop()函数，进行出队效率很低，因为在列表开头删除元素需要将其他元素往前移动一位.

所以一般用其他方法实现队列。实现队列一般使用两个指针分别指向前端和后端，

便于删除和添加元素。

在使用队列时一般使用循环队列以避免浪费空间。

循环队列要实现以下几点

（1）入队

（2）出队

（3）判断是否为空队列

（4）判断队列是否已满

（5）返回队列前端和后端的值

数组实现(顺序队列)

数组实现队列要先创建固定队列长度，以此来创建一个列表，front和rear分别对应队列前端和后端的索引位置。由于rear所对应的后端要超出队列一个元素，所以设计时应当时列表比给出的长度多一格，以避免程序报错。

class Queue:
    def __init__(self,size):        #设置队列
        self.size = size + 1          
        self.queue = [0] * self.size  #生成队列
        self.front = self.rear = 0    #设置指针

    def enqueue(self,data):           #入队
        if self.isfull():             
            print("队列已满")
        else:
            self.queue[self.rear] = data
            self.rear = (self.rear + 1) % self.size

    def dequeue(self):               #出队
        if self.isempty():
            print("队列为空")
        else:
            self.front = (self.front + 1) % self.size

    def isempty(self):         #判断是否为空
        return self.front == self.rear

    def isfull(self):          #判断是否已满
        return (self.rear + 1) % self.size == self.front

    def frontitem(self):       #输出队头
        if self.isempty():
            print("队列为空")
        else:
            print(self.queue[self.front])

    def rearitem(self):       #输出队尾
        if self.isempty():
            print("队列为空")
        else:
            print(self.queue[(self.rear - 1 + self.size)] % self.size)% self.size

重点在于对指针的循环操作。两个指针不断移动表示队列的长度，当指针所对应的下标超过列表长度时，做循环处理，即让指针再次从下标为0出开始循环。

链表实现(链式队列)

使用链表实现更加简单，由于要动态创建和删除节点，效率较低，但是优点在于可以动态增长。

class Node:     #设置节点
    def __init__(self,data = None,next = None):
        self.data = data
        self.next = next

class Queue:      #设置队列
    def __init__(self,head = Node()):   #引入头节点
        self.front = self.rear = head  #设置前端和后端

    def enqueue(self,data):    #引入新元素
        self.new = Node(data)  #创建新元素的节点
        self.rear.next = self.new  #使后端的next指向新节点
        self.rear = self.new       #让新阶段成为后端

    def dequeue(self):         #删除节点
        if self.isempty():
            print("队列为空")
        else:
            self.front = self.front.next    #将前端指向原前端的next

    def isempty(self):
        return self.front == self.rear

    def frontitem(self):
        if self.isempty():
            print("队列为空")
        else:
            print(self.front.data)

    def rearitem(self):
        if self.isempty():
            print("队列为空")
        else:
            print(self.rear.data)

deque()

python3的官方文档中有介绍实现队列的方法，运用collection.deque来实现，可以快速从两端添加和删除元素。

如下：

from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")          
queue.append("Graham")       
queue.popleft()                 
#'Eric'
queue.popleft()            
#'John'
queue                      
#deque(['Michael', 'Terry', 'Graham'])

十分的简便。