数据结构--队列、双端队列实际举例详解（Python代码）

一、队列

1. 一种特殊的线性表，特殊之处在于它只能在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。简而言之，就像排队一样，先进先出：FIFO（First In First Out）
2. 进行添加操作的端称为队尾，进行删除操作的端称为队头。

1.1举例

第一个就队头，第二个就是队尾，队头进行删除操作，队尾进行添加操作。比如说我们早上去买包子，人多了就得排队，买包子的人是从队尾开始排（添加），你排第一个的时候就可以付钱拿着包子走人了（删除）。

1.2代码

#coding=utf-8

class Queue(object):
    '''
    enter_queue():往队列末尾添加一个元素
    delete_queue():从队列头部删除一个元素
    is_empty():判空操作
    size():返回队列的大小
    '''

    def __init__(self):
        # 空的列表，保存队列数据
        self.list = []

    def enter_queue(self,item):
        # 往队列末尾添加一个元素
        self.list.append(item)

    def delete_queue(self):
        # 从队列头部删除一个元素
        return self.list.pop(0)
        # return self.list，这是返回列表

    def is_empty(self):
        # 判空操作
        return self.list == []

    def size(self):
        # 返回队列的大小
        return len(self.list)


 # 数据测试
if __name__ == "__main__":
    a = Queue()
    a.enter_queue("第一个排队== 第一个买到包子的人")
    a.enter_queue("第二个排队== 第二个买到包子的人")
    a.enter_queue("第三个排队== 第三个买到包子的人")

    print(a.delete_queue())
    print(a.delete_queue())
    print(a.delete_queue())

1.3运行结果

二、双端队列

其两端都可以入列和出列的数据结构，如下图所示，队尾（rear）和队头（front）都可以加入和移出数据
注意：其具有队列和栈的性质

2.1举例

（想来想去都不知道用什么例子好，这是我目前能够想到的最好的一个例子了呜呜呜）
想象一下这是一个酒店吧，它有两个门，一个前门，一个后门，前门可以进，也可以出，后门可以进，也可以出

2.2代码

#coding=utf-8

"""
add_front():从队列头部加入一个元素
add_rear():从队列尾部加入一个元素
remove_front():从队列头部删除一个元素
remove_rear():从队列尾部删除一个元素
is_empty(): 判空操作
size():返回队列的大小
"""

class Double_ended_queue():
    def __init__(self):
        # 空的列表，保存队列数据
        self.list = []

    def add_front(self, item):
        # 从队列头部加入一个元素
        self.list.insert(0,item)

    def remove_front(self):
        # 从队列头部删除一个元素
        return self.list.pop(0)

    def add_rear(self, item):
        # 从队列尾部添加一个元素
        self.list.append(item)

    def remove_rear(self):
        # 从队列尾部删除一个元素
        return self.list.pop()

    def is_empty(self):
        # 判空操作
        return self.list == []

    def size(self):
        # 返回队列的大小
        return len(self.list)

    # 数据测试


if __name__ == "__main__":
    a =Double_ended_queue()
    a.add_front("前门进的第一个人")
    a.add_front("前门进的第二个人")
    a.add_front("前门进的第三个人")
    a.add_rear("后门进的第一个人")
    a.add_rear("后门进的第二个人")
    a.add_rear("后门进的第三个人")

    # 从队尾出队
    print(a.remove_rear())
    print(a.remove_rear())
    print(a.remove_rear())
    print(a.remove_rear())
    print(a.remove_rear())
    print(a.remove_rear())

2.3运行结果

本文地址：https://blog.csdn.net/hanhanwanghaha/article/details/107582842