首页  /  数据结构教程  /  顺序队列一  /  

顺序队列一

点击打开在线编译器,边学边练

1.队列的概念

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

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

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

41.png

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


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

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

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

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


411.png(图表示结点)


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

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

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

412.png(图表示队列设计)


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

//结点定义
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;
}


下一课:顺序队列二
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记