数据结构之——队列

第一话：基础知识

资料【来自维基百科】：

译：在计算机科学中，队列是一种特别的抽象数据类型或者集合，其中集合中的实体保持顺序并且排列到实体的终端位置，成为入队，从实体的前方位置取出，成为出队。队列存储方式是FIFO(即先进先出数据类型)。第一个入队的会第一个出队删除，这相当于一旦一个元素被添加进来的时候，之前被入队的元素都可以被一处，队列是一个线性数据类型，或者说是更抽象的顺序集合例子。

图例【来自维基百科】：

两种方式：Enqueue(入队)  Dequeue(出队)。

注：队列是特殊的线性表，只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行表尾进行插入，进行插入操作的端是队尾，进行删除操作的端称作队头，队中没有元素时，称为空队列。

第二话：常用接口

以上也包括了出队的一个操作类，这里没有提及到，所以也可以去掉。

• 队列接口

empty(); 测试容器是否为空

size();返回队列的大小

front();表的前端

rear();表的后端

back();最后一个元素

push();插入元素

pop();弹出元素

swap();交换内容

因为队列的实现方式和栈很相像，所以在接口的实现方面也有很多相通的地方。

这里有个小细节需要注意：

队列空的条件： front = rear

队列满的条件： rear = MAXSIZE

队列的rear和front位置大致就是如图所示，结合图示和基本的接口，可以完成完成顺序队中队列的一些基本运算。其实还有环形的队列方式，这个在讲完基本的顺序队的实现之后再说。

• 基本操作

1.initqueue();

2.empty();

3.enqueue();

4.dequeue();

用定义顺序队列的类型Queue

typedef struct{
   ElemType data [MaxSize];
   int front,rear;
}Queue;

1.初始化队列

void initqueue(Queue * &q){
   q = new Queue;
   q->front = q->rear = -1 ; //初始rear 和 front的值都指向-1
}

2.销毁队列

void DestroyQueue(Queue * &q){
  delete[q];
}

3.判断队列是否为空

bool empty(Queue * q){
    return (q->front == q->rear);
}

这里很巧妙地直接用到了front是否相等与rear来判断队列是否为空

4.入队操作

bool enqueue(Queue *&q,ElemType &e){
    if(q->rear == MaxSize-1)//防止上溢
    	return false;
    else
        q->rear++;
        q->data[q->rear] = e;
        return true;
}

5.出队操作

bool dequeue(Queue *&q,ElemType & e){
    if(q->rear == q->front)//为空
    	return false;
    else
        q->front++;
        e = q->data[q->front];
        return true;
}

在出队和入队的时候，front和rear都做了相应的加，往后移动一位，但是不同的是入队时将e赋值给新的rear++ 而 出队的时候是将front++赋值给e 更新e的值，删除先前的e 。

第三话：环形队列

找基本概念的时候发现Quara上面有人问 ，就拷过来了（From：Rashmi Shankar, Student）

解决再缓冲的问题，提出了环形结构的队列形式，把rear和front连接起来。

实质上，这只是在计算队列个数方面发生了改变。

基本模型：

因为rear-MaxSize == 0 时是队伍满的成立条件，所以可以用求余的运算条件来算

出队：front=(front+1)%MaxSize

入队：rear=(rear +1)%MaxSize

所以在实现过程只是和线性表不同的是求front和rear 的方式而已

环形中

判断上溢条件： if(q->rear+1) %MaxSize== q->front)

判断下溢条件： if(q->rear == q->front)