5. 队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称 FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

与栈一样，队列可以通过顺序表或链表来实现。

5.1 单向队列

单向队列就像排队一样，先进先出，其结构如下：

image

单向队列操作

enqueue(item) ：往队列中添加一个item元素
dequeue()：从队列头部删除一个元素
is_empty()：判断一个队列是否为空
size()：返回队列的大小

同样地，这里也以 list 实现单向队列，当然你也可以使用链表实现。

class Queue(object):
    """创建一个空的队列"""

    def __init__(self):
        """
        用顺序表实现队列，Python 中 list 是顺序表
        队列：先进先出
        以列表尾部为队头（append：O(1)，就要从列表头就是队列尾部（pop(0)：O(n)）
        以列表头部为队头（insert(0, item)：O(n)，就要从列表就尾是队列尾部（pop()：O(1)）
        所有哪种方法都可以
        """
        # 定义一个列表，用来存储元素
        self.__list = []

    def enqueue(self, item):
        """往队列中添加一个item元素"""
        self.__list.append(item)

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

    def is_empty(self):
        """判断栈是否为空
        若 self.__list 为空，则为 False，
        [] 也是 False，两者为真，返回 True
        """
        return self.__list == []

    def size(self):
        """返回栈的元素个数"""
        return len(self.__list)


if __name__ == '__main__':
    q = Queue()
    print(q.is_empty())
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)

    print(q.size())
    print(q.is_empty())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

    print(q.is_empty())

如果用 list 实现单向队列，不管是以 list 头部作为队头还是队尾，最终的结果都是有一个 O(n) 还有个 O(1）。

运行结果如下：

# 先进先出
True
3
False
1
2
3
True

5.2 双端队列

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

image

操作

add_front(item)：从队头加入一个item元素
add_rear(item) ：从队尾加入一个item元素
remove_front() ：从队头删除一个item元素
remove_rear()：从队尾删除一个item元素
is_empty() ：判断双端队列是否为空
size() ：返回队列的大小

class Deque(object):
    """创建一个空的双端队列"""

    def __init__(self):
        """
        用顺序表实现栈，Python 中 list 是顺序表
        栈：先进先出
        以列表尾部为队头（append：O(1)，就要从列表头就是队列尾部（pop(0)：O(n)）
        以列表头部为队头（insert(0, item)：O(n)，就要从列表就尾是队列尾部（pop()：O(1)）
        所有哪种方法都可以
        """
        # 定义一个列表，用来存储元素
        self.__list = []

    def add_front(self, item):
        """从队头加入一个item元素"""
        self.__list.insert(0, item)     # O(n)
        # self.__list.append(item)      # O(1)

    def add_rear(self, item):
        """从队尾加入一个item元素"""
        self.__list.append(item)        # O(1)
        # self.__list.insert(0, item)   # O(n)

    def remove_front(self):
        """从队头删除一个item元素"""
        return self.__list.pop(0)       # O(n)
        # return self.__list.pop()      # O(1)

    def remove_rear(self):
        """从队尾删除一个item元素"""
        return self.__list.pop()        # O(1)
        # return self.__list.pop(0)     # O(n)

    def is_empty(self):
        """判断栈是否为空
        若 self.__list 为空，则为 False，
        [] 也是 False，两者为真，返回 True
        """
        return self.__list == []

    def size(self):
        """返回栈的元素个数"""
        return len(self.__list)


if __name__ == '__main__':
    q = Deque()
    print(q.is_empty())
    q.add_front(1)      # 1
    q.add_front(2)      # 2 1
    q.add_rear(3)       # 2 1 3

    print(q.size())     # 3
    print(q.is_empty())     # False
    print(q.remove_front())     # 2
    print(q.remove_front())     # 1
    print(q.remove_rear())      # 3

    print(q.is_empty())         # True

运行结果如下：