队列

队列，和栈一样，队列也是一种特殊的线性表结构，只不过队列是在一端插入，另一端删除，就跟我们平常排队一样的道理，从队尾入队，在队头出去，所以队列的特性是先入先出（FIFO），允许插入的一端叫队尾，允许删除的一端叫队头。
一张图可以形象的体现两者的差别：

和栈一样，队列也可以通过数组和链表实现，通过数组实现的叫顺序队列，通过链表实现的叫做链式队列，栈只需要一个栈顶指针就可以了，因为只允许在栈顶插入删除，但是队列需要两个指针，一个指向队头，一个指向队尾。我们先看看 C++ 简单顺序队列的实现：

Queue.hpp

#include <iostream>
using namespace std;

template<class T> class Queue{
public:
    Queue();
    ~Queue();

    void add(T t);
    T front();
    T pop();
    int size();
    int is_empty();

private:
    T *arr;
    int count;
};

// 创建“队列”，默认大小是12
template<class T>
Queue<T>::Queue()
{
    arr = new T[12];
    if (!arr)
    {
        cout<<"arr malloc error!"<<endl;
    }
}

// 销毁“队列”
template<class T>
Queue<T>::~Queue()
{
    if (arr)
    {
        delete[] arr;
        arr = NULL;
    }
}

// 将val添加到队列的末尾
template<class T>
void Queue<T>::add(T t)
{
    arr[count++] = t;
}


// 返回“队列开头元素”
template<class T>
T Queue<T>::front()
{
    return arr[0];
}

// 返回并删除“队列末尾的元素”
template<class T>
T Queue<T>::pop()
{
    int i = 0;;
    T ret = arr[0];

    count--;
    while (i++<count)
        arr[i-1] = arr[i];

    return ret;
}

// 返回“队列”的大小
template<class T>
int Queue<T>::size()
{
    return count;
}

// 返回“队列”是否为空
template<class T>
int Queue<T>::is_empty()
{
    return count==0;
}

main.cpp

#include <iostream>

#include "queue.hpp"

int main() {
    int tmp=0;
    Queue<int> *astack = new Queue<int>();

    // 将10, 20, 30 依次推入队列中
    astack->add(10);
    astack->add(20);
    astack->add(30);

    // 将“队列开头元素”赋值给tmp，并删除“该元素”
    tmp = astack->pop();
    cout<<"tmp="<<tmp<<endl;

    // 只将“队列开头的元素”赋值给tmp，不删除该元素.
    tmp = astack->front();
    cout<<"tmp="<<tmp<<endl;

    astack->add(40);

    cout<<"is_empty()="<<astack->is_empty()<<endl;
    cout<<"size()="<<astack->size()<<endl;
    while (!astack->is_empty())
    {
        tmp = astack->pop();
        cout<<tmp<<endl;
    }

    return 0;
}

通过数组实现的顺序队列有一个问题，就是随着队列元素的插入和删除，队尾指针和队头指针不断后移，而导致队尾指针指向末尾无法插入数据，这时候有可能队列头部还是有剩余空间的，如下图所示：

我们当然可以通过数据搬移的方式把所有队列数据往前移，但这会增加额外的时间复杂度，如果频繁操作数据量很大的队列，显然对性能有严重损耗，对此问题的解决方案是循环队列，即把队列头尾连起来：

这样一来就不会出现之前的问题了，此时判断队列是否为空的条件还是 tail==head，但是判断队列是否满的条件就变成了 (tail+1) % maxsize == head，maxsize 是数组的长度，浪费一个空间是为了避免混淆判断空队列的条件。当然如果通过链表来实现队列的话，显然没有这类问题，因为链表没有空间限制。

队列的应用也非常广泛，比如我们常见的消息队列就是队列的典型应用场景。

队列

评论区