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

1）队列的定义

      队列是一种先进先出的线性表，它允许在表的一端进行插入，在表的另一端进入删除，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）。 

2）队列的存储结构

队列的顺序存储：队列的顺序存储结构又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指向当前的队头和队尾。

        在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针。由于顺序队列的空间大小是提前设定好的，所以队尾指针有一个上限值，当队尾指针达到上限值时，就不能只通过修改队尾指针来实现新元素的入队操作了，若将顺序队列假想成一个环状，则可维持入队、出队操作运算的简单性，称为循环队列。

如图一，设循环队列最大容量MAXSIZE,初始队列为空，且rear = front = 0。

如图二，元素入队时，修改队尾指针 rear = (rear + 1) % MAXSIZE;

如图三，元素出队时，修改队头指针 front = (front +1) % MAXSIZE;

如图四，队列为空时，rear == front;

如图五，入队操作导致队列满，则 rear == front;

如图六，为了区分队列空 和 队列满，牺牲一个存储单元，约定以“队列的尾指针所指位置的下一个位置是头指针时表示队满”，“头、尾指针相同时表示队空”;

循环队列的基本操作

①初始化

#define MAXSIZE 100typedef struct{    int *base;    //循环队列的存储空间，假设为整数    int front;    //队头    int rear;     //队尾}SqQueue;int init(SqQueue *queue){    queue->base = (int *)malloc(MAXSIZE * sizeof(int));    if(!queue->base)        return -1;    queue->front = 0;    queue->rear = 0;    return 0;}

 ②出队列

int DeQueue(SqQueue *queue,int *e){    if(queue->rear == queue->front)        return -1;    *e = queue->base[queue->front];    queue->front = (queue->front + 1) % MAXSIZE;    return 0;}

③入队列

int EnQueue(SqQueue *queue,int e){    if((queue->rear + 1) % MAXSIZE == queue->front)        return -1;    queue->base[queue->rear] = e;    queue->rear = (queue->rear + 1) % MAXSIZE;    return 0;}

队列的链式存储结构

      为了便于操作，给链队列添加一个头结点，并令头指针指向头结点，因此，队列为空的判定条件是头指针和尾指针相等，且都指向头结点。