目录

概念篇

队列的概念

入队

出队

获取队首元素

代码篇

顺序表实现

队列类的声明

队列的扩容

队列的销毁

入队

出队

获取队首元素

获取元素数量

队列的完整源码

链表实现

队列类的声明

队列的扩容

队列的销毁

入队

出队

获取队首元素

获取元素数量

队列的完整源码

概念篇

队列的概念

队列仅限在表尾插入，表头删除，遵循先进先出的原则

入队

将元素从队尾进行插入

第一步，将元素添加到队尾，更新队尾指针（链表）或索引（顺序表）

第二步，队列大小+1

出队

将队首元素删除

第一步，删除队首元素，更新队首指针（链表）或索引（顺序表）

第二步，队列的大小-1

获取队首元素

返回队首指针（或索引）指向的元素

第一步，利用队首指针（或索引）获取队首元素并返回

代码篇

顺序表实现

队列类的声明

#include <iostream>
#include <stdexcept>
using namespace std;
// 模板声明，表明Queue类是一个通用的模板类，可以用于存储任何类型的元素
template <typename T>
// 队列的数据结构
class Queue
{
private:
    // 存储队列中的元素
    T *data;
    // 队首索引
    int front;
    // 队尾索引
    int rear;
    // 队列容量
    int capacity;
    // 用于在队列容量不足时扩容
    void resize();

public:
    // 构造函数，初始化队列成员变量
    Queue() : data(new T[10]), front(0), rear(0), capacity(10) {}
    // 析构函数，用于释放队列所占用的内存
    ~Queue();
    // 入队
    void enqueue(T element);
    // 出队
    T dequeue();
    // 获取队首元素
    T getFront() const;
    // 获取元素数量
    int getSize() const;
};

队列的扩容

// 队列的扩容
template <typename T>
void Queue<T>::resize()
{
    // 新容量是原容量的2倍
    T *newData = new T[capacity * 2];
    // 将原数组的元素放入新数组中
    for (int i = 0; i < rear; i++)
    {
        newData[i] = data[i];
    }
    // 释放原数组的内存
    delete[] data;
    // 更新新数组为队列新的存储数组
    data = newData;
    // 更新队列的容量
    capacity *= 2;
}

队列的销毁

// 队列的销毁
template <typename T>
Queue<T>::~Queue()
{
    // 释放data的内存
    delete[] data;
}

入队

// 入队
template <typename T>
void Queue<T>::enqueue(T element)
{
    // 容量不足时进行扩容
    if (rear == capacity)
    {
        resize();
    }
    // 将元素赋值给队尾上rear的位置，并将元素数量+1
    data[rear++] = element;
}

出队

// 出队
template <typename T>
T Queue<T>::dequeue()
{
    // 若队列为空则抛出异常
    if (front == rear)
    {
        throw std::underflow_error("Queue is empty");
    }
    // 若队列不为空则返回队首元素，并将队首元素移除
    return data[front++];
}

获取队首元素

// 获取队首元素
template <typename T>
T Queue<T>::getFront() const
{
    // 若队列为空则抛出异常
    if (front == rear)
    {
        throw std::underflow_error("Queue is empty");
    }
    // 若队列不为空则返回front索引的位置
    return data[front];
}

获取元素数量

// 获取元素数量
template <typename T>
int Queue<T>::getSize() const
{
    return rear - front;
}

队列的完整源码

#include <iostream>
#include <stdexcept>
using namespace std;
// 模板声明，表明Queue类是一个通用的模板类，可以用于存储任何类型的元素
template <typename T>
// 队列的数据结构
class Queue
{
private:
    // 存储队列中的元素
    T *data;
    // 队首索引
    int front;
    // 队尾索引
    int rear;
    // 队列容量
    int capacity;
    // 用于在队列容量不足时扩容
    void resize();

public:
    // 构造函数，初始化队列成员变量
    Queue() : data(new T[10]), front(0), rear(0), capacity(10) {}
    // 析构函数，用于释放队列所占用的内存
    ~Queue();
    // 入队
    void enqueue(T element);
    // 出队
    T dequeue();
    // 获取队首元素
    T getFront() const;
    // 获取元素数量
    int getSize() const;
};
// 队列的扩容
template <typename T>
void Queue<T>::resize()
{
    // 新容量是原容量的2倍
    T *newData = new T[capacity * 2];
    // 将原数组的元素放入新数组中
    for (int i = 0; i < rear; i++)
    {
        newData[i] = data[i];
    }
    // 释放原数组的内存
    delete[] data;
    // 更新新数组为队列新的存储数组
    data = newData;
    // 更新队列的容量
    capacity *= 2;
}
// 队列的销毁
template <typename T>
Queue<T>::~Queue()
{
    // 释放data的内存
    delete[] data;
}
// 入队
template <typename T>
void Queue<T>::enqueue(T element)
{
    // 容量不足时进行扩容
    if (rear == capacity)
    {
        resize();
    }
    // 将元素赋值给队尾上rear的位置，并将元素数量+1
    data[rear++] = element;
}
// 出队
template <typename T>
T Queue<T>::dequeue()
{
    // 若队列为空则抛出异常
    if (front == rear)
    {
        throw std::underflow_error("Queue is empty");
    }
    // 若队列不为空则返回队首元素，并将队首元素移除
    return data[front++];
}
// 获取队首元素
template <typename T>
T Queue<T>::getFront() const
{
    // 若队列为空则抛出异常
    if (front == rear)
    {
        throw std::underflow_error("Queue is empty");
    }
    // 若队列不为空则返回front索引的位置
    return data[front];
}
// 获取元素数量
template <typename T>
int Queue<T>::getSize() const
{
    return rear - front;
}
int main()
{
    Queue<int> q;
    q.enqueue(3);
    q.enqueue(4);
    cout << q.getFront() << endl;
    q.enqueue(5);
    cout << q.getFront() << endl;
    q.dequeue();
    cout << q.getFront() << endl;
    cout << q.getSize() << endl;
    return 0;
}

链表实现

队列类的声明

#include <iostream>
#include <stdexcept>
using namespace std;
template <typename T>
class Queue
{
private:
    // 结构体定义，表示队列中的节点
    struct Node
    {
        T data;
        Node *next;
        Node(T d) : data(d), next(NULL) {}
    };
    // 队首节点指针
    Node *front;
    // 队尾节点指针
    Node *rear;
    // 元素个数
    int size;

public:
    // 构造函数，初始化队列
    Queue() : front(NULL), rear(NULL), size(0) {}
    // 析构函数，释放内存
    ~Queue();
    // 入队
    void enqueue(T element);
    // 出队
    T dequeue();
    // 获取队首元素
    T getFront() const;
    // 获取队列大小
    int getSize() const;
};

队列的扩容

无

队列的销毁

// 队列的销毁
template <typename T>
Queue<T>::~Queue()
{
    // 不断访问队列中的队首元素，并删除队首，直到队列为空
    while (front)
    {
        Node *temp = front;
        front = front->next;
        // 释放内存
        delete temp;
    }
}

入队

// 入队
template <typename T>
void Queue<T>::enqueue(T element)
{
    // 若队列为空则创建一个新的节点
    if (rear == NULL)
    {
        rear = new Node(element);
        front = rear;
    }
    // 若队列不为空则将新的节点插入到队列的末尾，将队尾指针指向新节点的next指针
    else
    {
        rear->next = new Node(element);
        rear = rear->next;
    }
    // 增加队列大小
    size++;
}

出队

// 出队
template <typename T>
T Queue<T>::dequeue()
{
    // 若队列为空则抛出异常
    if (front == NULL)
    {
        throw std::underflow_error("Queue is empty");
    }
    // 将队首元素赋值给element，准备返回队首元素
    T element = front->data;
    // 将队首的指针赋值给temp，准备删除节点
    Node *temp = front;
    // 删除队首节点
    front = front->next;
    // 释放内存
    delete temp;
    // 大小-1
    size--;
    // 若删除后队列为空，则将rear指针置为NULL
    if (size == 0)
    {
        rear = NULL;
    }
    // 返回队首元素
    return element;
}

获取队首元素

// 获取队首元素
template <typename T>
T Queue<T>::getFront() const
{
    // 若队列为空则抛出异常
    if (front == NULL)
    {
        throw std::underflow_error("Queue is empty");
    }
    return front->data;
}

获取元素数量

// 获取元素数量
template <typename T>
int Queue<T>::getSize() const
{
    return size;
}

队列的完整源码

#include <iostream>
#include <stdexcept>
using namespace std;
template <typename T>
class Queue
{
private:
    // 结构体定义，表示队列中的节点
    struct Node
    {
        T data;
        Node *next;
        Node(T d) : data(d), next(NULL) {}
    };
    // 队首节点指针
    Node *front;
    // 队尾节点指针
    Node *rear;
    // 元素个数
    int size;

public:
    // 构造函数，初始化队列
    Queue() : front(NULL), rear(NULL), size(0) {}
    // 析构函数，释放内存
    ~Queue();
    // 入队
    void enqueue(T element);
    // 出队
    T dequeue();
    // 获取队首元素
    T getFront() const;
    // 获取队列大小
    int getSize() const;
};
// 队列的销毁
template <typename T>
Queue<T>::~Queue()
{
    // 不断访问队列中的队首元素，并删除队首，直到队列为空
    while (front)
    {
        Node *temp = front;
        front = front->next;
        // 释放内存
        delete temp;
    }
}
// 入队
template <typename T>
void Queue<T>::enqueue(T element)
{
    // 若队列为空则创建一个新的节点
    if (rear == NULL)
    {
        rear = new Node(element);
        front = rear;
    }
    // 若队列不为空则将新的节点插入到队列的末尾，将队尾指针指向新节点的next指针
    else
    {
        rear->next = new Node(element);
        rear = rear->next;
    }
    // 增加队列大小
    size++;
}
// 出队
template <typename T>
T Queue<T>::dequeue()
{
    // 若队列为空则抛出异常
    if (front == NULL)
    {
        throw std::underflow_error("Queue is empty");
    }
    // 将队首元素赋值给element，准备返回队首元素
    T element = front->data;
    // 将队首的指针赋值给temp，准备删除节点
    Node *temp = front;
    // 删除队首节点
    front = front->next;
    // 释放内存
    delete temp;
    // 大小-1
    size--;
    // 若删除后队列为空，则将rear指针置为NULL
    if (size == 0)
    {
        rear = NULL;
    }
    // 返回队首元素
    return element;
}
// 获取队首元素
template <typename T>
T Queue<T>::getFront() const
{
    // 若队列为空则抛出异常
    if (front == NULL)
    {
        throw std::underflow_error("Queue is empty");
    }
    return front->data;
}
// 获取元素数量
template <typename T>
int Queue<T>::getSize() const
{
    return size;
}
int main()
{
    Queue<int> q;
    q.enqueue(3);
    q.enqueue(4);
    cout << q.getFront() << endl;
    q.enqueue(5);
    cout << q.getFront() << endl;
    q.dequeue();
    cout << q.getFront() << endl;
    cout << q.getSize() << endl;
    return 0;
}

# 数据结构
Logo
乐奇 Rokid 开放社区

更多推荐

cover

让界面替我“摇“一次：一个AR祈愿智能体的AIUI实践

avatar 乐奇 Rokid 开放社区
cover

AR 智能眼镜并不是简单地在眼前放一块屏幕，而是把**摄像头、传感器、计算机视觉、空间定位、语音交互和云端服务**连接起来

avatar 乐奇 Rokid 开放社区

智能眼镜市场全景解析：从技术演进到产业格局

本文系统梳理智能眼镜市场，涵盖产品形态、技术演进、市场规模、产业链结构及竞争格局。指出智能眼镜正从音频交互向AR显示与空间计算演进，受AI大模型、供应链成熟与生态延伸驱动，呈现分层发展态势。虽面临场景刚需不足、续航重量矛盾与隐私挑战，但B端应用先行、AI原生设计与标准完善将推动行业迈向规模化渗透，未来需关注核心技术突破与真实使用数据。

avatar 乐奇 Rokid 开放社区