队列,和栈一样,队列也是一种特殊的线性表结构,只不过队列是在一端插入,另一端删除,就跟我们平常排队一样的道理,从队尾入队,在队头出去,所以队列的特性是先入先出(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 是数组的长度,浪费一个空间是为了避免混淆判断空队列的条件。当然如果通过链表来实现队列的话,显然没有这类问题,因为链表没有空间限制。
队列的应用也非常广泛,比如我们常见的消息队列就是队列的典型应用场景。
评论区