循环队列

循环队列

一、队列

       相信大家对队列是非常熟悉吧，初学数据结构就要背过“栈，先进后出；队列先进先出”。没错，队列就像我们每天排队去餐厅买饭一样，先到的在队伍的前面，买完饭就离开了，后到的排到队伍的最后面。

       说的专业一点，队列其实也是一种特殊的线性表结构，那么他特殊在哪呢？特殊在对表插入和删除操作，众所周知，我们普通的线性表或者链表，可以再表的任何位置进行插入和和删除节点的操作。而我们的队列呢，它只允许在表的前端，即队头（front）进行删除的操作，在表的后端，即队尾（rear）进行插入操作。

       建立顺序队列结构一般为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置（也就是说rear所指向的地址是没有元素的）。每次在队尾插入一个元素时，rear增1；每次在队头删除一个元素时，front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，称为空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。

二、循环队列

       为了解决上述中，普通顺序队列随着不断的插入删除操作，而使所存储队列的数组的后面部分已经满了，到达了数组的最后一个位置，而前面部分大部分因为删除操作还空着，这个问题。引入了循环队列，无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用。

三、循环队列的三种状态

1、队空状态

队列中没有元素，front和tear指向同一块地址，front=tear，如下图所示。

2、正常状态

正常状态即处于队空状态和队状态之间，此时队列中有元素但是没有满，如下图。

3、队满状态

此时队列中元素的个数为数组所分配的地址数-1，（因为tear所指向的位置不放元素）。

四、队列的相关计算

1、普通顺序队列中元素的个数 = tear – front ；

2、循环队列中元素的个数 = (tear-front + size) % size ;（size是数组长度）

3、元素入队时，其地址为rear，rear变为(rear + 1) % size;

4、元素出队时，front变为( front + 1)%size;

五、Java代码实现循环队列

/*

 * 以存储元素为int类的数组进行演示

 */

public class CycleQueue {

   //首先定义一个数组用来存储循环队列

   int size=10;

   int []queue = new int[size];

   //定义队首指针和队尾指针

   int front,tear = 0;

   //求队列中元素的个数

   int getNumber(){

      return (tear-front+size)%size;

   }

   //判读队列目前的状态,可以存储返回true,队满返回false

   boolean isNotFull(){

      if(getNumber()==size-1){

         System.out.println("处于队满状态");

         return false;

      }

      else{

         if(front==tear) System.out.println("处于队空状态");

         else System.out.println("处于普通状态");

         return true;

      }

   }

   //入队操作，success return true,else return false

   boolean enterQueue(int element){

      if(isNotFull()){

         queue[tear]=element;

         tear=(tear+1)%size;

         return true;

      }else return false;

   }

   //出队操作，删除并返回队首元素

   int deleateQueue(){

      if(front == tear)//如果队列是空的，返回null

         return (Integer)null;

      else {

         int temp = front;

         front = (front+1)%size;

         return queue[temp];

      }

   }

   public static void main(String[] args) {

      CycleQueue queue = new CycleQueue();

      int s[] = {1,2,3,4,5,6,7,8,9,10,11,12};

      for (int i = 0; i < s.length; i++) {

         queue.enterQueue(s[i]);

      }

      while(queue.getNumber()>0)

      System.out.print(queue.deleateQueue()+" ");

   }

}

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　----亓慧杰