顺序队列Queue——数据结构系列教程(c++版)

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

#endif // ENTITYS_H_INCLUDED
        

ArrayQueue.h 头文件

#ifndef ARRAYQUEUE_H_INCLUDED
#define ARRAYQUEUE_H_INCLUDED

#include "Entitys.h"

//************************************************************************************************************************************************************************
//
//      类名：数组队列(ArrayQueue)
//
//      概述：一个可复用的数组队列，存储结构采用数组实现，支持任意类型数据（模板泛型）。
//
//      说明：默认队列的最大容量为100，入队出队时间复杂度为O(1)
//
//************************************************************************************************************************************************************************

#define MAXSIZE 100  // 队列的最大容量


//========================================================================================================================================================================
//
//                                                                 数组队列结构体(ArrayQueue)
//
//========================================================================================================================================================================
template <typename T>
struct ArrayQueue{
    // ------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        T data[MAXSIZE];   // 存储数据，可存储字符或整数
        int head;        // 队列头，初始为-1表示空栈
        int tail;        // 队列尾，初始为-1表示空栈
        int qty;         // 用于跟踪队列中的元素数量

        //---------------声明私有成员函数---------------

    // ------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        ArrayQueue() {
            head = 0; tail = 0; qty = 0;
            for(int i=0;i < MAXSIZE;i++) { data[i] = T(); }
        }

        int isEmpty();// 判断队列是否为空
        int isFull();// 判断队列是否已满
        void enQueue(const T& value);// 入队操作（在队列尾入队）
        T deQueue();// 出队操作（返回队列头元素，队列空返回-1）
        T getHead();// 获取队列头元素（不弹出，队列空返回-1）
        T getTail();// 获取队列尾元素（不弹出，队列空返回-1）
        int getSize();// 获取队列大小
        void print();// 打印队列数据
        void destroyQueue();// 销毁整个队列（防止内存泄漏）

        // 析构函数：自动销毁队列，避免内存泄漏
        ~ArrayQueue() {
        }
};

#endif // ARRAYQUEUE_H_INCLUDED
                
                

ArrayQueue.cpp 程序代码

#include <iostream>
#include"ArrayQueue.h"

//**********************实现公有成员函数**********************

// 判断队列是否为空
template <typename T>
int ArrayQueue<T>::isEmpty()
{
    return qty == 0;
}

// 判断队列是否已满
template <typename T>
int ArrayQueue<T>::isFull()
{
    return qty == MAXSIZE;
}

// 入队操作（在队列尾入队）
template <typename T>
void ArrayQueue<T>::enQueue(const T& value)
{
    if (isFull())
    {
        printf("队列已满！无法入队。\n");
        return;
    }

    data[tail] = value;
    tail = (tail + 1) % MAXSIZE; //实现循环队列
    qty++;
}

// 出队操作（返回队列头元素）
template <typename T>
T ArrayQueue<T>::deQueue()
{
    if(isEmpty())
    {
        printf("队列为空，无法出队。\n");
        return T();
    }

    T value =data[head];
    data[head] = T(); // 可选：清空出队的位置
    head = (head + 1) % MAXSIZE;
    qty--;
    return value;
}

// 获取队列头元素（不弹出）
template <typename T>
T ArrayQueue<T>::getHead()
{
    if (isEmpty()) {
        return T();
    }
    return data[head];
}

// 获取队列尾元素（不弹出）
template <typename T>
T ArrayQueue<T>::getTail()
{
    if (isEmpty()) {
        return T();
    }
    int index = (tail - 1 + MAXSIZE) % MAXSIZE;// 计算队尾元素的真实下标（适配循环队列）
    return data[index];
}

// 获取队列大小
template template <typename T>
int ArrayQueue<T>::getSize()
{
    return qty;
}

// 打印队列数据（仅遍历有效元素，不修改任何指针）
template <typename T>
void ArrayQueue<T>::print()
{
    if (isEmpty()) {
        printf("队列内容：空\n");
        return;
    }

    printf("队列内容：");
    // 遍历队列中实际存在的 qty 个元素
    for (int i = 0; i < qty; i++) {
        // 计算第i个有效元素的索引（适配循环队列）
        int index = (head + i) % MAXSIZE;
        printf("%d ", data[index]);
    }
    printf("\n");
    // 可选：打印队列状态（便于调试）
    printf("队列状态：头指针=%d，尾指针=%d，元素数量=%d\n", head, tail, qty);
}         

// 显式实例化常用类型（避免链接错误，可选）
template class ArrayQueue<int>;
template class ArrayQueue<char>;
template class ArrayQueue<float>;
template class ArrayQueue<std::string>;
template class ArrayQueue<Student>; // 新增：显式实例化Student类型
template class ArrayQueue<Pos>; // 新增：显式实例化Pos类型
template class ArrayQueue<PrintTask>; // 新增：显式实例化PrintTask类型

main.cpp 测试代码

#include "ArrayQueue.h"
#include <iostream>
#include <string>

int main() {
    ArrayQueue<int> queues;

    // 1. 入队测试
    printf("\n=== 入队测试 ===\n");
    queues.enQueue(1);
    queues.enQueue(2);
    queues.enQueue(3);
    queues.enQueue(4);
    queues.enQueue(5);
    printf("入队1、2、3、4、5后：\n");
    queues.print();

    // 2. 出队测试
    printf("\n=== 出队测试 ===\n");
    printf("出队3次：");
    printf("%d ",queues.deQueue());
    printf("%d ",queues.deQueue());
    printf("%d \n",queues.deQueue());
    printf("出队后");
    queues.print();
    
    return 0;
}

输出结果

=== 入队测试 ===
入队1、2、3、4、5后：
队列内容：1 2 3 4 5
队列状态：头指针=0，尾指针=5，元素数量=5

=== 出队测试 ===
出队3次：1 2 3
出队后队列内容：4 5
队列状态：头指针=3，尾指针=5，元素数量=2
    

六、注意事项

七、应用场景

• 层级 / 顺序处理的场景：二叉树层序遍历、图的 BFS、任务排队 → 队列保证按顺序处理；
• 最短路径 / 最少步数校验的场景：迷宫最短路径、无权图最短路径 → BFS 的层级特性天然适配最短路
• 循环 / 绕圈的场景：约瑟夫环、滑动窗口 → 队列的循环特性模拟绕圈。

八、总结

• 队列是 先进先出（FIFO）的线性数据结构，仅允许在队尾入队、队头出队，具有操作限制性；
• 按实现方式分为顺序队列（数组）和链式队列（链表），按功能扩展分为循环队列、双端队列、优先级队列等，其中循环队列解决了普通顺序队列的空间浪费问题；
• 核心操作的时间复杂度均为 O (1)，顺序队列优势在于高效访问，链式队列优势在于动态扩容；
• 广泛应用于任务调度、异步处理、BFS 算法、消息队列等场景，是计算机科学中不可或缺的基础数据结构；
• 与栈的核心区别在于进出规则，队列是 “先进先出”（双端操作），栈是 “先进后出”（单端操作）。

本教程通过代码解析和实战示例，覆盖了队列的核心原理、关键操作实现和实际使用场景。队列作为基础数据结构，在缓存机制、任务调度、消息队列等场景中有着广泛应用，掌握数组队列的实现，是深入学习更复杂数据结构（如优先级队列）的重要基础。