数据结构基础--顺序队列（假溢出和循环队列）

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列图解

队列的表示和操作，元素的出队和入队要符合先进先出，后进后出的原则
空队列，当Q.rear == Q.front时候表示为空队列
入队指的是元素从队列的对尾进入队列的，比如c1,c2,c3的入队
出队指的是元素从队列的队头出队，比如从c1,c2相继出队

队列的表示与操作实现

队列假溢出问题
如上图所示如果出队的数量大于入队的数量就会造成队列的假溢出，比如c4,c5,c6入队，c3,c4出队的情况下依据判断堆满的条件，队已经满了，但实际上根本没有满就是假溢出。为了解决这个问题，我们将队列原本的一个空间置为空，然后我们可以使用逻辑来将队列形成一个环，这个使我们最常见的解决方案。

循环队列中头尾指针与元素之间的关系

循环队列

循环队列操作图解

总结：

判断堆满条件：Q.rear== Q.front
判断队满的条件：(Q.rear + 1) %MAXSIZE == Q.front
设计一个队列，定义一个结构体，使用数组开辟一段连续的空间来存储数据内容

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

/* 循环队列的顺序存储结构 */
typedef struct
{
    QElemType data[MAXSIZE];
    int front;        /* 头指针 */
    int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;

初始化一个空队列Q

Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

将队列清空：只需要将Q->front和Q->rear置为0即可

Status ClearQueue(SqQueue *Q){
    
    Q->front = Q->rear = 0;
    return OK;
}

判断一个队列是否为空，若队列Q为空队列,则返回TRUR,否则返回FALSE;

Status QueueEmpty(SqQueue Q){
    //队空标记
    if (Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}

获取队列的长度：返回Q的元素个数,也就是队列的当前长度

int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}

获取队头元素：若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR

Status GetHead(SqQueue Q,QElemType *e){
    //队列已空
    if (Q.front == Q.rear)
        return ERROR;
    
    *e = Q.data[Q.front];
    return OK;
    
}

入队：若队列未满,则插入元素e为新队尾元素

Status EnQueue(SqQueue *Q,QElemType e){
    
    //队列已满
    if((Q->rear+1)%MAXSIZE == Q->front)
        return ERROR;
    
    //将元素e赋值给队尾
    Q->data[Q->rear] = e;
    
    //rear指针向后移动一位,若到最后则转到数组头部;
    Q->rear = (Q->rear+1)%MAXSIZE;
    
    return OK;

出队：若队列不空,则删除Q中队头的元素,用e返回值

Status DeQueue(SqQueue *Q,QElemType *e){
   
    //判断队列是否为空
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    //将队头元素赋值给e
    *e = Q->data[Q->front];
    
    //front 指针向后移动一位,若到最后则转到数组头部
    Q->front = (Q->front+1)%MAXSIZE;
    
    return OK;
}

遍历队列：从队头到队尾依次对队列的每个元素数组

Status QueueTraverse(SqQueue Q){
    int i;
    i = Q.front;
    while ((i+Q.front) != Q.rear) {
        printf("%d   ",Q.data[i]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}

最后编辑于：2020.06.18 08:44:56