3.8 队列的顺序表示和实现

3.5.2 队列的顺序表示和实现

• 队列的物理存储可以用顺序结构，也可用链式存储结构，相应地队列的存储方式也分为两种，即顺序队列和链式队列、

• 队列的顺序表示——————用一维数组base[MAXQSIZE]

  #define MAXQSIZE  100 // 最大队列的长度
  typedef  struct{
    	QElemType* base;   // 初始化的动态分配存储空间
    	int  front;        // 头指针
    	int  rear;			  //  尾指针
    	int  length;			//  用来记录队列所存储的元素个数 
  }SqQueue;
  

• 为什么需要使用循环队列？

  • 因为会发生上溢的情况下，会导致空间利用率不高，所以使用循环队列使空间利用率提高。所以我可以都上面的队列结构中指针进行修改，对队列中两个指针进行下标循环，即可解决问题。

• 解决思路

  • 将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时，若向量的开始的端空着，又可以从头使用空着的空间。当front为maxqsize时，也一样。这两个操作主要体现在入队和出队的操作当中。
  • 这里需要注意的是，就是两个指针的循环是利用mod运算来是实现。
  • 还有就是如何来表示队空和队满的情况，自己使用的是另外设置一个变量来进行记录队列的长度

初始化队列

• 【算法思想】初始情况下，front=rear=0,也就是说头指针和尾指针指向同一位置

• 【算法描述】

  Status InitQueue(&Q){
    	 Q.base=new QElemType[MAXQSIZE];   // 分配空间
    //Q.base=(QElemType)malloc(sizeof(QElemType));
    	 if(!Q.base)										 //  判断是否分配成功
         	exit(OVERFLOW);
    	 Q.rear=Q.base=0;
    	 Q.length=0;
  }
  

求队列的长度

• 【算法描述】

  int  QueueLength(Q){
    	return Q.length;
  }
  

循环队列入队操作

• 【算法思想】入队操作是在队尾进行操作。

• 【算法步骤】
  1、首先是需要判断队列是否已满，然后进行插入操作
  2、front指针所指向的位置空间进行赋值，值为参数所传递进来的值。
  3、将front指针进行移动一位，并且将length进行加一即可。

• 【算法描述】

  Status EnQueue(&Q,e){
    if(Q.Length==MAXQSIZE){
      	return  ERROR;
    }
    Q.base[Q.front]=e;
    Q.front=(Q.front+1)%MAXQSIZE;
    Q.length++;
    return OK;
  }
  

循环队列出队操作

• 【算法思想】出队操作是在队头进行操作

• 【算法步骤】
  1、首先是判断队列是否为空，然后进行下面的操作。
  2、将rear指针所指向的位置元素进行删除
  3、将rear指针进行移动一位，并且将length减一即可。

• 【算法描述】

   Status DeQueue(&Q,&e){
     	if(Q.length==0){
        	return ERROR;
      }
     	e=Q.base[Q.rear];
     	Q.rear=(Q.rear+1)%MAXQSIZE;
      Q.length++;
    	return OK; 
   }
  

取队头元素

• 【算法描述】

  SElemType GetHead(SqQueue Q){
    	// 首先是判断队列是否为空
    	if(Q.length==0){
        	return ERROR;
      }
    	return Q.base[Q.front];
  }