Python3数据结构06 - 队列

原创

Madman

9069 次阅读

Synopsis: 前面讲了栈数据结构，本文将先讲述队列，它具有先进先出（FIFO）的特性，只允许在队尾插入元素，在队头删除元素。队列的一个变种是双端队列，它具有队列和栈的性质，双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行

代码已上传到 https://github.com/wangy8961/python3-algorithms ，欢迎star

1. 队列

队列（queue）跟栈有一些相似之处，但它是先进先出（FIFO, First-In-First-Out）。队列只允许在后端（rear，队尾）进行插入操作（也叫入队，enqueue），在前端（front，队头）进行删除操作（也叫出队，dequeue），不允许在中间位置进行操作。类似于我们现实生活中的排队场景，排在队头的最先出队列

2. Python实现

队列也可以用顺序表或链表来实现，这里使用顺序表，即Python中的列表来实现队列数据结构

class Queue:
    '''用顺序表实现队列'''
    def __init__(self):
        self.__list = []  # 用来存放元素的容器，这里使用列表（顺序表）

    def is_empty(self):
        '''判断队列是否为空'''
        return self.__list == []

    def size(self):
        '''返回队列的元素个数'''
        return len(self.__list)

    def enqueue(self, value):
        '''往队尾插入一个元素
        这里假设队尾是列表的尾部，如果你的队列的 '出队' 操作很频繁，
        则应该设置队尾是列表的头部，这样出队操作是 self.__list.pop()，它的时间复杂度为O(1)
        '''
        self.__list.append(value)

    def dequeue(self):
        '''从队头删除一个元素'''
        return self.__list.pop(0)

测试：

if __name__ == '__main__':
    # 创建空队列
    q = Queue()
    print('*' * 20 + ' 空队列时: ' + '*' * 20)
    print('是否为空队列: ', q.is_empty())
    print('队列的元素个数: ', q.size())

    # 队尾插入一些元素
    q.enqueue(10)
    q.enqueue('Python')
    q.enqueue(23.50)
    q.enqueue('Hello')
    q.enqueue(100