本文共 5402 字，大约阅读时间需要 18 分钟。

队列的基本认识和操作

一.队列的基础知识

队列是一种可以实现“先进先出”的存储结构。也可以理解为一种特殊的链表，它只允许在链表的一端进行插入，在链表的另一端删除元素，不可以在中间操作。如同我们平常去排队买票，先到的先买到票就可以先走，后来的就只能等轮到自己时才可以买票走。

2.队列的分类

队列的结构可分为链式队列和静态队列两种。链式队列采用动态内存分配的方式实现，允许任意位置插入和删除操作；而静态队列则基于固定大小的数组采用循环结构实现，避免了传统数组的假溢出问题。

队列的结构图可以用链表和循环数组来表示。链式队列每个节点包含数据和指向下一个节点的指针，静态队列则通过循环数组实现环形存储结构。

对于队列也是受限的线性表，但由于顺序存储会出现假溢出，所以出现了循环队列的结构防止顺序存储的队列出现溢出假现象，链队列不会出现这种情况。

3.队列通常定义的参数

①.一个队列通常由队头（front）和队尾（rear）两个参数确定。

②.两个参数不同场合的不同含义：

• 队列初始化：front和rear的值都是零。
• 队列非空：front代表的是队列的第一个元素，rear代表的是队列的最后一个有效元素的下一个元素。
• 队列为空：front和rear的值相等，但不一定是零。

---

二.链式队列的建立和基本操作

1.队列所需的结构体

typedef struct Node {     int data;     struct Node *pNode; } NODE, *PNODE; typedef struct awsl {     PNODE front;     PNODE rear; } AWSL, *PAWSL;

2.队列初始化

链式队列就像链表，所以就要初始化的时候动态开辟内存或者用数组的形式为其开辟内存，除了要开辟内存外，还要初始化结构中的其他项，尤其注意指针域，不初始化可能会对计算机已存储的数值产生影响。当front和rear相等时表示队列为空，即front和rear指向同一个结点。

3.入队

入队操作只能从队尾，链式队列不用担心队列是否已满，但是我们先要保证内存空间要有，所以就要先判断计算机是否有足够的空间分配给该函数，然后就是尾插，先使队尾(rear)指向的结点指向新创建的结点，再使队尾(rear)为新插入的结点。

4.出队

出队操作只能从队头出队，对于链式队列只需要将front指向下一个结点，再释放掉原front位置的空间即可。

5.遍历队列

对于队列的遍历，只需要定义一个指针从front到rear将每个结点存储的数据逐一输出即可。

6.清空队列

从front开始直到rear，front每往后走一个，就释放掉front原指向的结点即可。

7.链式队列源代码

#include #include #include typedef struct Node {     int data;     struct Node *pNode; } NODE, *PNODE; typedef struct awsl {     PNODE front;     PNODE rear; } AWSL, *PAWSL; void init_awsl(PAWSL ps) {     PNODE t = (PNODE)malloc(sizeof(NODE));     if (NULL == t) {         printf("内存不足！1\n");         exit(-1);     }    ps->rear = ps->front = t;     t->pNode = NULL;     return; }void push_awsl(PAWSL ps) {     if (NULL != ps->rear->pNode) {         printf("请初始化！\n");         return;     }    PNODE t = (PNODE)malloc(sizeof(NODE));     if (NULL == t) {         printf("内存不足！\n");         exit(-1);     }    printf("要入列的元素是：");     scanf("%d", &ps->rear->data);     ps->rear->pNode = t;     ps->rear = t;     t->pNode = NULL;     return; }void go_awsl(PAWSL ps) {     PNODE t = ps->front;     if ((NULL == t->pNode) || (NULL != ps->rear->pNode)) {         printf("队列为空！出列失败。\n");         return;     }    ps->front = t->pNode;     printf("出列的元素是：%d\n", t->data);     free(t);     return; }void traverse_awsl(PAWSL ps) {     PNODE t = ps->front;     if ((NULL == t->pNode) || (NULL != ps->rear->pNode)) {         printf("队列为空！遍历失败。\n");         return;     }    printf("队列内的元素：\n");     while (t != ps->rear) {         printf("%d\n", t->data);         t = t->pNode;     }    return; }void empty_awsl(PAWSL ps) {     if (NULL != ps->rear->pNode) {         printf("请初始化！\n");         return;     }    while (ps->front != ps->rear) {         PNODE t = ps->front;         ps->front = t->pNode;         free(t);     }    printf("已清空！\n");     return; }

---

三.静态队列的建立和基本操作

创建静态队列的前提条件

所谓的静态队列就是一个循环数组，数组是一个线性关系的顺序表，实现数组的循环是静态队列的关键，这就使我们想到了约瑟夫环，利用%的原理使数组变成一个环型，即队头（front）和队尾（rear）每次移动时并不是向数组一般直接+1，而是利用front=(front+1)%数组长度和rear=(rear+1)%数组长度来实现环形数组。

使用此方法需要注意的是，顺序队列在判断数组是否已满时，出现以下情况：

• 当队列为空时，队列的头指针等于队列的尾指针；
• 当数组满员时，队列的头指针等于队列的尾指针；

1.队列所需的结构体

typedef struct queue {     int *pBase;     int front;     int rear; } QUEUE;

2.队列初始化

静态队列就像数组一样，不过他是一个循环数组，因为需要在被调中定义静态队列，所以需要动态分配内存，除了要开辟内存外，还要初始化结构中的其他项。前后指针重合时表示队列为空。

3.判断队列是否存满

当队尾（rear）的下一个就是队头（front）时，表示该队列已满。

4.入队

入队操作只能从队尾，先判断队列是否已满，然后就是尾插，rear表示的是队尾的存储值的空间的下一个，也就是直接把值存进下标为 rear的空间。

5.判断队列是否为空

当静态队列的front和rear值相等时，表示该队列为空。

6.出队

静态队列的出队，只需要修改front，使它为下一个单元的下标就可以，这样就可以把数据从逻辑上删除。

7.遍历队列

定义一个整型类型的变量，作为下标从front遍历到rear并逐一输出。

8.清空队列

清空静态队列，我们只需要把front和rear下标重新指向数组的0下标即可。

9.摧毁队列

对于摧毁操作，我们就要把初始化中开辟的内存释放掉并且把front和rear赋值为0。

10.静态队列源代码

#include #include #include typedef struct queue {     int *pBase;     int front;     int rear; } QUEUE;void init(QUEUE *pQ) {     pQ->pBase = (int *)malloc(sizeof(int) * 6);     pQ->front = 0;     pQ->rear = 0; }bool en_queue(QUEUE *pQ, int val) {     if (full_queue(pQ)) {         return false;     } else {         pQ->pBase[pQ->rear] = val;         pQ->rear = (pQ->rear + 1) % 6;         return true;     }}bool full_queue(QUEUE *pQ) {     if ((pQ->rear + 1) % 6 == pQ->front) {         return true;     } else {         return false;     }}void traverse_queue(QUEUE *pQ) {     int i = pQ->front;     while (i != pQ->rear) {         printf("%5d", pQ->pBase[i]);         i = (i + 1) % 6;     }    return; }bool out_queue(QUEUE *pQ, int *val) {     if (empty_queue(pQ)) {         return false;     } else {         *val = pQ->pBase[pQ->front];         pQ->front = (pQ->front + 1) % 6;         return true;     }}bool empty_queue(QUEUE *pQ) {     if (pQ->rear == pQ->front) {         return true;     } else {         return false;     }}bool clear_queue(QUEUE *pQ) {     pQ->front = pQ->rear = 0;     return true; }bool destory_queue(QUEUE *pQ) {     free(pQ->pBase);     pQ->pBase = NULL;     pQ->front = pQ->rear = 0;     return true; }int main(void) {     QUEUE Q;     int val;     init(&Q);     en_queue(&Q, 1);     en_queue(&Q, 2);     en_queue(&Q, 3);     en_queue(&Q, 4);     en_queue(&Q, 5);     en_queue(&Q, 6);     en_queue(&Q, 7);     traverse_queue(&Q);     printf("\n");     if (out_queue(&Q, &val)) {         printf("出队成功，出队的元素为%2d", val);     } else {         printf("出队失败！");     }    printf("\n");     traverse_queue(&Q);     printf("\n");     if (clear_queue(&Q)) {         printf("队列已清空！");     } else {         printf("队列清空失败！");     }    printf("\n");     if (destory_queue(&Q)) {         printf("队列摧毁成功！");     } else {         printf("队列摧毁失败！");     }    return 0; }

转载地址：http://jfrf.baihongyu.com/