Python3数据结构06 - 队列

  • 原创
  • Madman
  • /
  • 2018-09-07 13:36
  • /
  • 0
  • 38 次阅读

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 + ' 队尾插入一些元素后: ' + '*' * 20)
    print('是否为空队列: ', q.is_empty())
    print('队列的元素个数: ', q.size())

    # 队头删除一些元素
    print('*' * 20 + ' 元素按入队的顺序依次出队: ' + '*' * 20)
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

    # Output:
    # ******************** 空队列时: ********************
    # 是否为空队列:  True
    # 队列的元素个数:  0
    # ******************** 队尾插入一些元素后: ********************
    # 是否为空队列:  False
    # 队列的元素个数:  5
    # ******************** 元素按入队的顺序依次出队: ********************
    # 10
    # Python
    # 23.5
    # Hello
    # 100

3. 双端队列

双端队列(deque,全名double-ended queue)是一种具有队列性质的抽象数据类型。双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行

上图中,如果我们只看左边到中间的部分,则它其实就是一个的结构。所以,如果你是在左边先插入,然后还在左边删除的话,则元素是后进先出

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

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

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

    def append(self, value):
        '''尾部插入'''
        self.__list.append(value)

    def appendleft(self, value):
        '''头部插入'''
        self.__list.insert(0, value)

    def pop(self):
        '''尾部删除'''
        return self.__list.pop()

    def popleft(self):
        '''头部删除'''
        return self.__list.pop(0)

测试:

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

    # 尾部插入一些元素
    q.append(10)
    q.append('Python')
    q.append(23.50)
    print('*' * 20 + ' 尾部插入一些元素后: ' + '*' * 20)
    print('是否为空双端队列: ', q.is_empty())
    print('双端队列的元素个数: ', q.size())

    # 尾部删除
    print('*' * 20 + ' 尾部删除(后进先出): ' + '*' * 20)
    print(q.pop())
    print('双端队列的元素个数: ', q.size())

    # 头部插入一些元素
    q.appendleft('Hello')
    q.appendleft('100')
    print('*' * 20 + ' 头部插入一些元素后: ' + '*' * 20)
    print('双端队列的元素个数: ', q.size())

    # 头部删除
    print('*' * 20 + ' 头部删除(后进先出): ' + '*' * 20)
    print(q.popleft())
    print('双端队列的元素个数: ', q.size())

    # Output:
    # ******************** 空双端队列时: ********************
    # 是否为空双端队列:  True
    # 双端队列的元素个数:  0
    # ******************** 尾部插入一些元素后: ********************
    # 是否为空双端队列:  False
    # 双端队列的元素个数:  3
    # ******************** 尾部删除(后进先出): ********************
    # 23.5
    # 双端队列的元素个数:  2
    # ******************** 头部插入一些元素后: ********************
    # 双端队列的元素个数:  4
    # ******************** 头部删除(后进先出): ********************
    # 100
    # 双端队列的元素个数:  3

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

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3数据结构06 - 队列

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

0 条评论

暂时还没有评论.

发表评论前请先登录