赞
踩
队列的概念比较好理解,和我们现实中的排队比较相似,先进先出。栈和队列有点相似,栈有入栈出栈两种基本操作,队列相对应也有入队出队两种基本操作,不过栈只能从栈顶入,从栈顶出;而队列从队尾入,从队头出,所以队列也是一种操作受限的线性表。
和栈一样,用数组实现的队列叫顺序队列,用链表实现的队列叫链式队列。
前面说了,队列从队尾入,从队头出,因此我们需要维护队头head和队尾tail,顺序队列的入队和出队的代码大致是:
template<typename T> void enqueue(T data){ if(tail==capacity) //队列已经满了,无法再入队 throw "queue is full"; array[tail]=data; ++tail; } template<typename T> T dequeue(){ if(head==tail) //队列已经空了,无法出队 throw "queue is empty\n"; T ret=array[head]; ++head; return ret; }
这样子会有一个问题:head和tail都是不断变大的,随着若干次入队和出队,tail达到了数组的尾端也就是tail==capacity,而head可能在数组的中间位置,这时候队列的元素在[head,tail]上,数组[0,head)的空间却闲置了,但是此时无法入队。
针对这个问题,我们可以在入队时当tail==capacity时也判断head!=0,都成立的话做一次数据的前移,将[head,tail]上的元素移到[0,tail-head]上,就可以将空间腾出来,这里就不展示完整代码了。
链式队列的话就不需要考虑移数据或者动态扩容的问题,同样也是维护head和tail指针,入队出队的伪代码:
template<typename T>
void enqueue(T data){
if(tail == nullptr)
tail = new Node(data);
else
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。