数据结构

队列是一种基本的数据结构，它遵循先进先出（FIFO, First In First Out）的原则。这意味着最先添加到队列中的元素将是第一个被移除的。队列通常用于任务调度、广度优先搜索等场景。

队列的基本操作

  1. 入队（Enqueue） ：将一个新元素添加到队列的末尾。
  2. 出队（Dequeue） ：从队列的前端移除并返回一个元素。
  3. 查看队首元素（Front） ：返回队列的第一个元素，但不移除它。
  4. 检查队列是否为空（IsEmpty） ：检查队列中是否没有任何元素。

队列的实现方式

数组实现队列

使用数组来实现队列是最直观的方法。我们可以定义一个固定大小的数组，并维护两个指针，分别指向队列的前端和后端。

class Queue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * self.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 self.is_full():
            print("Queue Overflow")
            return
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow")
            return None
        temp = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return temp

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

# 示例使用
q = Queue(5)
q.enqueue(1)
q.enqueue(2)
print(q.front_element())  # 输出: 1
print(q.dequeue())        # 输出: 1

链表实现队列

链表可以更灵活地处理动态大小的队列，不需要预先定义容量。

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def is_empty(self):
        return self.front is None

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

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow")
            return None
        temp = self.front
        self.front = temp.next
        if self.front is None:
            self.rear = None
        return temp.data

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

# 示例使用
q = Queue()
q.enqueue(1)
q.enqueue(2)
print(q.front_element())  # 输出: 1
print(q.dequeue())        # 输出: 1

应用场景

  • 任务调度：操作系统中，CPU调度器使用队列来管理就绪进程。
  • 广度优先搜索（BFS） ：图的BFS算法使用队列来追踪需要访问的节点。
  • 缓存系统：LRU缓存淘汰策略使用队列来追踪最近最少使用的项目。

发表评论