基本概念
队列是最常见的概念，日常生活经常需要排队，仔细观察队列会发现，队列是一种逻辑结构，是一
种特殊的线性表。特殊在：
只能在固定的两端操作线性表
只要满足上述条件，那么这种特殊的线性表就会呈现一种“先进先出”的逻辑，这种逻辑就被称为队
列。
由于约定了只能在线性表固定的两端进行操作，于是给队列这种特殊的线性表的插入删除，起个特
殊的名称：
队头：可以删除节点的一端
队尾：可以插入节点的一端
入队：将节点插入到队尾之后
出队：将队头节点从队列中剔除
由于这种固定两端操作的简单约定，队列获得了“先进先出”的基本特性，如下图所示：
顺序存储的队列：循环队列
与其他的逻辑结构类似，队列可以采用顺序存储形成循环队列，也可以采用链式存储形成链式队
列。顺序存储的队列之所以被称为循环队列，是因为可以利用更新队头队尾的下标信息，来循环地
利用整个数组，出队入队时也不必移动当中的数据。循环队列示意图如下所示：
从上述动图中可以观察到，需要牺牲至少数组中的一个存储位置，来区分循环队列中的满队和空
队。满队和空队的约定如下：
当head（队头元素下标）与tail（队尾元素下标）相等时，队列为空
当tail循环加一与head相等时，队列为满
与其他数据结构一样，管理循环队列除了需要一块连续的内存之外，还需要记录队列的总容量、当
前队列的元素个数、当前队头、队尾元素位置，如果有多线程还需要配互斥锁和信号量等信息，为
了便于管理，通常将这些信息统一于在一个管理结构体之中：
typedef int DATA;
typedef struct
{DATA *pData; // 队列入口int size; // 队列总容量int head; // 队列队头元素下标int tail; // 队列队尾元素下标
}SQueue;
循环队列的基本操作
分析
squeue.h
#ifndef __SQUEUE_H
#define __SQUEUE_H
typedef int DATA;
typedef struct
{DATA *pData; // 队列入口int size; // 队列总容量int head; // 队列队头元素下标int tail; // 队列队尾元素下标
}SQueue;
// 初始化队列
int SQ_init(SQueue *q, int num);
// 判断队列是否已满
int SQ_isfull(SQueue *q);
// 判断队列是否为空
int SQ_isempty(SQueue *q);
// 入队
int SQ_push(SQueue *q,DATA data);
// 出队
int SQ_pop(SQueue *q,DATA *data);
// 回收队
int SQ_free(SQueue *q);
#endifsqueue.c
#include <stdlib.h>
#include "squeue.h"
// 初始化队列
int SQ_init(SQueue* q,int num)
{q -> pData = (DATA*)calloc(sizeof(DATA),num);if(q -> pData == NULL)return -1;q -> size = num ;q -> head = q -> tail = 0;return 0;
}
// 判断队列是否已满
int SQ_isfull(SQueue *q)
{return (q -> tail + 1) % q -> size == q -> head;
}
// 判断队列是否为空
int SQ_isempty(SQueue *q)
{return q -> tail == q -> head;
}
// 出队
int SQ_push(SQueue *st,DATA data)
{if(SQ_isfull(st))return -1;st -> pData[st -> tail] = data;st -> tail = (st -> tail+1) % st -> size;return 0;
}
// 入队
int SQ_pop(SQueue *st,DATA *data)
{if(SQ_isempty(st))return -1;*data = st -> pData[st -> head];st -> head = (st -> head+1) % st -> size;return 0;
}
// 回收队列
int SQ_free(SQueue *st)
{if(st -> pData){free(st->pData);st -> pData = NULL;}st -> head = st -> tail = 0;
}注意：
循环队列中，需要牺牲一个存储位置来区分空队和满队
链式存储的队列：链式队列
链式队列的组织形式与链表无异，只不过插入删除被约束在固定的两端。为了便于操作，通常也会
创建所谓管理结构体，用来存储队头指针、队尾指针、队列元素个数等信息：
从上图可以看到，链式队列主要控制队头和队尾，由于管理结构体中保存了当前队列元素个数
size，因此可以不必设计链表的头节点，初始化空队列时只需要让队头队尾指针同时指向空即可。
以下是队列链表节点设计和管理结构体设计的示例代码：
typedef int DATA;
// 链式队列节点
typedef struct _node
{DATA data;struct _node *next;
}NODE/*,*PNODE*/;
// 链式队列管理结构体
typedef struct
{NODE *pHead; // 队头指针NODE *pTail; // 队尾指针int size ; // 队列当前元素个数int num ;
}LinkQueue;链式队列的基本操作
分析
linkQueue.h
#ifndef __LINKQUEUE_H
#define __LINKQUEUE_H
typedef int DATA;
// 链式队列节点
typedef struct _node
{DATA data;struct _node *next;
}NODE/*,*PNODE*/;
// 链式队列管理结构体
typedef struct
{NODE *pHead; // 队头指针NODE *pTail; // 队尾指针int size ; // 队列当前元素个数
int num ;
}LinkQueue;
void LQ_init(LinkQueue *q,int sz);
int LQ_isfull(LinkQueue *q);
int LQ_isempty(LinkQueue *q);
int LQ_push(LinkQueue *q,DATA data);
int LQ_pop(LinkQueue *q,DATA *data);
int LQ_free(LinkQueue *q);
#endiflinkQueue.c
#include "LinkQueue.h"
#include <stdlib.h>
void LQ_init(LinkQueue *q,int sz)
{q -> pHead = q -> pTail = NULL;q -> size = sz;q -> num = 0;
}
int LQ_isfull(LinkQueue *q)
{return q -> num == q -> size;
}
int LQ_isempty(LinkQueue *q)
{return q -> num == 0;
}
int LQ_push(LinkQueue *q,DATA data)
{if(LQ_isfull(q))return -1;NODE* pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;pNew -> data = data;pNew -> next = NULL;if(!(q -> pTail))q -> pHead = q -> pTail = pNew;
else{ q -> pTail -> next = pNew;q -> pTail = pNew;}q -> num ++;return 0;
}
int LQ_pop(LinkQueue *q,DATA *data)
{if(LQ_isempty(q))return -1;NODE* p = q -> pHead;*data = p -> data;if(p == q -> pTail)q -> pHead = q -> pTail = NULL;else q -> pHead = p -> next;free(p);q -> num --;return 0;
}
int LQ_free(LinkQueue *queue)
{NODE* p = queue -> pHead, *q = NULL;while(p){q = p;p = p -> next;free(q);}queue -> pHead = queue -> pTail = NULL;queue -> num = 0;return 0;
}linkQueue_main.c
int main(void)
{LinkQueue queue;LQ_init(&queue,10);register int i = 1; for(; i <= 10 ; i++) LQ_push(&queue, i);if( -1 == LQ_push(&queue,1024))fprintf(stderr,"满队,入队失败!\n");while(!LQ_isempty(&queue)){DATA data;LQ_pop(&queue,&data);printf("%4d",data);}printf("\n");LQ_free(&queue);return 0;
}
)
