循环队列的常见操作

深藏阁楼爱情的钟 2022-05-26 01:26 246阅读 0赞

###### 与栈相比，队列我个人感觉简单一些，不过对于一般的队列，都是循环队列，这是为了防止内存的浪费，使为队列分配的内存可以循环使用，而且一般动态分配一个长度为n的循环队列的话，真正用来储存数据的只有n-1，因为要留一个空节点使队列尾的下标等于该空节点的下标，通过该空节点用来区分队满与队空，队满是判断条件是（rear+1）% len = front其中rear为队尾数据的下标，front为队头的下标，len为长度。下面是我在观看郝斌老师的视频后的总结，对原来郝斌老师的代码加上的释放队列空间以及清空队列数据的这两个操作 ######

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Queue{
        int len;
        int front;
        int rear;
        int * pBase;
    }Queue;
    
    void init(Queue *);//初始化队列
    void en_queue(Queue *,int);//入队
    void traverse_queue(Queue *);//遍历
    void out_queue(Queue *);//出队
    void destroy(Queue *);//释放
    void clear(Queue *);//重置
    
    int main(){
        Queue Q;
        printf("请输入您需要的循环队列的长度:\n");
        scanf("%d",&(Q.len));
        init(&Q);
        en_queue(&Q, 1);
        en_queue(&Q, 2);
        en_queue(&Q, 3);
        en_queue(&Q, 4);
        en_queue(&Q, 5);
        en_queue(&Q, 6);
        en_queue(&Q, 7);
        en_queue(&Q, 8);
        traverse_queue(&Q);
        out_queue(&Q);
        traverse_queue(&Q);
        out_queue(&Q);
        traverse_queue(&Q);
        out_queue(&Q);
        traverse_queue(&Q);
        out_queue(&Q);
        traverse_queue(&Q);
        destroy(&Q);
        printf("%p",Q.pBase);
        return 0;
    }
    
    void init(Queue* pQ){
        pQ->pBase = (int*)malloc(sizeof(int)*(pQ->len));
        pQ->front = 0;
        pQ->rear = 0;
    }
    
    void en_queue(Queue* pQ,int val){
        if ((pQ->rear+1)%pQ->len == pQ->front){
            printf("队列已满!%d入队失败\n",val);
        }else{
            pQ->pBase[pQ->rear] = val;
            pQ->rear = (pQ->rear+1) % pQ->len;
        }
        return;
    }
    
    void traverse_queue(Queue* pQ){
        if (pQ->rear == pQ->front){
            printf("队列为空!\n");
        }else{
            int i = pQ->front;
            while (i != pQ->rear) {
                printf("%d ",pQ->pBase[i]);
                i = (i+1) % pQ->len;
            }
        }
        printf("\n");
        return;
    }
    
    void out_queue(Queue *pQ){
        if (pQ->rear == pQ->front){
            printf("队列为空!\n");
        }else{
            int val = pQ->pBase[pQ->front];
            pQ->front = (pQ->front+1) % pQ->len;
            printf("出队的元素值为:%d\n",val);
        }
        return;
    }
    
    void destroy(Queue *pQ){
        pQ->len=-1;//因为pQ不是动态分配的，所以不要咬释放变量pQ的空间
        free(pQ->pBase);//释放动态分配的数组的空间
        return;
    }
    
    void clear(Queue *pQ){
        pQ->len = 0;
        pQ->front = 0;
        pQ->rear = 0;
        return;
    }

###### 注：个人认为循环队列的主要的一个巧妙的方法就是用取余这个方法，使循环队列的循环功能得以实现 ######