数据结构--队列

队列

遵循先进先出FIFO（first in first out）的原则。在这种结构中，数据被依次添加到队列末端，并从队列的前端移除。类似于结账排队。

操作

队列主要支持以下几种操作

• Enqueue：将一个元素添加到队列的尾部
• Dequeue：从队列头部移除一个元素
• Front：获取头部元素（不移除）
• IsEmpty：检查队列是否为空
• Size：返回队列中元素的数量

实现

队列可以通过多种方式实现:

使用数组或列表

使用链表

可以在O(1)的时间复杂度内进行插入和删除操作

__

• 使用库queue.Queue: 这是Python标准库提供的一个线程安全的队列实现，适用于多线程环境
• 使用双端队列(duque): Python 的 collections.deque提供了一个优化的双端队列实现，适合用作队列

题目描述

实现一个循环队列。循环队列的容量可以动态调整，在队列空间不足时，需要扩大到当前容量的两倍。队列需要支持以下操作：

1. 入队：将一个元素添加到队列末尾。
2. 出队：从队列前端移除一个元素，并返回它。
3. 获取前端元素：返回队列前端的元素但不移除它。
4. 获取后端元素：返回队列后端的元素但不移除它。
5. 队列大小：返回队列中的元素数量。
6. 队列是否为空：检查队列是否为空。
7. 队列是否已满：检查队列是否达到当前容量上限。

队列初始化时为空，且初始容量设为8。

功能要求

1. 自动扩容：当尝试进行入队操作时，如果队列已满，则自动将队列容量扩大到当前的两倍。
2. 循环处理：队列使用循环的方式处理数组边界，即如果队列末尾到达数组末端但数组前端有空间，则继续在数组前端进行操作。

输入输出示例

输入：

1. 入队5次（元素为1, 2, 3, 4, 5）
2. 出队2次
3. 入队2次（元素为6, 7）
4. 获取前端元素
5. 获取后端元素
6. 队列大小

输出：

1. 元素出队：1, 2
2. 队列前端元素：3
3. 队列后端元素：7
4. 队列大小：5

代码模板

class CircularQueue:
    def __init__(self, capacity=8):
        # 初始化队列

    def enqueue(self, value):
        # 元素入队操作

    def dequeue(self):
        # 元素出队操作

    def peek_front(self):
        # 获取队列前端元素

    def peek_rear(self):
        # 获取队列后端元素

    def size(self):
        # 返回队列大小

    def is_empty(self):
        # 检查队列是否为空

    def is_full(self):
        # 检查队列是否已满

    def resize(self):
        # 扩大队列容量

# 示例使用
if __name__ == "__main__":
    queue = CircularQueue()
    # 进行入队、出队等操作，并打印结果

option + command+L