「数据结构五」C 语言实现队列

队列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

循环队列

和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还设置了两个整形变量 front 和 rear 分别指示队列头元素和队列尾元素的位置（分别称为头指针和尾指针）。

为了防止因为数组越界而导致的程序非法操作错误（我们称为“假溢出”）。因为此时队列的实际空间并未占满，所以这种现象称为“假溢出”。造成这种情况的原因是由于“队尾入队，队头出队”这种受限制的操作造成的。

关于“假溢出”，可以参考下面这两篇 csdn 博客。

队列---顺序队列的存储结构不足（假溢出）
队列---循环队列

上述“假溢出”的问题该怎么解决么？这里采用一个巧妙的办法，将顺序队列变成一个环状空间，称之为循环队列。

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE 0

typedef int Status;
typedef int QElemType;

typedef struct {
    QElemType *base;  //存储空间基地址
    int front;  //头指针
    int rear;  //尾指针
    int QueueSize;  //队列容量
}SqQueue;

Status InitQueue(SqQueue *);
Status DestroyQueue(SqQueue *);
Status ClearQueue(SqQueue *);
Status QueueEmpty(SqQueue );
int QueueLength(SqQueue);
Status GetHead(SqQueue, QElemType *);
Status EnQueue(SqQueue *, QElemType);
Status DeQueue(SqQueue *, QElemType *);
void QueueTraverse(SqQueue , void(*vi)(QElemType));

/**
 * 操作结果：构造一个空队列 Q
 * @param e
 * @return
 */
Status InitQueue(SqQueue *Q) {
    Q->base = (QElemType *)malloc(MAX_QUEUE_SIZE * sizeof(SqQueue));
    if (!Q->base) {
        exit(OVERFLOW);
    }
    Q->front = Q->rear = 0;  //头指针尾指针置为零，队列为空
    return OK;
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：队列 Q 被销毁
 * @param Q
 * @return
 */
Status DestroyQueue(SqQueue *Q) {
    if (Q->base) {
        free(Q->base);
    }
    Q->base = NULL;
    Q->front = Q->rear = 0;
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：清空队列 Q
 * @param Q
 * @return
 */
Status ClearQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：若 Q 为空队列，则返回 true，否则返回 false
 * @param Q
 * @return
 */
Status QueueEmpty(SqQueue Q) {
    if (Q.front == Q.rear) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：返回 Q 中元素个数，即队列长度
 * @param Q
 * @return
 */
int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

/**
 * 初始条件：队列 Q 存在且非空
 * 操作结果：返回 Q 中队头元素
 * @param Q
 * @param e
 * @return
 */
Status GetHead(SqQueue Q, QElemType *e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    *e = Q.base[Q.front];
    return OK;
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：插入入元素 e 为 Q 的新队尾元素
 * @param Q
 * @param e
 * @return
 */
Status EnQueue(SqQueue *Q, QElemType e) {
    if ((Q->rear + 1) % MAX_QUEUE_SIZE == Q->front) {
        return ERROR;  //队尾指针在循环意义上加 1 后等于头指针，表示队满
    }
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_QUEUE_SIZE;  //队尾指针加 1
    return OK;
}

/**
 * 初始条件：队列 Q 存在且非空
 * 操作结果：删除 Q 的队头元素，且用 e 返回
 * @param Q
 * @param e
 * @return
 */
Status DeQueue(SqQueue *Q, QElemType *e) {
    if (Q->front == Q->rear) {
        return ERROR;
    }
    *e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAX_QUEUE_SIZE;  //队头指针加 1
    return OK;
}

/**
 * 初始条件：队列 Q 存在且非空
 * 操作结果：从队头到队尾，依次对遍历队列中每个元素
 * @param Q
 * @param vi
 */
void QueueTraverse(SqQueue Q, void(*vi)(QElemType)) {
    int i = Q.front;
    while (i != Q.rear) {
        vi(Q.base[i]);  //遍历
        i = (i + 1) % MAX_QUEUE_SIZE;
    }
    printf("\n");
}

/**
 * 遍历函数
 * @param e
 */
void vi(QElemType e) {
    printf("%d ",e);
}

/**
 * 主函数，测试程序
 * @return
 */
int main() {
    SqQueue q;
    QElemType e;

    InitQueue(&q);
    printf("队列的长度：%d\n", QueueLength(q));
    printf("队列是否为空：%d\n", QueueEmpty(q));
    EnQueue(&q, 3);
    EnQueue(&q, 4);
    EnQueue(&q, 5);
    EnQueue(&q, 6);
    QueueTraverse(q, vi);
    printf("队列的长度：%d\n", QueueLength(q));
    printf("队列是否为空：%d\n", QueueEmpty(q));
    GetHead(q, &e);
    printf("队列的头元素：%d\n", e);
    DeQueue(&q, &e);
    QueueTraverse(q, vi);
    ClearQueue(&q);
    printf("队列的长度：%d\n", QueueLength(q));
    printf("队列是否为空：%d\n", QueueEmpty(q));

    DestroyQueue(&q);
}

上面测试代码在 Clion 下的执行结果如下图所示。

链式队列

链队是指采用链式存储结构实现的对列，队列通常用链队来实现，它有效的解决了队列存储空间不足的问题。

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define INFEASIBLE 0

typedef int Status;
typedef int QElemType;

typedef struct QNode {
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct {
    QueuePtr front;  //队头指针
    QueuePtr rear;  //队尾指针
}LinkQueue;

Status InitQueue(LinkQueue *);
Status DestroyQueue(LinkQueue *);
Status ClearQueue(LinkQueue *);
Status QueueEmpty(LinkQueue );
int QueueLength(LinkQueue);
Status GetHead(LinkQueue, QElemType *);
Status EnQueue(LinkQueue *, QElemType);
Status DeQueue(LinkQueue *, QElemType *);
void QueueTraverse(LinkQueue , void(*vi)(QElemType));

/**
 * 操作结果：构造一个空队列 Q
 * @param Q
 * @return
 */
Status InitQueue(LinkQueue *Q) {
    if (!(Q->front = Q->rear = (QueuePtr)malloc(sizeof(struct QNode)))) {
        exit(OVERFLOW);
    }
    Q->front->next = NULL;
    return OK;
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：队列 Q 被销毁
 * @param Q
 * @return
 */
Status DestroyQueue(LinkQueue *Q) {
    while (Q->front) {  //指向队尾时结束循环
        Q->rear = Q->front->next;  // 队尾指针指向队头指针的下一个结点
        free(Q->front);  //释放队头结点
        Q->front = Q->rear;  //修改队头指针
    }
    return OK;
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：清空队列 Q
 * @param Q
 * @return
 */
Status ClearQueue(LinkQueue *Q) {
    QueuePtr p, q;
    Q->rear = Q->front;  //队尾指针指向头结点
    p = Q->front->next;  //p 指向队列第一个元素
    Q->front->next = NULL;  //队头指针 next 域置空
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    return OK;

}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：若 Q 为空队列，则返回 true，否则返回 false
 * @param Q
 * @return
 */
Status QueueEmpty(LinkQueue Q) {
    if (Q.front->next == NULL) {
        return TRUE;
    } else {
        return FALSE;
    }
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：返回 Q 中元素个数，即队列长度
 * @param Q
 * @return
 */
int QueueLength(LinkQueue Q) {
    int i = 0;  //计数器
    QueuePtr p = Q.front->next;  //p 指向队头元素
    while (p) {
        i++;
        p = p->next;
    }
    return i;
}

/**
 * 初始条件：队列 Q 存在且非空
 * 操作结果：返回 Q 中队头元素
 * @param Q
 * @param e
 * @return
 */
Status GetHead(LinkQueue Q, QElemType *e) {
    if (Q.front != Q.rear) {
        *e = Q.front->next->data;
        return OK;
    }
    return INFEASIBLE;
}

/**
 * 初始条件：队列 Q 存在
 * 操作结果：插入入元素 e 为 Q 的新队尾元素
 * @param Q
 * @param e
 * @return
 */
Status EnQueue(LinkQueue *Q, QElemType e) {
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(struct QNode));  //开辟新结点
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;  //将新结点插入到队尾
    Q->rear = p;  //修改队尾指针
    return OK;
}

/**
 * 初始条件：队列 Q 存在且非空
 * 操作结果：删除 Q 的队头元素，且用 e 返回
 * @param Q
 * @param e
 * @return
 */
Status DeQueue(LinkQueue *Q, QElemType *e) {
    QueuePtr p;
    if (Q->front == Q->rear) {  //判断是否为空队列
        return ERROR;
    }
    p = Q->front->next;  //p 指向队头元素
    *e = p->data;
    Q->front->next = p->next;  //修改头指针
    if (Q->rear == p) {  //如果删除的是队列最后一个元素
        Q->rear = Q->front;  //队尾指针指向头结点
    }
    free(p);
    return OK;
}

/**
 * 初始条件：队列 Q 存在且非空
 * 操作结果：从队头到队尾，依次对遍历队列中每个元素
 * @param Q
 * @param vi
 */
void QueueTraverse(LinkQueue Q, void(*vi)(QElemType)) {
    QueuePtr p = Q.front->next;  //p 指向队头元素
    while (p) {
        vi(p->data);  //遍历
        p = p->next;
    }
    printf("\n");
}

/**
 * 遍历函数
 * @param e
 */
void vi(QElemType e) {
    printf("%d ",e);
}

/**
 * 主函数，测试程序
 * @return
 */
int main() {
    LinkQueue q;
    QElemType e;

    InitQueue(&q);
    printf("队列的长度：%d\n", QueueLength(q));
    printf("队列是否为空：%d\n", QueueEmpty(q));
    EnQueue(&q, 3);
    EnQueue(&q, 4);
    EnQueue(&q, 5);
    EnQueue(&q, 6);
    QueueTraverse(q, vi);
    printf("队列的长度：%d\n", QueueLength(q));
    printf("队列是否为空：%d\n", QueueEmpty(q));
    GetHead(q, &e);
    printf("队列的头元素：%d\n", e);
    DeQueue(&q, &e);
    QueueTraverse(q, vi);
    ClearQueue(&q);
    printf("队列的长度：%d\n", QueueLength(q));
    printf("队列是否为空：%d\n", QueueEmpty(q));

    DestroyQueue(&q);
}

具体运行效果和顺序栈运行效果一样。

想要查看源码可以访问下面 github 链接，如果觉得不错，请给个 Star。

顺序队列
 链式队列

本文属数据结构系列持续更新中。

最后编辑于：2017.12.07 04:45:52

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,602评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,442评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,878评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,306评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,330评论 5赞 373
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,071评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,382评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,006评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,512评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,965评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,094评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,732评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,283评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,286评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,512评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,536评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,828评论 2赞 345

「数据结构 五」C 语言实现队列

循环队列

链式队列

推荐阅读更多精彩内容

「数据结构五」C 语言实现队列