数据结构【队列】

定义：

  一种可以实现“先进先出”的存储结构，比较像在火车站买票。

分类：

  1、链式队列：内部属于链表，对链表的操作做一些限制，就是链式队列   2、静态队列：内部属于数组     静态队列通常都必须是循环队列

循环队列释义：

  1、静态队列为什么必须是循环队列如果按照传统的数组来表示插入和删除的话应该是     这样的：有一个队列一共有6个，队列的实际元素只有5个，rear指向的是无效的元素

图1.png

  如果现在要把“m”删除掉，那么就必须把front指针往上加

  删除后的结果如下图：

图2.png

  如果要把“a”删除的话，也是一样的，需要把front往上加。

  那么这样的话之前的空间就无法再次利用了，如果一个队列这么实现的话就会浪费

  大量内存，最后导致内存占用过高，程序崩溃。

  假设队列是这样的：

图3.png

   想要添加一个“毛”字，那么rear势必也要往上加，加以后是这样的

图4.png

  rear再往上加，如果是传统的数组的话，这个时候rear已经越界了，那么这样做肯定

  是不行的。

所以综上所述，静态队列必须是循环队列。

  循环队列表示：

图5.png

  当需要新增一个“毛”字的时候，让rear指向第一个元素，那么这个时候就

  可以把“毛”字添加进来了。

  如果我们还需要添加一个“争”字，是不是rear再加1就可以了，那么添加后是这样的

图6.png

  假设现在front指向了数组的最后一个元素，我们把“毛”字给删除掉

图7.png

  循环队列的话，把front只需要指向第一个元素就好了，这样就形成了循环队列。如图：

图8.png

  2、循环队列需要几个参数来确定     需要两个参数来确定   3、循环队列各个参数的含义     两个参数不同场合有不同的含义     1、队列初始化front、rear的值都是零     2、队列非空front代表的是队列的第一个元素，rear代表的是       最后一个有效元素的下一个元素     3、队列空front和rear的值相等，但是不一定是零   4、循环队列入队伪算法

入队伪算法.png

  5、循环队列出队伪算法

出队伪算法.png

  6、如何判断循环队列是否为空

    当front与rear相等的时候就为空

  7、如何判断循环队列是否已满

判断队列是否满.png