数据结构与算法(九）-- 队列

                                                               队列

队列的定义：它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。

顺序队：采用顺序存储结构的队列，存储空间连续。           front指向对头元素

  rear 指向队尾元素的下一个位置

队列的定义

#define MaxSize 50
typedef strcut{
    ElemType data[MaxSize];    
    int front, int rear;    //队头指针、队尾指针
}SqQueue;

初始化：front = rear = 0  //队尾与对头指向一致

判空：Q.front == Q.rear;

求长度：Q.rear - Q.front

队满：（Q.rear+1）%QueueSize = front;   

循环队列：为了防止队列假溢出，将存储队列的顺序队列视为一个环，将rear指向循环位置

循环队列的操作：取余(%MaxSize)  将队尾后的元素整除最大个数，然后重新计数（继续从front开始）

循环队列是一个环，在末尾时要挪到下一个时候需要指定到初始位置，取余操作可以满足一个数一直加但最终结果一直在0和队列长度之间循环的要求

front指针移动：Q.front = (Q.front+1)%MaxSize;

rear指针移动： Q.rear = (Q.rear+1)%MaxSize;

队列长度： (Q.rear+MaxSize - Q.front)%MaxSize;

队满：(Q.rear+1)%MaxSize = front;

判空：Q.front = Q.rear;

为了防止队满与对空冲突，需要牺牲一个存储单元：Q.front == (Q.rear+1)%MaxSize;  //判断rear是否在front之前                           或者增加一个变量代表元素个数： Q.size == 0;  //对的大小为0         Q.size == MaxSize;  //队的大小为最大值，队满。                 

循环队列的基本操作：

void InitQueue(SqQueue &Q){    //初始化循环队列为空
    Q.rear == Q.front = 0;    //初始在对头位置
}

bool isEmpty(SqQueue Q){    //判空
    if(Q.rear == Q.front)
        return true;
    else return flase;
}

bool InsertQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize == Q.front){  //队满
        return false;
    }
    Q.data[Q.rear] = x;                 //x变量放在队尾
    Q.rear = (Q.rear+1)%MaxSize;        //移动指针，前移到队尾
}

bool Delete_Queue(SqQueue &Q, &x){    //出队操作（删除队头结点）
    if(Q.rear == Q.front)        //队空
        return false;
    x = Q.data[Q.rear];        //删除队头元素
    Q.front = (Q.front+1) % MaxSize;     //对头指针前移一位
    return true;
}    

队列的链式存储结构：链队

用带头结点队列，可以实现插入、删除、判空的统一（方便操作）

定义链队：

typedef struct{        //定义链式结构体
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front, *rear;    //定义队头指针与队尾指针
}

空链队形式：

链队的基本操作：

typedef InitQueue(LinkQueue &Q){
    Q.front = (LinkNode *) malloc (sizeof(LinkNode));    //动态分配结点内存
    Q.rear = Q.front;    //空队    
    Q.front->next = null;    //队头后继指向为空
}

判空操作：if(Q.front == Q.rear)        return true;
入队操作：

bool Insert_Queue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *) malloc (sizeof(LinkNode));    //分配一个新节点
    s->next = null;    //在队尾进行插入
    s->data = data;
    Q.rear->next = s; //队尾指针为新结点
    Q.rear = s;    //s为新队尾
}

出队操作：在对头进行删除

bool Delete_Queue(LinkQueue &Q, ElemType &x){
    if(Q.rear == Q.front){
        return false;
    }
    LinkNode *p = Q.front->next;      //指定为队头结点
    x = p->data;
    Q.rear->next = p->next;    //被删结点的后继转移为队头结点
    if(Q.rear == p){
        Q.rear = Q.front;        //修改为头结点
    }
    free(p);
    return true;
}