数据结构之队列的实现

队列的简介

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

队列的结构特性不像栈一样，只对栈顶进行入栈，出栈，获取栈的长度；队列的结构是在后端进行入队，前端进行出队，在判断队列的长度时，还要考虑队溢出问题。

截屏2020-04-14上午10.46.10.png

通过上面的一张图，可以了解到入队和出队的原理，从对尾（rear）入队
从队头（front）出队。从这张图可以看出，判断队空的情况是q.front=q.rear。

截屏2020-04-14上午11.07.37.png

从这张图的队满情况可以看出，判断队满的条件好像也是q.front=q.rear，和判断队空的条件一样，因此，我们需要让队尾指向一个空，把这个空荡成判断的条件。

因此，可以总结出：
判断队空：q.front == q.rear
判断队满：（q.rear+1）%MAXSIZE == q.front

接下来，我们先通过数组来对队列进行操作：

//定义数组队列结构体

typedef struct {
    ElemType *data;
    int front;
    int rear;
}StackQueue;

初始化队列，对数组进行动态分配空间

//初始化队列
Status InitStackQueue(StackQueue *q){
    //动态分配空间
    q->data = (ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
    q->front = q->rear = 0;
    return OK;
}

清空队列和判断队列是否为空

//清空队列
Status ClearStackQueue(StackQueue *q){
    q->front = q->rear = 0;
    return OK;
}
//判断队列是否为空
Status EmptyStackQueue(StackQueue q){
    if(q.rear == q.front)   return OK;
    else    return ERROR;
}

返回队列个数，通过（q.rear-q.front+MAXSIZE）与MAXSIZE取余。

//返回队列的个数
int StackQueueCount(StackQueue q){
    return (q.rear-q.front+MAXSIZE)%MAXSIZE;
}
//获取头节点
Status GetStackQueueHead(StackQueue q,ElemType *e){
    if(q.rear == q.front)   return ERROR;
    *e = q.data[q.front];
    return OK;
}

插入队列，在队尾操作

//队列的插入
Status PushStackQueue(StackQueue *q,ElemType e){
    //判断队满
    if((q->rear+1)%MAXSIZE == q->front) return ERROR;
    q->data[q->rear] = e;
    q->rear = (q->rear+1)%MAXSIZE;
    return OK;
}

删除，在对头删除

//队列的删除
Status DeleteStackQueue(StackQueue *q,ElemType *e){
    //判断队列是否为空
    if(q->rear == q->front) return ERROR;
    
    *e = q->data[q->front];
    q->front = (q->front+1)%MAXSIZE;
    return OK;
}

遍历操作

//遍历队列
Status DisplayStackQueue(StackQueue q){
    //判断队列是否为空
    if(q.rear == q.front)   return ERROR;
    int i = q.front;
    while (i!=q.rear) {
        printf("%d  ",q.data[i]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}

main函数，调用函数

printf("顺序队列的操作\n");
    
    int i=0;
    ElemType e;
    StackQueue q;
    printf("初始化队列\n");
    InitStackQueue(&q);
    printf("初始化队列后，队列是否为空？%d(1空,0不空)\n",EmptyStackQueue(q));
    printf("入队\n");
    for (int i = 0; i<15; i++) {
        PushStackQueue(&q, i);
    }
    DisplayStackQueue(q);
    printf("插入队列后，队列是否为空？%d(1空,0不空)\n",EmptyStackQueue(q));
    
    i = StackQueueCount(q);
    printf("队列个数为:%d\n",i);
    
    
    GetStackQueueHead(q, &e);
    printf("队列头节点为:%d\n",e);
    
    DeleteStackQueue(&q, &e);
    printf("出队列元素为:%d\n",e);
    
    ClearStackQueue(&q);
    printf("清空队列后，队列是否为空？%d(1空,0不空)\n",EmptyStackQueue(q));
    
    return 0;

打印结果

15868344412601.png 链表操作队列.png

链表实现队列，情况和用数组实现不太相同，在进行插入操作时，无需判断是否为空，直接在对尾即可插入，而清空和删除操作时，也需要将节点释放，将对头指向下一个节点。
接下来，我们来实现一下通过链表对队列进行操作：

定义节点和队列

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node, *QNode;

typedef struct {
    QNode rear;
    QNode front;
}LinkQueue;

通过链表来实现队列，无需再动态分配空间大小了，直接通过创建节点，然后加入队尾即可。

//初始化队列
Status InitLinkQueue(LinkQueue *q){
    q->front = q->rear = (QNode)malloc(sizeof(QNode));
    //判断创建的节点是否成功
    if(!q->front && !q->rear)   return ERROR;
    q->rear->next = NULL;
    return OK;
}

判断队列为空，同样的是判断q->front == q->rear。
销毁时，将整个队列都销毁
清空时，将尾节点指向头节点，将其他节点删除。

//判断队列是否为空
Status EmptyLinkQueue(LinkQueue *q){
    if(q->front == q->rear) return OK;
    else    return ERROR;
}
//销毁队列队列
Status DestoryLinkQueue(LinkQueue *q){
    while (q->front) {
        q->rear = q->front;
        q->front = q->front->next;
        free(q->rear);
    }
    return OK;
}
Status ClearLinkQueue(LinkQueue *Q){
    QNode p,q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    return OK;
}

在判断队列长度时，我们需要对链表进行遍历来得到队列的长度

int LinkQueueLength(LinkQueue q){
    int i = 0;
    QNode p;
    p = q.front;
    while (q.rear != p) {
        i++;
        p = p->next;
    }
    return i;
}

插入时，首先需要创建一个新节点，无需判断队列是否已满，将对尾指向新节点。
删除时，只需将头节点的下一个节点（首元节点）删除，将头节点指向首元节点的下一个节点。

//插入队列
Status PushLinkQueue(LinkQueue *q,ElemType e){
    QNode p;
    p = (QNode)malloc(sizeof(QNode));
    if(!p)  return ERROR;
    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
    return OK;
}
//删除队列
Status PopLinkQueue(LinkQueue *q,ElemType *e){
    if(q->front == q->rear) return ERROR;
    QNode p;
    p = q->front->next;
    *e = p->data;
    q->front->next = p->next;
    if(q->rear == p)    q->rear = q->front;
    free(p);
    return OK;
}

获取头节点和遍历节点

//获取队头元素
Status GetLinkQueueHead(LinkQueue q,ElemType *e){
    if(q.front == q.rear)   return ERROR;
    *e = q.front->next->data;
    return OK;
}
//遍历队列
Status DisplayLinkQueue(LinkQueue q){
    QNode p = q.front->next;
    while (p) {
        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

main函数，调用函数

Status isStatus;
    LinkQueue q;
    ElemType e;
    printf("Hello, World!\n");
    printf("链式队列的操作\n");
    printf("初始化\n");
    InitLinkQueue(&q);
    
    printf("初始化后，链表是否为空:%d(1空，0不空)\n",EmptyLinkQueue(&q));
    
    printf("队列长度为:%d\n",LinkQueueLength(q));
    
    for (int i = 0; i<10; i++) {
        PushLinkQueue(&q, i);
    }
    printf("插入之后，队列元素有:\n");
    DisplayLinkQueue(q);
    
    printf("插入后，链表是否为空:%d(1空，0不空)\n",EmptyLinkQueue(&q));
    
    printf("队列长度为:%d\n",LinkQueueLength(q));
    
    GetLinkQueueHead(q, &e);
    printf("队头元素为:%d\n",e);
    
    
    PopLinkQueue(&q, &e);
    printf("出队列元素为:%d\n",e);
    
    GetLinkQueueHead(q, &e);
    printf("出队列之后，队头元素为:%d\n",e);
    
    DisplayLinkQueue(q);
    printf("出队列之后,队列长度为:%d\n",LinkQueueLength(q));
    
    ClearLinkQueue(&q);
    printf("清空队列后，链表是否为空:%d(1空，0不空)\n",EmptyLinkQueue(&q));
    
    printf("销毁队列\n");
    isStatus = DestoryLinkQueue(&q);
    printf("销毁队列:%d(1成功,0失败)\n",isStatus);
    

打印结果

打印结果.png

通过数组和链表实现队列的操作，我更喜欢用数组来写队列，数组省去了很多麻烦的操作，例如节点的删除，队列的长度的获取等。