数据结构第一弹-队列

大家好，今天和大家一起分享一下数据结构中的队列相关内容~

队列是一种非常重要的线性数据结构，遵循先进先出（FIFO, First In First Out）的原则。

一、队列概述

队列是一种特殊的线性表，它只允许在一端进行插入操作，在另一端进行删除操作。队列的入口称为队尾（rear），出口称为队头（front）。新元素总是被添加到队尾，而移除时总是从队头开始。这种特性使得队列非常适合用于处理需要按顺序处理的任务列表，如任务调度、消息传递等场景。

队列的基本操作

• Enqueue（入队）：向队尾添加一个新元素。
• Dequeue（出队）：从队头移除一个元素。
• Front（查看队头）：返回队头元素但不移除。
• Rear（查看队尾）：返回队尾元素但不移除。
• isEmpty（检查是否为空）：判断队列是否为空。
• isFull（检查是否已满）：对于固定大小的队列，判断队列是否已满。
• Size（获取长度）：返回队列中的元素数量。

二、队列的实现

队列可以通过多种方式实现，包括数组、链表甚至是循环队列。每种实现都有其优缺点，适用于不同的应用场景。

1. 数组实现

使用数组实现队列是最直观的方法之一。通过维护两个指针——front 和 rear 来追踪队列的头部和尾部位置。当队列满了或空了时，需要特殊处理来避免数组越界。

class ArrayQueue:

    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

    def enqueue(self, item):
        if not self.is_full():
            self.rear = (self.rear + 1) % self.capacity
            self.queue[self.rear] = item
            self.size += 1
        else:
            print("Queue is full")

    def dequeue(self):
        if not self.is_empty():
            removed_item = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.capacity
            self.size -= 1
            return removed_item
        else:
            print("Queue is empty")
            return None

    def front_element(self):
        if not self.is_empty():
            return self.queue[self.front]
        else:
            print("Queue is empty")
            return None

    def rear_element(self):
        if not self.is_empty():
            return self.queue[self.rear]
        else:
            print("Queue is empty")
            return None

    def get_size(self):
        return self.size

2. 链表实现

链表实现队列可以动态地调整大小，不需要预先设定容量。每个节点包含数据域和指向下一个节点的指针。通过维护队头和队尾两个指针，可以高效地执行入队和出队操作。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def enqueue(self, item):
        new_node = Node(item)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node

        else:
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty")
            return None

        removed_item = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        self.size -= 1
        return removed_item

    def front_element(self):
        if not self.is_empty():
            return self.front.data
        else:
            print("Queue is empty")
            return None

    def rear_element(self):
        if not self.is_empty():
            return self.rear.data
        else:
            print("Queue is empty")
            return None

    def get_size(self):
        return self.size

3. 循环队列

循环队列是一种特殊的数组队列，它可以有效地利用数组空间。当队尾到达数组末尾时，会自动回到数组起始位置。循环队列通过模运算来计算索引，以保持队列的连续性。

class CircularQueue:

    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.capacity

    def enqueue(self, item):

        if not self.is_full():
            self.queue[self.rear] = item
            self.rear = (self.rear + 1) % self.capacity
            self.size += 1
        else:
            print("Queue is full")

    def dequeue(self):

        if not self.is_empty():
            removed_item = self.queue[self.front]
            self.queue[self.front] = None
            self.front = (self.front + 1) % self.capacity
            self.size -= 1
            return removed_item
        else:
            print("Queue is empty")
            return None

    def front_element(self):
        if not self.is_empty():
            return self.queue[self.front]
        else:
            print("Queue is empty")
            return None

    def rear_element(self):
        if not self.is_empty():
            return self.queue[(self.rear - 1) % self.capacity]
        else:
            print("Queue is empty")
            return None

    def get_size(self):
        return self.size

三、队列的应用

队列在许多领域有着广泛的应用，下面列举几个常见的例子：

1. 操作系统中的进程调度

操作系统使用队列来管理等待CPU时间片的进程。按照优先级或其他策略安排进程进入就绪队列，然后根据一定规则选择下一个执行的进程。

2. 缓冲区

在网络通信中，队列常用来作为缓冲区，临时存放待发送或接收的数据包。这样可以平滑数据流，提高网络传输效率。

3. 打印机任务队列

打印机通常有一个任务队列，用户提交打印请求后，这些请求会被加入到队列中，打印机依次处理这些任务。

4. 广度优先搜索（BFS）

在图论中，广度优先搜索算法使用队列来探索图的各个顶点。从起始顶点开始，逐层向外扩展，直到遍历完所有可达顶点。

实战案例：银行排队系统

假设我们正在设计一个简单的银行排队系统，顾客到达银行后需要取号等待办理业务。我们可以使用队列来模拟这个过程。

# 使用链表实现的队列

bank_queue = LinkedListQueue()

def customer_arrives(customer_id):
    bank_queue.enqueue(customer_id)
    print(f"Customer {customer_id} has joined the queue.")

def call_next_customer():
    next_customer = bank_queue.dequeue()
    if next_customer is not None:
        print(f"Calling customer {next_customer} to the counter.")
    else:
        print("No more customers in the queue.")

# 模拟客户到达
for i in range(1, 11):
    customer_arrives(i)

# 处理客户
for _ in range(5):
    call_next_customer()

在这个例子中，每当有新顾客到达银行时，他们会被加入到队列中。当柜员准备好服务下一位顾客时，调用call_next_customer函数从队列中取出并处理最前面的顾客。

队列作为一种基础的数据结构，在计算机科学中扮演着重要角色。无论是简单的线性队列还是更复杂的循环队列，都能有效解决各种场景，欢迎大家一起讨论~