Python3数据结构06 - 队列

  • 原创
  • Madman
  • /
  • /
  • 0
  • 2122 次阅读

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)
    print('*' * 20 
                                
                            
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构06 - 队列

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.