数据结构--队列

队列（Queue）是一种抽象数据类型，用于按特定顺序存储和管理元素。它是一种线性数据结构，遵循先进先出（FIFO，First In First Out）的原则。这意味着最早添加的元素最早被移除。

队列的基本操作

1. 入队（Enqueue）：将一个元素添加到队列的末尾。
2. 出队（Dequeue）：从队列的前端移除一个元素。
3. 队列前端（Front 或 Peek）：返回队列前端的元素，但不移除它。
4. 队列为空（IsEmpty）：检查队列是否为空。
5. 队列大小（Size）：返回队列中元素的数量。

队列的应用

队列在很多场景中都有应用，包括：

• 任务调度：操作系统中的任务调度。
• 数据流处理：在处理数据流时，保持数据的顺序。
• 广度优先搜索（BFS）：图和树的遍历。

队列的实现

队列可以使用多种数据结构来实现，包括数组、链表和双端队列（deque）。

用数组实现的简单队列

class Queue:
    def __init__(self):
        self.queue = []
    
    def enqueue(self, item):
        self.queue.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("dequeue from empty queue")
    
    def front(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("front from empty queue")
    
    def is_empty(self):
        return len(self.queue) == 0
    
    def size(self):
        return len(self.queue)

# 示例使用
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 输出: 1
print(q.front())    # 输出: 2
print(q.is_empty()) # 输出: False
print(q.size())     # 输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

双端队列（Deque）

双端队列（Deque，Double-ended Queue）是队列的一种变体，它允许在队列的两端进行插入和删除操作。Python 提供了 collections.deque 类，用于高效地实现双端队列。

使用双端队列的示例

from collections import deque

# 创建一个双端队列
dq = deque()

# 在右侧添加元素
dq.append(1)
dq.append(2)
dq.append(3)

# 在左侧添加元素
dq.appendleft(0)

# 在右侧移除元素
print(dq.pop())  # 输出: 3

# 在左侧移除元素
print(dq.popleft())  # 输出: 0

# 获取队列前端的元素
print(dq[0])  # 输出: 1

# 获取队列大小
print(len(dq))  # 输出: 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

• 队列 是一种先进先出（FIFO）的数据结构。
• 基本操作包括入队、出队、获取前端元素、检查是否为空和获取队列大小。
• 双端队列（Deque） 允许在两端进行插入和删除操作，比普通队列更灵活。
• Python 的 collections.deque 提供了高效的双端队列实现。

通过以上示例和解释，你应该对队列有一个基本的了解，并知道如何在 Python 中使用队列和双端队列。