【数据结构】队列的深度学习

数据结构再度学习（详细注释版）：队列<顺序（循环实现）队列，链队列>

顺序队列

//
//  main.c
//  SequenceQueue
//
//  Created by Eason on 2020/8/2.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 21  //采用循环队列的方式，充分利用空间，但是会有一个单元的浪费，实际容量为最大容量-1，因为要区分空与满
typedef int ElemType;
typedef int Status;
typedef struct{   //顺序队列的存储结构
    ElemType data[MAXSIZE];   //队列元素的数据
    int front, rear;   //头指针与尾指针
}SqQueue;

//初始化顺序队列
Status initQueue(SqQueue *Q){
    Q->front=0;   //初始时头指针与为指针均指向0
    Q->rear=0;
    return OK;
}

//判断顺序队列是否为空
Status isEmpty(SqQueue Q){
    if(Q.front==Q.rear){   //当头指针与尾指针指向相同的单元时表示队列为空
        return TRUE;
    }else{
        return FALSE;
    }
}

//判断顺序队列是否已满
Status isFull(SqQueue Q){
    if((Q.rear+1)%MAXSIZE==Q.front){   //循环队列头指针可能在前也可能在后，头指针在前尾指针在最后差1时为满，头指针在后尾指针与头指针差1时为满，则用差值取余的方式可判断当前是否已满
        return TRUE;
    }else{
        return FALSE;
    }
}
//获取顺序队列的长度
Status getLength(SqQueue Q){
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;   //根据循环队列的特点，即长度为差值加最大容量与最大容量的取模运算
}

//清空顺序队列
Status clearQueue(SqQueue *Q){
    Q->front = Q->rear;   //根据队列为空的判断条件，即将头指针指向尾指针时两指针指向同一单元时队列为空。不能颠倒，因为尾指针指向的是空单元
    return OK;
}

//入队
Status enter(SqQueue *Q, ElemType *e){
    if(isFull(*Q)){   //判断队列是否还可以再入队元素
        printf("队列已满，无法入队\n");
        return ERROR;
    }
    Q->data[Q->rear]=e;   //将当前尾指针指向的空白单元入值
    Q->rear = (Q->rear+1)%MAXSIZE;   //将尾指针向后走一格，因为有可能是从队尾到队头，所以使用取模的方式判断尾指针接下来的位置
    return OK;
}

//出队
Status leave(SqQueue *Q, ElemType *e){
    if(isEmpty(*Q)){   //判断队列是否有元素可以出队
        printf("队列为空，不可出队\n");
        return ERROR;
    }
    *e = Q->data[Q->front];   //将当前队首元素出队给e供返回与查看
    Q->front = (Q->front+1)%MAXSIZE;   //将头指针向后走一格，因为有可能是从队尾到队头，所以使用取模的方式判断头指针接下来的位置
    return OK;
}

//获取队首元素
Status getHead(SqQueue Q, ElemType *e){
    if(isEmpty(Q)){   //判断队列是否有元素可供查看
        printf("队列为空，无队首元素\n");
        return ERROR;
    }
    *e = Q.data[Q.front];   //将当前队头元素返回给e供返回并查看
    return OK;
}

//打印队列
Status printQueue(SqQueue Q){
    if(isEmpty(Q)){   //判断队列当前是否有元素可供打印
        printf("队列为空，无队元素可供打印\n");
        return ERROR;
    }
    int i=0;   //当前元素数量计数器
    while(!isEmpty(Q)){
        i++;   //不为空说明当前有元素可供打印，则计数器+1
        printf("从队首至队尾的第%d个元素为：%d\n", i, Q.data[Q.front]);   //打印当前队首元素
        Q.front = (Q.front+1)%MAXSIZE;   //将头指针向后走一格，因为有可能是从队尾到队头，所以使用取模的方式判断头指针接下来的位置
    }
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    SqQueue Q;
    initQueue(&Q);
    printf("初始化队列Q后队列的长度为：%d,是否为空？（是1否0）：%d\n", getLength(Q), isEmpty(Q));
    printf("将1-18顺序的入队后队列变为：\n");
    for(int i=1;i<=18;i++){
        enter(&Q, i);
    }
    printQueue(Q);
    printf("此时队列的长度为：%d\n", getLength(Q));
    printf("队列的最大长度为20，检验再依次入队3个元素后得：\n");
    enter(&Q, 19);
    enter(&Q, 20);
    enter(&Q, 21);
    printQueue(Q);
    printf("-----验证循环队列-----\n");
    int e;
    leave(&Q, &e);
    printf("出队列：%d\n", e);
    enter(&Q, 21);
    printf("入队列：21\n");
    printf("此时的队列内容为：\n");
    printQueue(Q);
    printf("此时队列的长度为：%d，是否已满？（1是0否）：%d\n", getLength(Q), isFull(Q));
    printf("清空队列后队列为：\n");
    clearQueue(&Q);
    printQueue(Q);
    return 0;
}

链队

//
//  main.c
//  LinkedQueue
//
//  Created by Eason on 2020/8/2.
//  Copyright © 2020 Eason. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;   //注意：头指针始终指向头结点（不存放数据）头结点的下一结点才是链队的队头
typedef struct QueueNode{   //链队结点的存储结构
    ElemType data;   //数据域
    struct QueueNode *next;   //指针域
}QueueNode, *QueueNodePtr;

typedef struct{   //链队头结点的存储结构
    QueueNodePtr front, rear;   //头指针与尾指针
}LinkQueue;

//初始化链队
Status initQueue(LinkQueue *Q){
    Q->front = (QueueNodePtr)malloc(sizeof(QueueNode));   //初始化为首位指针分配内存
    Q->rear = (QueueNodePtr)malloc(sizeof(QueueNode));
    if(!Q->front || !Q->rear){   //若不存在则说明内存分配失败无法初始化
        printf("初始化内存分配失败");
        return ERROR;
    }
    Q->front = Q->rear;   //空队的条件 队头指针=队尾指针 均指向头结点
    Q->front->next = NULL;   //头结点的下一结点，即首个结点为空
    return OK;   //这里要注意，初始的时候首位指针均指向头结点，是不存放数据的，链队此时为空
}

//判断链队是否为空
Status isEmpty(LinkQueue Q){
    if(Q.front==Q.rear){   //链队为空的条件为头指针=尾指针，即都指向头结点
        return TRUE;
    }else{
        return FALSE;
    }
}

//获取链队的长度
int getLength(LinkQueue Q){
    QueueNodePtr p;   //定义临时结点指针
    p = Q.front->next;   //将临时结点置为链队的首个结点
    int i=0;   //链队长度计数器
    while(p){   //如果此时链队结点存在的话就继续向下进行
        i++;   //计数器+1
        p = p->next;   //链队指针继续向下移动
    }
    return i;   //返回链队计数器i即长度
}

//入队
Status enter(LinkQueue *Q, ElemType *e){
    QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));   //为新入队的结点分配内存空间
    if(!p){   //验证是否为新结点内存分配成功
        printf("新结点内存分配失败，无法入队");
        return ERROR;
    }
    p->data = e;   //将新结点的数据域置为指定值
    Q->rear->next = p;   //还未入队的此时队尾的下一结点指向p
    Q->rear = p;   //这时队尾指针指向p，即p成为了新的队尾结点
    p->next = NULL;   //队尾结点的指针域为空
    return OK;
}

//出队
Status leave(LinkQueue *Q, ElemType *e){
    if(isEmpty(*Q)){   //判断链队是否为空，若为空则无链队元素可供出队
        printf("链队为空，无队元素可出列\n");
        return ERROR;
    }
    QueueNodePtr p;   //定义临时结点指针p
    p = Q->front->next;   //将p置为链队的首个结点
    *e = p->data;   //将首个结点p的数据域赋给e以供返回与查看
    Q->front->next = p->next;   //将老首个结点的下一结点设置为首个结点
    if(Q->rear == p){   //若此时p也为尾结点，说明队列为空了
        Q->rear = Q->front;   //如果队列为空则将队尾指针重新指向头结点表示链队为空了
    }
    free(p);   //将出队的p结点释放掉
    return OK;
}

//获取链队的队头元素
Status getHead(LinkQueue Q, ElemType *e){
    if(isEmpty(Q)){   //判断链队是否为空，若为空则无链队的队头元素可供查看
        printf("链队为空，无队头元素\n");
        return ERROR;
    }
    *e = Q.front->next->data;   //若链队不为空，则将链队的首个结点的数据域赋给e供返回与查看
    return OK;   //仅查看队头元素，指针不发生移动
}

//清空链队
Status clearQueue(LinkQueue *Q){
    QueueNodePtr p, q;   //定义临时结点pq
    p = Q->front->next;   //将p结点置为链队的首个结点
    Q->rear = Q->front;   //将队尾指针指向头结点与头指针相同，这样则表示此时链队为空
    Q->front->next = NULL;   //将头结点的指针域置空，即无首个结点
    while(p){   //若p存在则继续执行循环体
        q = p;   //将p赋给q
        p = p->next;   //p继续向下进行
        free(q);   //释放q，一直循环直到p结点不再存在，即此时链队的结点都被释放掉了
    }
    return OK;
}

//打印链队
Status printQueue(LinkQueue Q){
    if(isEmpty(Q)){   //判断链队是否为空，若为空则无链队元素可供打印
        printf("当前链队无元素可供打印\n");
        return ERROR;
    }
    QueueNodePtr p;   //定义临时结点p
    p = Q.front->next;   //将p赋为链队的首个结点
    int i=0;   //此时链队元素位置计数器
    while(p){   //如果此时p存在的话则继续执行循环体
        i++;   //p存在则计数器+1
        printf("从队首至队尾的第%d个元素为：%d\n", i, p->data);   //打印当前p结点的数据域
        p = p->next;   //p指针继续向下移动，直到p为空，即链队的所有结点都打印完毕
    }
    return OK;
}

//测试
int main(int argc, const char * argv[]) {
    LinkQueue Q;
    initQueue(&Q);
    printf("初始化队列Q后队列的长度为：%d\n此时的链队是否为空？（1是0否）：%d\n", getLength(Q), isEmpty(Q));
    printf("将1-6按顺序入队后可得链队：\n");
    for(int i=1;i<=6;i++){
        enter(&Q, i);
    }
    printQueue(Q);
    printf("此时队列的长度为：%d\n", getLength(Q));
    int e;
    getHead(Q, &e);
    printf("此时队列的队头为：%d\n", e);
    printf("队列出队两个元素：\n");
    leave(&Q, &e);
    printf("出队：%d\n", e);
    leave(&Q, &e);
    printf("出队：%d\n", e);
    printf("现在的链队为：\n");
    printQueue(Q);
    printf("现在的链队长度为：%d\n", getLength(Q));
    getHead(Q, &e);
    printf("现在链队的队头为：%d\n", e);
    printf("清空链队后得链队为：\n");
    clearQueue(&Q);
    printQueue(Q);
    return 0;
}