数据结构-队列

​ 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

​ 队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出线性表](https://blog.csdn.net/LWJLWJ_/article/details/125064006?spm=1001.2014.3001.5501)。

功能描述：循环队列的常用接口

构造函数：

• seqQueue(); //构造函数

大小操作：

• empty(); //判断循环队列是否为空
• full(); //判断循环队列是否已满
• size(); //返回循环队列的大小
• resize(); // 扩容

插入删除：

• pop(); //移除队首元素，并返回其值
• front(); //返回队首元素的值
  clear(); //清空

seqQueue.h

#pragma once
#include 
#include 

template 
class seqQueue
{
private:
    Type *data;     //维护数据指针
    int maxSize;    //队列容量
    int begin, end; //分别指向队头和队尾
public:
    seqQueue(int initSize = 100);                                  //构造函数
    ~seqQueue() { delete[] data; }                                 //析构函数
    bool empty() const { return begin == end; }                    //判空
    bool full() const { return (end + 1) % maxSize = begin; }      //判满
    void clear() { begin = end = -1; }                             //清空
    void push(const Type &value);                                  //入队
    int size() const { return (end - begin + maxSize) % maxSize; } //返回元素个数
    void resize();                                                 //用于重新定义队列容量
    Type pop();                                                    //出队
    Type front() const;                                            //取队首
};

template 
seqQueue::seqQueue(int initSize) //构造函数
{
    if (initSize <= 0)
    {
        std::cout << "badSize!" << std::endl; //队列容量有误
        assert(initSize > 0);
    }
    data = new Type[initSize];
    maxSize = initSize;
    begin = end = -1;
}

template 
void seqQueue::push(const Type &x) //入队
{
    if ((end + 1) % maxSize == begin)
    {
        resize();
    }
    end = (end + 1) % maxSize;
    data[end] = x;
}

template 
Type seqQueue::pop() //出队
{
    if (empty())
    {
        std::cout << "outOfRange!" << std::endl;
        assert(!empty());
    }
    begin = (begin + 1) % maxSize;
    return data[begin];
}

template 
Type seqQueue::front() const //返回对首元素
{
    if (empty())
    {
        std::cout << "outOfRange!" << std::endl;
        assert(!empty());
    }
    return data[(begin + 1) % maxSize];
}

template 
void seqQueue::resize() //扩大容量
{
    Type *tmp = data;
    data = new Type[2 * maxSize];
    for (int i = 1; i < maxSize; ++i)
    {
        data[i] = tmp[(begin + i) % maxSize];
    }
    begin = 0;
    end = maxSize - 1;
    maxSize = 2 * maxSize;
    delete tmp;
}

main.cpp

#include 
using namespace std;
#include "seqQueue.h"

void testQueue(seqQueue &p)
{
    cout << "插入和取出测试：" << endl;
    for (int i = 0; i < 4; i++)
    {
        p.push(i);
    }
    cout << "队列大小为：" << p.size() << endl;
    // while (!p.empty())
    // {
    //     cout << p.pop() << " ";
    // }
    cout << endl;
    cout << "队首值为：" << p.front() << endl;
}

int main()
{
    seqQueue s1;
    testQueue(s1);
    return 0;
}

功能描述：链队列的常用接口

构造函数：

• listQueue(); //构造函数

大小操作：

• empty(); //判断链队列是否为空
• full(); //判断链队列是否已满
• size(); //返回链队列的大小
• resize(); // 扩容

插入删除：

• pop(); //移除队首元素，并返回其值
• front(); //返回队首元素的值
• clear(); //清空

linkQueue.h

#pragma once
#include 
#include 

template 
class linkQueue
{
private:
    struct node
    {
        Type data;  //数据域
        node *next; //指针域
        node(const Type &value, node *p = nullptr)
        {
            this->data = value;
            this->next = p;
        }
        node() : next(nullptr) {}
        ~node(){};
    };
    node *begin, *end; //分别为队首指针和队尾指针
public:
    linkQueue() { begin = end = nullptr; }          //构造函数
    ~linkQueue();                                //析构函数
    bool empty() const { return begin == nullptr; } //判空
    void clear();                                //清空
    int size() const;                            //返回链队列大小
    void push(const Type &value);                //入队
    Type pop();                                  //出队
    Type front() const;                          //读队头元素，并返回它的值
};

template 
linkQueue::~linkQueue() //析构函数
{
    node *p;
    while (begin)
    {
        p = begin;
        begin = begin->next;
        delete p;
    }
}
template 
void linkQueue::clear() //清空
{
    node *p;
    while (begin)
    {
        p = begin;
        begin = begin->next;
        delete p;
    }
    end = nullptr;
}

template 
int linkQueue::size() const //返回链队列大小
{
    node *p;
    p = begin;
    int num = 0;
    while (p)
    {
        num++;
        p = p->next;
    }
    return num;
}

template 
void linkQueue::push(const Type &value) //入队
{
    if (empty())
    {
        begin = end = new node(value);
    }
    else
    {
        end->next = new node(value);
        end = end->next;
    }
}

template 
Type linkQueue::pop() //出队并返回其值
{
    if (empty())
    {
        std::cout << "outOfRange!" << std::endl;
        assert(!empty());
    }
    node *p;
    p = begin;
    Type value = begin->data;
    begin = begin->next;
    if (empty())
    {
        end = nullptr;
    }
    delete p;
    return value;
}

template 
Type linkQueue::front() const //读队头元素，并返回它的值
{
    if (empty())
    {
        std::cout << "outOfRange!" << std::endl;
        assert(!empty());
    }
    return begin->data;
}

main.cpp

#include 
using namespace std;
#include "linkQueue.h"

void testQueue(linkQueue &p)
{
    cout << "插入和取出测试：" << endl;
    for (int i = 0; i < 4; i++)
    {
        p.push(i);
    }
    cout << "队列大小为：" << p.size() << endl;
    // while (!p.empty())
    // {
    //     cout << p.pop() << " ";
    // }
    cout << endl;
    cout << "队首值为：" << p.front() << endl;  
}

int main()
{
    linkQueue s1;
    testQueue(s1);
    return 0;
}

循环队列能很好地避免数据溢出的问题，而循环队列则不存在数据溢出的问题，因为它是动态开辟空间的。