侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

队列

kaixindeken
2021-04-18 / 0 评论 / 0 点赞 / 66 阅读 / 2,316 字

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

1.png

和栈一样,队列也可以通过数组和链表实现,通过数组实现的叫顺序队列,通过链表实现的叫做链式队列,栈只需要一个栈顶指针就可以了,因为只允许在栈顶插入删除,但是队列需要两个指针,一个指向队头,一个指向队尾。我们先看看 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;
}

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

1.png

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

1.png

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

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

0

评论区