自己实现一个数组+结构体版队列

队列是一种基础数据结构，遵循"先进先出(FIFO)"原则。下面我将通过结构体和数组实现一个完整的队列，包含所有核心操作，并添加详细注释和使用示例。

队列的结构体设计

首先我们需要设计一个队列结构体，包含数据存储数组、头尾指针和辅助变量：

#include <iostream>
using namespace std;

// 队列最大容量
const int MAX_QUEUE_SIZE = 100;

// 队列结构体定义
typedef struct {
    int data[MAX_QUEUE_SIZE];  // 存储队列元素的数组
    int front;                 // 队头指针，指向队头元素
    int rear;                  // 队尾指针，指向队尾元素的下一个位置
    int size;                  // 队列中元素的数量
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

// 检查队列是否为空
bool isEmpty(Queue* q) {
    return q->size == 0;
}

// 检查队列是否已满
bool isFull(Queue* q) {
    return q->size == MAX_QUEUE_SIZE;
}

// 入队操作：将元素添加到队尾
bool enqueue(Queue* q, int item) {
    if (isFull(q)) {
        cout << "队列已满，无法入队！" << endl;
        return false;
    }
    
    // 使用循环队列方式处理队尾指针
    q->data[q->rear] = item;
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->size++;
    return true;
}

// 出队操作：从队头移除元素并返回
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        cout << "队列为空，无法出队！" << endl;
        return -1;  // 返回-1表示错误
    }
    
    int item = q->data[q->front];
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    q->size--;
    return item;
}

// 获取队头元素但不出队
int getFront(Queue* q) {
    if (isEmpty(q)) {
        cout << "队列为空，无法获取队头元素！" << endl;
        return -1;
    }
    return q->data[q->front];
}

// 获取队列中元素个数
int getSize(Queue* q) {
    return q->size;
}

// 打印队列所有元素
void printQueue(Queue* q) {
    if (isEmpty(q)) {
        cout << "队列为空" << endl;
        return;
    }
    
    cout << "队列中的元素（从队头到队尾）：";
    int i = q->front;
    while (i != q->rear) {
        cout << q->data[i] << " ";
        i = (i + 1) % MAX_QUEUE_SIZE;
    }
    cout << endl;
}

// 清空队列
void clearQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
    q->size = 0;
}

循环队列的工作原理

上面的实现使用了循环队列技术，这是为什么呢？

假设我们有一个固定大小的数组，如果不使用循环队列，会出现"假溢出"问题：

1. 初始状态：front=0, rear=0, size=0
2. 入队10：data[0]=10, rear=1, size=1
3. 入队20：data[1]=20, rear=2, size=2
4. 出队：front=1, size=1，此时数组索引0位置为空
5. 再次入队时，如果直接使用rear++，会导致数组末尾被填满，但前面还有空位置

循环队列通过取模运算解决了这个问题：

q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;  // 入队时
q->front = (q->front + 1) % MAX_QUEUE_SIZE;  // 出队时

这样当指针到达数组末尾时，会自动回到数组开头，形成一个环形结构。

完整的使用示例

下面是一个完整的示例，展示如何使用我们实现的队列：

int main() {
    // 创建队列结构体变量
    Queue myQueue;
    
    // 初始化队列
    initQueue(&myQueue);
    
    cout << "=== 队列操作演示 ===" << endl;
    
    // 测试入队操作
    cout << "入队操作：" << endl;
    enqueue(&myQueue, 10);
    enqueue(&myQueue, 20);
    enqueue(&myQueue, 30);
    printQueue(&myQueue);  // 应该输出: 10 20 30
    
    // 测试获取队列大小
    cout << "队列大小：" << getSize(&myQueue) << endl;  // 应该输出: 3
    
    // 测试获取队头元素
    cout << "队头元素：" << getFront(&myQueue) << endl;  // 应该输出: 10
    
    // 测试出队操作
    cout << "出队元素：" << dequeue(&myQueue) << endl;  // 应该输出: 10
    printQueue(&myQueue);  // 应该输出: 20 30
    
    // 测试再次入队
    cout << "入队操作：" << endl;
    enqueue(&myQueue, 40);
    printQueue(&myQueue);  // 应该输出: 20 30 40
    
    // 测试清空队列
    cout << "清空队列..." << endl;
    clearQueue(&myQueue);
    cout << "清空后队列是否为空：" << (isEmpty(&myQueue) ? "是" : "否") << endl;  // 应该输出: 是
    
    return 0;
}

队列操作的时间复杂度

我们实现的队列各项操作的时间复杂度如下：

操作	时间复杂度	说明
初始化队列	O(1)	仅设置指针和变量
入队(enqueue)		直接操作队尾指针
出队(dequeue)		直接操作队头指针
获取队头元素		直接访问队头元素
获取队列大小		直接返回size变量
打印队列	O(n)	需要遍历所有元素
清空队列	O(1)	仅重置指针和变量

队列与其他数据结构的区别

• 队列 vs 栈：

  • 队列：先进先出(FIFO)，元素从队尾入队，队头出队
  • 栈：后进先出(LIFO)，元素从栈顶入栈，栈顶出栈

• 队列 vs 数组/链表：

  • 队列是一种抽象数据类型，定义了特定的操作规则
  • 数组/链表是物理存储结构，可以用来实现队列

拓展：实现一个通用型队列

如果希望队列可以存储不同类型的数据，可以使用C++模板：

template <typename T>
typedef struct {
    T data[MAX_QUEUE_SIZE];
    int front;
    int rear;
    int size;
} GenericQueue;

// 模板函数实现...（与上面类似，将int改为T）

总结

通过结构体和数组实现队列，我们深入理解了队列的内部工作原理。这种实现方式：

1. 空间效率高，利用固定大小数组存储数据
2. 时间效率高，核心操作均为O(1)复杂度
3. 通过循环队列解决了"假溢出"问题

掌握队列的实现和原理，对理解更复杂的数据结构和算法（如广度优先搜索、任务调度等）非常有帮助。继续加油，你正在编程之路上稳步前进！

C++队列(Queue)完全教程：从入门到实战

🚀 欢迎来到队列的世界

在编程的世界里，数据结构就像是我们存放和管理数据的"工具箱"。今天我们要认识的这个"工具"叫做队列(Queue)，它是一种非常基础但又极其重要的数据结构。学会队列，你就掌握了处理"先来先服务"类问题的关键技能！

🌈 什么是队列？

队列是一种线性数据结构，它的特点是先进先出(First In First Out, FIFO)。就像我们日常生活中排队买票一样，先来的人先买到票离开，后来的人后买到票离开。

🎨 队列的形象比喻

想象一个水管：

┌───────────────┐
│  数据元素1    │  <- 队头(Front)
├───────────────┤
│  数据元素2    │
├───────────────┤
│  数据元素3    │
└───────────────┘  <- 队尾(Rear)

• 新元素只能从队尾进入队列（入队操作）
• 元素只能从队头离开队列（出队操作）

📦 C++中的队列实现

在C++中，我们可以通过两种方式使用队列：

1. 使用STL标准库中的queue容器适配器
2. 自己动手实现一个队列类

🌟 方法一：使用STL的queue

STL(Standard Template Library)为我们提供了便捷的queue容器，我们可以直接使用：

#include <iostream>
#include <queue>  // 队列头文件
using namespace std;

int main() {
    // 创建一个整数队列
    queue<int> myQueue;
    
    // 1. 入队操作(push)：将元素添加到队尾
    myQueue.push(10);
    myQueue.push(20);
    myQueue.push(30);
    cout << "入队后队列中的元素：";
    
    // 注意：queue不支持直接遍历，我们需要借助临时队列查看
    queue<int> tempQueue = myQueue;
    while (!tempQueue.empty()) {
        cout << tempQueue.front() << " ";  // 2. 访问队头元素(front)
        tempQueue.pop();  // 3. 出队操作(pop)：移除队头元素
    }
    cout << endl;
    
    // 4. 查看队列大小(size)
    cout << "队列中元素的个数：" << myQueue.size() << endl;
    
    // 5. 检查队列是否为空(empty)
    if (myQueue.empty()) {
        cout << "队列为空" << endl;
    } else {
        cout << "队列不为空" << endl;
    }
    
    // 6. 访问队尾元素（注意：STL queue没有直接的back()，需要自己实现）
    tempQueue = myQueue;
    int lastElement = 0;
    while (!tempQueue.empty()) {
        lastElement = tempQueue.front();
        tempQueue.pop();
    }
    cout << "队尾元素是：" << lastElement << endl;
    
    return 0;
}

🛠️ STL队列的常用操作

操作	描述	时间复杂度
push(element)	将元素添加到队尾	O(1)
pop()	移除队头元素
front()	访问队头元素
size()	返回队列中元素的个数
empty()	检查队列是否为空

🔨 方法二：自己实现一个队列（数组版）

为了更好地理解队列的内部原理，我们可以自己动手实现一个基于数组的队列：

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;  // 队列的最大容量

class Queue {
private:
    int arr[MAX_SIZE];      // 存储队列元素的数组
    int front;              // 队头指针
    int rear;               // 队尾指针
    int count;              // 队列中元素的个数

public:
    // 构造函数
    Queue() {
        front = 0;
        rear = -1;
        count = 0;
    }
    
    // 入队操作
    bool enqueue(int item) {
        if (isFull()) {
            cout << "队列已满，无法入队！" << endl;
            return false;
        }
        rear = (rear + 1) % MAX_SIZE;  // 循环队列的处理
        arr[rear] = item;
        count++;
        return true;
    }
    
    // 出队操作
    int dequeue() {
        if (isEmpty()) {
            cout << "队列为空，无法出队！" << endl;
            return -1;  // 假设-1表示错误
        }
        int item = arr[front];
        front = (front + 1) % MAX_SIZE;  // 循环队列的处理
        count--;
        return item;
    }
    
    // 查看队头元素
    int peek() {
        if (isEmpty()) {
            cout << "队列为空，无法查看！" << endl;
            return -1;
        }
        return arr[front];
    }
    
    // 查看队列大小
    int size() {
        return count;
    }
    
    // 检查队列是否为空
    bool isEmpty() {
        return count == 0;
    }
    
    // 检查队列是否已满（针对循环队列）
    bool isFull() {
        return count == MAX_SIZE;
    }
    
    // 打印队列中的元素
    void printQueue() {
        if (isEmpty()) {
            cout << "队列为空" << endl;
            return;
        }
        
        cout << "队列中的元素：";
        int i = front;
        while (i != rear) {
            cout << arr[i] << " ";
            i = (i + 1) % MAX_SIZE;
        }
        cout << arr[rear] << endl;
    }
};

int main() {
    Queue myQueue;
    
    cout << "=== 测试队列操作 ===" << endl;
    
    // 测试入队
    myQueue.enqueue(10);
    myQueue.enqueue(20);
    myQueue.enqueue(30);
    myQueue.printQueue();  // 应该输出: 10 20 30
    
    // 测试查看队头
    cout << "队头元素：" << myQueue.peek() << endl;  // 应该输出: 10
    
    // 测试出队
    cout << "出队元素：" << myQueue.dequeue() << endl;  // 应该输出: 10
    myQueue.printQueue();  // 应该输出: 20 30
    
    // 测试队列大小
    cout << "队列大小：" << myQueue.size() << endl;  // 应该输出: 2
    
    return 0;
}

🔄 循环队列 vs 普通队列

上面的数组实现中，我们使用了"循环队列"的技巧，这是为什么呢？

🚦 普通队列的问题

如果我们不使用循环队列，当多次入队和出队后，会出现"假溢出"现象：

初始状态: [0,0,0,0,0]  front=0, rear=-1
入队10: [10,0,0,0,0]  front=0, rear=0
入队20: [10,20,0,0,0]  front=0, rear=1
出队:   [0,20,0,0,0]  front=1, rear=1
入队30: [0,20,30,0,0]  front=1, rear=2
出队:   [0,0,30,0,0]  front=2, rear=2

此时虽然数组还有空间，但rear已经到达数组末尾，无法继续入队，这就是"假溢出"。

🔄 循环队列的解决方案

循环队列将数组视为一个环，当rear到达数组末尾时，下一个位置回到数组开头：

rear = (rear + 1) % MAX_SIZE;  // 入队时
front = (front + 1) % MAX_SIZE;  // 出队时

这样就解决了"假溢出"问题，充分利用了数组空间。

📖 队列的应用场景

队列在实际编程中有非常广泛的应用：

1. 操作系统中的任务调度：操作系统使用队列来管理待执行的任务，按照"先来先服务"的原则处理任务。

2. 打印机任务队列：多个打印任务进入队列，按顺序打印。

3. 广度优先搜索(BFS)：在图论算法中，BFS算法使用队列来遍历图的节点。

4. 网络请求处理：服务器处理客户端的请求时，通常使用队列来管理请求。

5. 消息队列系统：在分布式系统中，消息队列用于解耦服务之间的通信。

🌈 实战练习：用队列解决问题

📝 问题：模拟打印机队列

问题描述： 有n个打印任务进入打印机队列，每个任务有一个优先级(1-10)，10为最高优先级。打印机每次从队列中取出一个任务：

• 如果队列中存在优先级更高的任务，则当前任务重新进入队列尾部
• 否则，打印当前任务

请计算每个任务的实际打印顺序。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;  // 任务数量
    cout << "请输入任务数量：";
    cin >> n;
    
    queue<pair<int, int>> taskQueue;  // 任务队列，存储(任务ID, 优先级)
    vector<int> priorities(n);  // 存储每个任务的优先级
    
    // 输入每个任务的优先级
    cout << "请输入每个任务的优先级(1-10)：" << endl;
    for (int i = 0; i < n; ++i) {
        cin >> priorities[i];
        taskQueue.push({i + 1, priorities[i]});  // 任务ID从1开始
    }
    
    int printOrder = 0;  // 打印顺序
    vector<int> result(n);  // 存储每个任务的打印顺序
    
    while (!taskQueue.empty()) {
        auto currentTask = taskQueue.front();
        taskQueue.pop();
        
        // 检查队列中是否有更高优先级的任务
        bool higherPriorityExists = false;
        for (auto task : taskQueue) {
            if (task.second > currentTask.second) {
                higherPriorityExists = true;
                break;
            }
        }
        
        if (higherPriorityExists) {
            // 有更高优先级的任务，当前任务重新入队
            taskQueue.push(currentTask);
        } else {
            // 没有更高优先级的任务，打印当前任务
            printOrder++;
            result[currentTask.first - 1] = printOrder;
            cout << "任务 " << currentTask.first << " 正在打印，打印顺序：" << printOrder << endl;
        }
    }
    
    // 输出每个任务的打印顺序
    cout << "\n每个任务的打印顺序：" << endl;
    for (int i = 0; i < n; ++i) {
        cout << "任务 " << (i + 1) << ": " << result[i] << endl;
    }
    
    return 0;
}

🧩 问题分析

这个问题很好地体现了队列的"先进先出"特性，同时结合了优先级的概念。程序的核心逻辑是：

1. 使用队列存储等待打印的任务
2. 每次取出队头任务，检查是否有更高优先级的任务
3. 如果有，当前任务重新入队
4. 否则，打印当前任务并记录顺序

💪 挑战自我：实现双端队列(Deque)

双端队列(Deque)是一种特殊的队列，它允许在队头和队尾都进行插入和删除操作。试着自己实现一个双端队列吧！

提示：双端队列的实现需要考虑：

• 在队头和队尾都能进行插入和删除
• 处理边界情况（空队列、满队列）
• 可以使用数组或链表实现

🌟 总结与加油

恭喜你完成了队列的学习！现在你已经掌握了：

1. 队列的基本概念和"先进先出"特性
2. C++中使用STL队列和自己实现队列的方法
3. 循环队列的原理和实现
4. 队列的实际应用场景
5. 用队列解决实际问题

编程学习就像队列一样，每一步的积累都会按顺序发挥作用。不要害怕遇到困难，每一次挑战都是成长的机会！继续加油，下一个数据结构在等着你呢～

📚 拓展学习

• 了解更多STL容器：deque（双端队列）、priority_queue（优先队列）
• 学习队列在图算法中的应用：广度优先搜索(BFS)
• 研究队列在操作系统中的具体实现
• 尝试用队列解决更多实际问题，比如银行排队系统模拟

相信自己，你一定可以在编程的道路上走得更远！🚀