python数据结构之队列

python学习笔记之队列

数据结构-队列

队列是有序数据集合，队列的特点，删除数据项是在头部，称为前端(front)，增加数据在尾部，称为后端(rear)。数据项总是开始排在队伍的后端，慢慢向前走，直到排到最前面，轮到它的时候离开队列。

刚进来的数据排在后端，待在队伍里时间最长的在前端，这种排列规则叫做FIFO(first-in first-out)，意思是“先进先出”，或者叫做“先来先服务”(first-come first-served)

队列一般提供以下接口：

1. Queue() 定义一个空队列，无参数，返回值是空队列
2. enqueue(item) 在队列尾部加入一个数据项，参数是数据项，无返回值
3. dequeue() 删除队列头部的数据项，不需要参数，返回值是被删除的数据，队列本身有变化。
4. isEmpty() 检测队列是否为空。无参数，返回布尔值。
5. size() 返回队列数据项的数量。无参数，返回一个整数。

用python的list数据类型能比较容易的实现队列数据模型，但这里不以list来实现。我们假设队列里的元素有一个指针，最先加进元素的指针指向它下一个元素，依次类推，最后一个元素的指针是指向None。所以队列里的元素可以抽象出一个类来，同样像链表时的Node类一样，Node类里有自己的数据和一个指向None的指针。一个Node对象如下示意图：

而队列里分为两端，一端叫前端，这一端做数据的删除操作，另一端叫后端，做数据的增加操作。数据只能从后端加入，并只能从前端删除。为了抽象这个Queue类，会创建两个指针，一个head，指向队头的元素，一个tail，指向队尾的元素。如果是一个空的队列，那head和tail都指向None。

一个空队列示意图：

当队列里有一个元素时，head和tail两个指针都指向这个元素，示意图是这样的：

当队列再增加一个元素时，tail指针会移动到新增加的这个元素，前一个元素的next指针也会指向新元素，而head指针不会发生改变，如下图：

不断向队列增加元素时，各个指针移动方式如上。

当是删除元素时，直接把head指针移动到下一个元素，再把值弹出即可。

来看一个最简单队列的代码实现：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
 
 
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
 
    def enqueue(self, value):
        node = Node(value)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
 
    def dequeue(self):
        if self.head is None:
            raise Exception('This is a empty queue')
        cur = self.head
        self.head = cur.next
        return cur.value
 
    def is_empty(self):
        return self.head is None
 
    def size(self):
        cur = self.head
        count = 0
        if cur is None:
            return count
        while cur.next is not None:
            count += 1
            cur = cur.next
        return count + 1
 
 
if __name__ == '__main__':
    q = Queue()
    for i in range(5):
        q.enqueue(i)
    for _ in range(5):
        print(q.dequeue())
    print(q.is_empty())
    print(q.size())
 

在实际编码中不会自己来实现一个队列，而是使用标准库中的queue，通过from queue import Queue来导入Queue类。