数据结构-队列
队列也是一种和限定的线性表,他和栈正好相反,同样这和数据结构在计算机的作用也是非常大的,我们可以通过队列发现好多其他的数据结构和他有关系,同样在我们的生活中也会发现好多这样的,最好理解的是,我们在吃饭时排队,这就是经典的队列.下面来讲解他的基本思想;
队列的定义及分类
- 01
队列的定义:是一种限定的线性表.它只允许在表的一端插入元素,而在另一端删除元素,我们可以想下生活中的排队,又分队头和队尾.在计算机的一个例子:操作系统中的作业排队就是队列实现的.
- 02
队列的分类:同样队列也分两种存储结构.它们是:顺序结构和链式结构; 我们先讲下链队列:它分:数据,队头指针,队尾指针,这时我闪可以想下在讲解线性表的时候,我们采用尾插法就是在这里体现的,
- 03
下面来讲解链队的基本操作:入队,出队,入队时我们要做的是要防止它的溢出,其他它的溢出就是你的电脑内存用完了,没有资源可以用了,出队的操作:我们要判断的是当里面没有元素了我们就不能进行出队操作了.
- 04
链表的顺序结构:我们习惯上说它是循环的队列,因为我们如果设计成直线性的话,就无法判断队满和队空的条件.就会出现我们说的假溢出,具体的可以看下面的图片讲解;
- 05
循环队列的入队和出队操作;在这部分我们遇到的困难就是边界的条件.我们怎么来判断何时是满的,何时是空的,队头和队尾相等了也就是可以判断了,(rear+1)mod MAXSIZE==front 这个是队满的状态,rear==front是为队空的状态.
队列的应用
- 01
可以用队列实现打印杨辉三角形,我在这时用的是链队实现的,当然出可以用顺序队列实现,实现的基本原理就是第i行的数需要第i-1行的操作.比如第6行生成第7行有四个步骤:1 第7行的第一个元素1入队, 2 第7行中间5个元素入队,3 第6行最后一个元素1入队,4 第7行最后一个元素1入队
- 02
下面的给出的C语言的实现.当然你也可以用其他的语言实现,但是原理都是相同的.