循环队列的队空与队满的条件

48 阅读 0 评论 32 点赞

我是靠谱客的博主英俊小伙，最近开发中收集的这篇文章主要介绍循环队列的队空与队满的条件，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

为了方便起见，约定：初始化建空队时，令
      front=rear=0,
  当队空时：front=rear
  当队满时：front=rear 亦成立
  因此只凭等式front=rear无法判断队空还是队满。有两种方法处理上述问题：
    （1）另设一个标志位以区别队列是空还是满。
    （2）少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：
  队空时： front=rear
  队满时： (rear+1)%maxsize=front

front指向队首元素，rear指向队尾元素的下一个元素。

[cpp]  
   view plain 
   copy 
   print 
   ? 
    
   
 /  
 //   
 // author: kangquan2008@csdn  
 //  
 /  
 #include <stdio.h>  
 #include <stdlib.h>  
 #include <stdbool.h>  
   
 #define QUEUE_SIZE 10  
 #define EN_QUEUE 1  
 #define DE_QUEUE 2  
 #define EXIT     3  
   
 typedef int    Item;  
 typedef struct QUEUE{  
   
     Item * item;  
     int front;  
     int tear;  
   
 }Queue;  
   
 int init_queue(Queue * queue)  
 {  
     queue->item = malloc(QUEUE_SIZE * sizeof(Item));  
     if(!queue->item)  
     {  
         printf("%sn","Alloc failed,not memory enough");  
         exit(EXIT_FAILURE);  
     }  
   
     queue->front = queue->tear = 0;  
   
     return 1;  
 }  
   
 int en_queue(Queue * queue, Item item)  
 {  
     if((queue->tear+1) % QUEUE_SIZE == queue->front)  
     {  
         printf("%sn","The queue is full");  
         return -1;  
     }  
   
     queue->item[queue->tear] = item;  
     queue->tear = (queue->tear + 1) % QUEUE_SIZE;  
   
     return 1;  
 }  
   
 int de_queue(Queue * queue, Item * item)  
 {  
     if(queue->front == queue->tear)  
     {  
         printf("%sn","The queue is empty");  
         return -1;  
     }  
   
     (*item) = queue->item[queue->front];  
     queue->front = (queue->front + 1) % QUEUE_SIZE;  
   
     return 1;  
 }  
   
 int destroy_queue(Queue * queue)  
 {  
     free(queue->item);  
 }  
   
 int main()  
 {  
     Queue que;  
     init_queue(&que);  
     int elem;  
     bool flag = true;  
     while(flag)  
     {  
         int choice;  
         printf("1 for en_queue,2 for de_queue,3 for exitrnplease input:");  
         scanf("%d",&choice);  
   
         switch((choice))  
         {  
             case EN_QUEUE:  
                 printf("input a num:");  
                 scanf("%d",&elem);  
                 en_queue(&que,elem);  
                 break;  
             case DE_QUEUE:  
                 if(de_queue(&que,&elem) == 1)  
                     printf("front item is:%dn",elem);  
                 break;  
             case EXIT:  
                 flag = false;  
                 break;  
             default:  
                 printf("error inputn");  
                 break;  
         }  
     }  
   
     destroy_queue(&que);  
     return 0;  
 }  