顺序队列的介绍及C/C++代码实现

1.队列的概念

在开始前，请牢记这句话：队列是一个先进先出的数据结构。

队列（queue）是限定在表的一端进行插入，表的另一端进行删除的数据结构，如同栈的学习，请联系前文所学链表，试想一个单链表，我们只能对他的链表表尾进行插入，而只能对链表的表头进行结点的删除，其余一切的操作均不允许，这样强限制性的“链表“，就是我们所说的队列。

让我们重新理顺一下定义：队列是一个线性的数据结构，规定这个数据结构只允许在一端进行插入，另一端进行删除，禁止直接访问除这两端以外的一切数据。

如图：队列就像一个两端相通的水管，只允许一端插入，另一端取出，先放入管中的球先从管中拿出。

2. 队列的结点设计与初始化

队列不如栈那般方便进行模拟，因此队列只有链式的设计方法，但是不同的是，队列本身分为多种队列，如顺序队列（就是此文所讲队列）和循环队列（下一篇文章所讲），以及后文在C++STL章中会提到的优先队列等等，均来自于队列的衍生。

我们以顺序队列的设计为例。

首先是队列的结点设计，我们可以设计出两个结构体，一个结构体Node表示结点，其中包含有一个data域和next指针（可以发现，这样的结点设计我们已经重复出现了很多次了，正是因为这样的结构设计方便理解）。

（图表示结点）

其中data表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）。

next指针表示，下一个的指针，其指向下一个结点，通过next指针将各个结点链接。

如同栈再次设计一个结构体进行限制性设计，接着，我们也额外添加一个结构体，其包括了两个分别永远指向队列的队尾和队头的指针，我们主要的操作只对这两个指针进行操作。

（图表示队列设计）

其结构体设计的代码可以表示为：

//结点定义
typedef struct node{
    int data;
    struct node *next;
}node;
//队列定义，队首指针和队尾指针
typedef struct queue{
    node *front;    //头指针
    node *rear;     //尾指针
}queue;

有关初始化，稍微复杂一点的是，我们对于初始化需要初始化两个类型，一个是初始化结点，一个是初始化队列，初始化队列稍微有些不同，那就是当初始化队列的时候，需要将头尾两个结点指向的内容统统制空，表示是一个空队列，两个创建的函数代码可以表示为：

//初始化结点
node *init_node(){
    node *n=(node*)malloc(sizeof(node));
    if(n==NULL){    //建立失败，退出
        exit(0);
    }
    return n;
}
 
//初始化队列
queue *init_queue(){
    queue *q=(queue*)malloc(sizeof(queue));
    if(q==NULL){    //建立失败，退出
        exit(0);
    }
    //头尾结点均赋值NULL
    q->front=NULL;  
    q->rear=NULL;
    return q;
}

3. 判断队列是否为空

判断队列是否为空比较简单，直接就是判断队列头指针是否是空值即可（关联如何创建队列可更好理解），判断队列是否为空是比较常用的操作。

其代码可以表示为：

//队列判空
int empty(queue *q){
    if(q->front==NULL){
        return 1;   //1--表示真，说明队列非空
    }else{
        return 0;   //0--表示假，说明队列为空
    }
}

或者直接利用返回值进行更简单的判断（两者效果完全一样）

int empty(queue *q){
    return q->front==NULL;
}