数据结构（六）循环队列的基本操作入队退队

约定不等于承诺〃 2022-08-09 06:46 266阅读 0赞

**队列特性：先进先出（FIFO)——先进队列的元素先出队列。来源于我们生活中的队列（先排队的先办完事）。**  
采用空闲一个位置的方式，即N个元素空间的循环队列最多只能存放N-1个有效元素。这也是大多数教材的做法。

1.  队列有下面几个操作：

void init(PQUEUE);//初始化 
    void in(PQUEUE);//入队 
    void out(PQUEUE,int *);//出队 
    void printQueue(PQUEUE);//打印队列 
    bool is_empty(PQUEUE);//队列是否为空 
    bool is_full(PQUEUE);//队列是否满

1) 循环队列初始化：front=rear=0；  
2）入队操作：rear=(rear+1)%size;  
3）出队操作：front=(front+1)%size;  
4）判断是否为空队列：front==rear；  
5）判断队列是否已满：front=(rear+1)%size；  
6）遍历队列各元素。

#include <stdio.h>
    #include <malloc.h>
    //静态队列,循环队列 
    typedef struct Queue{
        int * base; 
        int front;//队首
        int rear;//队尾 
        int len;//队列长度 
    }QUEUE,*PQUEUE;
    void init(PQUEUE);//初始化 
    void in(PQUEUE);//入队 
    void out(PQUEUE,int *);//出队 
    void printQueue(PQUEUE);//打印队列 
    bool is_empty(PQUEUE);//队列是否为空 
    bool is_full(PQUEUE);//队列是否满 
    int main(void){
        QUEUE q;
        int val; 
        init(&q);
        in(&q); 
        in(&q); 
        in(&q); 
        printQueue(&q); 
        out(&q,&val); 
        printf("出队的元素是:%d\n",val); 
        printQueue(&q);
        return 0; 
    } 
    //队列初始化 
    void init(PQUEUE pQ){
        int len;
        printf("请输入需要存储几个元素:");
        scanf("%d",&len); 
        pQ->base =(int*)malloc( sizeof(int)*(len+1) );//因为队尾是最后一个元素的下一个元素，所以要加一 
        if(pQ->base == NULL){
            printf("初始化,分配内存失败."); 
            exit(-1); 
        } 
        pQ->front = pQ->rear = 0; 
        pQ->len = len; 
    }
    //入队,队首总是指向第一个元素,队尾总是指针最后一个有效元素的下一个元素（一般为NULL） 
    void in(PQUEUE pQ){
        if(is_full(pQ)){
            printf("该队列已满，不能入队\n");
            return; 
        } 
        int val;
        printf("请输入值:");
        scanf("%d",&val);
        pQ->base[pQ->rear] = val;
        pQ->rear = (pQ->rear+1)%pQ->len; 
    }
    //出队 
    void out(PQUEUE pQ,int * pVal){
        if( is_empty(pQ) ){
            printf("该队列为空,不能出错\n");
            return; 
        } 
        *pVal = pQ->base[pQ->front];
        pQ->front = (pQ->front+1)%pQ->len; 
    }
    //打印队列 
    void printQueue(PQUEUE pQ){
        if( is_empty(pQ) ){
            printf("该队列为空\n");
            return; 
        } 
        printf("队列的元素为："); 
        int t = pQ->front; 
        while(t != pQ->rear){
            printf("%d ",pQ->base[t]);
            t = (t+1)%pQ->len; 
        } 
        printf("\n"); 
    } 
    //判断队列是否为空 
    bool is_empty(PQUEUE pQ){
        return pQ->front == pQ->rear; 
    } 
    //判断队列是否已满 
    bool is_full(PQUEUE pQ){
        return (pQ->rear+1)%pQ->len == pQ->front; 
    }