循环队列的实现

作者: saviochen | 来源:发表于2017-07-16 16:58 被阅读53次

    一、概述

    由于队列有元素出列,front就向后移动,所以队列前面的空间就空了出来。为了更合理的利用空间,将队列的首尾相连接。这样当rear移动到LENGTH时,会再从0开始循环。

    那当什么时候队列满呢?当rear等于front的时候。可是队列为空的时候也是同样的条件,那不就没法判断了吗?

    又有人提出了这样的想法:牺牲一个存储空间,front前面不存数据,当rearfront前面的时候就是满了。当rearfront之前时,队列中剩余一个空间,有LENGTH - 1个元素,所以rear也为LENGTH - 1。这时就算是队列满了。如图:

    队满的判断条件应为:(rear+1)%LENGTH == front
    空的判断条件为rear == front

    二、入队

    #define LENGTH 100 
    typedef char TYPE;  
    
     typedef struct queue{  
         TYPE data[LENGTH];  
         int front;  
         int rear;  
         queue():front(0), rear(0){}
     }circular_queue; 
    
     void push_front(circular_queue *sq,TYPE data){  
         if((sq->rear+1)%LENGTH == sq->front){  
             printf("the queue is full\n");  
             exit(1);  
         }  
         sq->data[sq->rear] = data;  
         sq->rear= (sq->rear + 1) % LENGTH;  
     }  
    

    三、出队

     TYPE pop_rear(circular_queue *cq){  
         if(cq->rear == cq->front){  
             printf("the queue is empty!\n");  
             exit(1);  
         }    
         TYPE val = cq->data[cq->front];
         cq->front = cq->front + 1 == LENGTH ? (cq->front+1) % LENGTH : cq->front + 1;
         return val;  
     }  
    

    四、打印队列的内容

     void display(circular_queue *cq){  
         if(cq->front == cq->rear){  
             printf("the queue is empty!\n");  
             exit(1);  
         }      
         for(int i = cq->front; i != cq->rear;  i = (i+1) % LENGTH )
             printf("%c ", cq->data[i]);              
     }
    

    相关文章

      网友评论

        本文标题:循环队列的实现

        本文链接:https://www.haomeiwen.com/subject/quatkxtx.html