队列结构——顺序队列、循环队列、链队列

队列结构的定义和属性#

定义：队列是一种与线性表相似的线性结构。但仅允许在表的一端进行插入，而在表的另一端进行删除。

队列结构的几个属性：

队尾：插入的一端叫做队尾
队头：删除的一端叫做队头
入队：向队列中插入新节点元素称为入队
出队：从队列中删除节点元素称为出队
队空：当队列中无节点元素时，表示队空
队满：当队列中节点超过允许存储空间时，表示队满（链队无队满的状态）

从队列的基本定义和操作来看，队列是一种具有先进先出特点的数据结构。

队列结构的抽象数据类型#

ADT Queue
{
数据对象：
	D = {ai | ai∈ElemType, i=1,2,…,n, n≧0 } //ElemType为类型标识符
数据关系：
	R = {<ai, ai+1> | ai, ai+1∈D, i=1,3,…,n-1 }
数据操作：
	(1) queSeq * InitQueue();            		//初始化队列
	(2) void DestroyQueue(queSeq *q);         	//销毁队列
	(3) Bool QueueEmpty(queSeq *q);            	//判断队列是否为空
	(4) int QueueLength(queSeq *q);            	//返回队列中数据元素个数
	(5) void enQueue(queSeq *q, ElemType e);  	//入队
	(6) Bool deQueue(queSeq *q, ElemType *e); 	//出队
}

可以发现，相比于线性表，队列的抽象运算和栈同样受到限制。

顺序队列#

顺序队列利用数组存放节点元素，同时设置两个变量 front 和 rear 分别保存队头和队尾的索引。

front 保存队头索引，即是数组索引小的一端； rear 保存队尾索引，即是数组索引大的一端。

定义顺序队列的存储结构：

#define MaxSize 50
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int front, rear;        //  队头和队尾指针
} queSeq;

初始化队列时，设置变量 front = rear = -1，表示队列为空。

队列执行增删操作时，都需要先把 front 或 rear 向前移动一位，然后再执行取值或赋值。

由此可知，rear 位置保存队尾元素，front 位置为空，front+1 位置保存队头元素。

当 rear = MaxSize - 1 时，表示数组已达到存储上限，即是队满了。

当 front = rear 时，表示队头和队尾保存同一个位置，因为逻辑上 front 位置为空，所以队列为空。

front 位置物理上不为空，因为并没有释放该位置的内存，只是逻辑上认为是空的。

顺序队列代码实现：

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

#define true 1
#define false 0
#define MaxSize 50

typedef int Bool;
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int front, rear;        //  队头和队尾指针
} queSeq;

//  初始化顺序队列
queSeq * InitQueue();            
//  销毁顺序队列
void DestroyQueue(queSeq *q);         
//  判断顺序队列是否为空
Bool QueueEmpty(queSeq *q);            
//  返回队列中元素个数，也称队列长度
int QueueLength(queSeq *q);            
//  进队
Bool enQueue(queSeq *q, ElemType e);  
//  出队
Bool deQueue(queSeq *q, ElemType *e); 


int main()
{
    ElemType e;
    queSeq *q;
    printf("(1)初始化队列q\n");
    q = InitQueue();
    printf("(2)依次进队列元素a,b,c\n");
    if (enQueue(q, 'a') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'b') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'c') == 0)
        printf("队满,不能进队\n");
    printf("(3)队列为%s\n", (QueueEmpty(q) == 1? "空" : "非空"));
    if (deQueue(q, &e) == 0)
        printf("队空,不能出队\n");
    else
        printf("(4)出队一个元素%c\n", e);
    printf("(5)队列q的元素个数:%d\n", QueueLength(q));
    printf("(6)依次进队列元素d,e,f\n");
    if (enQueue(q, 'd') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'e') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'f') == 0)
        printf("队满,不能进队\n");
    printf("(7)队列q的元素个数:%d\n", QueueLength(q));
    printf("(8)出队列序列:");
    while (!QueueEmpty(q))
    {
        deQueue(q, &e);
        printf("%c ", e);
    }
    printf("\n");
    printf("(9)释放队列\n");
    DestroyQueue(q);
    return 0;
}

//  初始化顺序队列
queSeq * InitQueue()
{
    queSeq *tmp = (queSeq *)malloc(sizeof(queSeq));
    tmp->front = tmp->rear = -1;
    return tmp;
}

//  销毁顺序队列
void DestroyQueue(queSeq *q)
{
    free(q);
}

//是否队空
Bool QueueEmpty(queSeq *q)
{
    if(q->front == q->rear)
        return true;
    else
        return false;
}

//队长
int QueueLength(queSeq *q)
{
    return q->rear - q->front;
}

//入队
Bool enQueue(queSeq *q, ElemType e)
{
    //是否队满
    if(q->rear == MaxSize - 1)
        return false;
    
    q->rear++;
    q->data[q->rear] = e;
    return true;
}

//出队
Bool deQueue(queSeq *q, ElemType *e)
{
    //是否队空
    if(QueueEmpty(q))
        return false;
    
    q->front++;
    *e = q->data[q->front];
    return true;
}

循环队列#

顺序队列使用数组存储元素节点，随着队列增删元素，front 和 rear 的值会递增。

当 rear = front 和 rear = MaxSize-1 同时出现时，队列会出现队满的假象。

循环队列充分地使用数组的存储空间，把数组的两端连接起来（相当于把队头和队尾连接起来），形成一个环形的顺序表。从逻辑结构来看这是一个环形队列或循环队列，但是从数据存储的物理结构来看还是和原来的数组方式是一样的。

初始化队列时，设置变量 front = rear = 0，表示队列为空。

因为 front 位置默认为空，，即队列中 front 指向的位置始终为空，所以循环队列的最大存储数量为 MaxSize-1。

当 rear 向前移动一位与 front 相等时表示队满。这也是初始化是 front 和 rear 不能等于 -1 的原因。

循环队列代码实现：

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

#define true 1
#define false 0
#define MaxSize 5

typedef int Bool;
typedef char ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int front, rear;        //  队头和队尾指针
} queCyc;

//  初始化循环队列
queCyc * InitQueue();            
//  销毁循环队列
void DestroyQueue(queCyc *q);         
//  判断循环队列是否为空
Bool QueueEmpty(queCyc *q);            
//  返回队列中元素个数，也称队列长度
int QueueLength(queCyc *q);            
//  进队
Bool enQueue(queCyc *q, ElemType e);  
//  出队
Bool deQueue(queCyc *q, ElemType *e); 


int main()
{
    ElemType e;
    queCyc *q;
    printf("(1)初始化队列q\n");
    q = InitQueue();
    printf("(2)依次进队列元素a,b,c\n");
    if (enQueue(q, 'a') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'b') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'c') == 0)
        printf("队满,不能进队\n");
    printf("(3)队列为%s\n", (QueueEmpty(q) == 1? "空" : "非空"));
    if (deQueue(q, &e) == 0)
        printf("队空,不能出队\n");
    else
        printf("(4)出队一个元素%c\n", e);
    printf("(5)队列q的元素个数:%d\n", QueueLength(q));
    printf("(6)依次进队列元素d,e,f\n");
    if (enQueue(q, 'd') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'e') == 0)
        printf("队满,不能进队\n");
    if (enQueue(q, 'f') == 0)
        printf("队满,不能进队\n");
    printf("(7)队列q的元素个数:%d\n", QueueLength(q));
    printf("(8)出队列序列:");
    while (!QueueEmpty(q))
    {
        deQueue(q, &e);
        printf("%c ", e);
    }
    printf("\n");
    printf("(9)释放队列\n");
    DestroyQueue(q);
    return 0;
}

//  初始化循环队列
queCyc * InitQueue()
{
    queCyc *tmp = (queCyc *)malloc(sizeof(queCyc));
    tmp->front = tmp->rear = 0;
    return tmp;
}

//  销毁循环队列
void DestroyQueue(queCyc *q)
{
    free(q);
}

//是否队空
Bool QueueEmpty(queCyc *q)
{
    if(q->front == q->rear)
        return true;
    else
        return false;
}

//队长
int QueueLength(queCyc *q)
{
    if(q->rear >= q->front)
        return q->rear - q->front;
    else
        return q->rear + MaxSize - q->front;
}

//入队
Bool enQueue(queCyc *q, ElemType e)
{
    //是否队满
    if((q->rear+1)%MaxSize == q->front)
        return false;
    
    q->rear++;
    q->data[q->rear] = e;
    return true;
}

//出队
Bool deQueue(queCyc *q, ElemType *e)
{
    //是否队空
    if(QueueEmpty(q))
        return false;
    
    q->front++;
    *e = q->data[q->front];
    return true;
}

链队列#

链队的存储结构定义为：

typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
} queNode;              //链队数据结点类型定义

typedef struct
{
    queNode *front;
    queNode *rear;
} queLink;

链队由两部分组成，分别是：数据节点组成的数据链队和两个指向数据节点的指针。
数据节点保存数据和后继节点的地址，两个指针分别指向队头和队尾的数据节点。

初始化队列时，设置指针变量 front = rear = NULL，表示队列为空。

front 和 rear 不为空时， front 指向队头节点， rear 指向队尾节点。

rear 为空时，表示队列为空。

不能使用 front = rear 作为队列为空的判断依据，因为当 front = rear 时，有可能队列里还有一个元素。

链队代码实现：

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

#define true 1
#define false 0

typedef int Bool;
typedef char ElemType;
typedef struct node
{
    ElemType data;
    struct node *next;
} queNode;              //链队数据结点类型定义

typedef struct
{
    queNode *front;
    queNode *rear;
} queLink;                              //链队类型定义


queLink * InitQueue();                  //初始化链队
void DestroyQueue(queLink *q);          //销毁链队
Bool QueueEmpty(queLink *q);            //判断链队是否为空
int QueueLength(queLink *q);            //返回队列中数据元素个数
void enQueue(queLink *q, ElemType e);   //入队
Bool deQueue(queLink *q, ElemType *e);  //出队

int main()
{
    ElemType e;
    queLink *q;
    printf("(1)初始化链队q\n");
    q = InitQueue();
    printf("(2)依次进链队元素a,b,c\n");
    enQueue(q, 'a');
    enQueue(q, 'b');
    enQueue(q, 'c');
    printf("(3)链队为%s\n", (QueueEmpty(q) == 1 ? "空" : "非空"));
    if (deQueue(q, &e) == 0)
        printf("队空,不能出队\n");
    else
        printf("(4)出队一个元素%c\n", e);
    printf("(5)链队q的元素个数:%d\n", QueueLength(q));
    printf("(6)依次进链队元素d,e,f\n");
    enQueue(q, 'd');
    enQueue(q, 'e');
    enQueue(q, 'f');
    printf("(7)链队q的元素个数:%d\n", QueueLength(q));
    printf("(8)出链队序列:");
    while (!QueueEmpty(q))
    {
        deQueue(q, &e);
        printf("%c ",e);
    }
    printf("\n");
    printf("(9)释放链队\n");
    DestroyQueue(q);
    return 0;
}

//初始化
queLink * InitQueue()
{
    queLink *tmp = (queLink *)malloc(sizeof(queLink));
    //默认头尾指针同时为NULL
    tmp->front = tmp->rear = NULL;
    return tmp;
}

//销毁
void DestroyQueue(queLink *q)
{
    queNode *node = q->front,*tmp;
    while(node != NULL)
    {   
        tmp = node;
        //node节点继续向后移动
        node = node->next;
        free(tmp);
    }
    free(node);
    free(q);
}

//队列是否为空
Bool QueueEmpty(queLink *q)
{
    if(q->rear == NULL)
        return true;
    else 
        return false;
}

//队列长度
int QueueLength(queLink *q)
{
    queNode *node = q->front;
    int n = 0;
    while(node != NULL)
    {
        n++;
        node = node->next;
    }
    return n;
}

// 入队
void enQueue(queLink *q, ElemType e)
{
    queNode *node = (queNode *)malloc(sizeof(queNode));
    node->data = e;
    node->next = NULL;
    //空队列时，把新节点赋值给头尾指针
    //当不为空队列时，把新节点赋值给尾指针的next指针，并把尾指针向后移动
    if(QueueEmpty(q))
        q->front = q->rear = node;
    else
    {
        q->rear->next = node;
        q->rear = node;
    }
}

//出队
Bool deQueue(queLink *q, ElemType *e)
{
    queNode *node;
    //空队列时，直接return
    if(QueueEmpty(q))
        return false;
    
    node = q->front;
    //只剩下一个节点时，把头尾指针重新赋值为NULL
    //剩余多个节点时，把头节点响后移动
    if (node->next == NULL)
        q->front = q->rear = NULL;
    else
        q->front = q->front->next;
    
    //节点取值，通过指针传值
    *e = node->data;
    free(node);
    return true;
}