LeetCode 刷题之队列

缺乏、安全感 2024-03-27 17:41 88阅读 0赞

## 5. 队列 ##

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

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

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

### 5.1 单向队列 ###

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

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iwv6VZyb-1676469300275)(https://hubery624.oss-cn-shenzhen.aliyuncs.com/排队.jpeg)\]

**单向队列操作**

*  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），是一种具有队列和栈的性质的数据结构。

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

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9PGhQNjW-1676469300275)(https://hubery624.oss-cn-shenzhen.aliyuncs.com/20200613105121.png)\]

**操作**

*  `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

运行结果如下：

True
    3
    False
    2
    1
    3
    True