队列 Queue First In First Out FIFO

队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的线性数据结构。在队列中，元素的添加总是在一端进行，称为队尾（Rear），而元素的移除总是在另一端进行，称为队首（Front）。

队列的基本操作：

Enqueue：在队尾添加一个元素。
Dequeue：移除队首的元素，并返回它。
Peek/Front：查看队首的元素，但不移除它。
IsEmpty：检查队列是否为空。
IsFull：检查队列是否已满（对于固定大小的队列）。
Size：获取队列中元素的数量。

队列的实现方式：

队列可以用数组、链表或循环数组来实现。

数组实现：

使用数组实现队列时，需要两个指针，一个指向队首，一个指向队尾。当到达数组末尾时，需要回绕到数组开始位置。

#include <iostream>
#include <vector>

class Queue {
private:
    std::vector<int> elements;
    int frontIndex;
    int rearIndex;
    bool isFull;

public:
    Queue(int size) : frontIndex(0), rearIndex(0), isFull(false) {
        elements.resize(size);
    }

    void enqueue(int element) {
        if (isFull) {
            throw std::overflow_error("Queue is full");
        }
        elements[rearIndex] = element;
        rearIndex = (rearIndex + 1) % elements.size();
        isFull = rearIndex == frontIndex;
    }

    int dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        int element = elements[frontIndex];
        frontIndex = (frontIndex + 1) % elements.size();
        isFull = false;
        return element;
    }

    int peek() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        return elements[frontIndex];
    }

    bool isEmpty() {
        return (!isFull && rearIndex == frontIndex);
    }

    bool isFull() {
        return isFull;
    }

    size_t size() {
        return isFull ? elements.size() : (rearIndex - frontIndex + elements.size()) % elements.size();
    }
};

链表实现：

使用链表实现队列时，不需要担心数组的固定大小问题。链表的头节点对应队首，尾节点对应队尾。

#include <iostream>
#include <memory>

class Node {
public:
    int data;
    std::unique_ptr<Node> next;

    Node(int data) : data(data), next(nullptr) {}
};

class Queue {
private:
    std::unique_ptr<Node> head; // 队首节点
    std::unique_ptr<Node> rear; // 队尾节点

public:
    Queue() : head(nullptr), rear(nullptr) {}

    void enqueue(int element) {
        auto newNode = std::make_unique<Node>(element);
        if (!head) {
            head = std::move(newNode);
            rear = head.get();
        } else {
            rear->next = std::move(newNode);
            rear = rear->next.get();
        }
    }

    int dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        int element = head->data;
        auto oldHead = std::move(head);
        head = std::move(oldHead->next);
        if (head == nullptr) {
            rear = nullptr;
        }
        return element;
    }

    int peek() {
        if (isEmpty()) {
            throw std::underflow_error("Queue is empty");
        }
        return head->data;
    }

    bool isEmpty() {
        return head == nullptr;
    }

    size_t size() {
        size_t count = 0;
        auto current = head.get();
        while (current != nullptr) {
            count++;
            current = current->next.get();
        }
        return count;
    }
};

队列的应用场景：

任务调度：在操作系统中，进程和线程调度使用队列来管理任务队列。
缓冲处理：如打印机任务队列，按照先进先出的顺序处理打印请求。
广度优先搜索：在图算法中，广度优先搜索使用队列来遍历节点。
实时处理系统：如网络请求处理，按照接收顺序响应请求。
生产者-消费者问题：生产者将产品放入队列，消费者从队列中取出产品。

队列是一种基础的数据结构，广泛应用于需要按顺序处理元素的场景。通过提供先进先出的操作，队列可以有效地管理数据流和任务队列。

(责任编辑：admin)

热门: