环形队列c语言代码

女爷i 2022-05-10 00:33 365阅读 0赞

这段代码实现了一个环形队列，数据类型可以根据自己的需要更改，这里预留的是指针类型。

ring\_queue.h

#ifndef _RINGQUEUE_
    #define _RINGQUEUE_
    
    #include <stdbool.h>
    #include <stdio.h>
    #include <string.h>
    
    // 队列包含的信息
    typedef struct queue
    {
        char **qu;      //用来存储全部的队列中的元素
        int head;     //队列头
        int tail;     //队尾
        int qlength;  //队列长度
        int maxsize;  //用来记录队列的最大容量
    
    }RQUEUE;
    
    RQUEUE  *rq_init ( RQUEUE *q, char **qu, int maxsize );
    bool rq_full (RQUEUE *q);
    bool rq_empty(RQUEUE *q);
    bool rq_front(RQUEUE *q, char **data);
    bool rq_back (RQUEUE *q, char **data);
    bool rq_push (RQUEUE *q, char *data);
    bool rq_pop  (RQUEUE *q, char **data);
    int rq_size  (RQUEUE *q);
    //------------------
    void rq_traverse(RQUEUE *q);
    
    #endif

ring\_queue.c

#include "ring_queue.h"
    
    #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
    #define  RQMAXSIZE  5
    #define  DMAXSIZE  8
    //  初始化队列
    RQUEUE  *rq_init ( RQUEUE *q, char **qu, int maxsize )
    {
        printf("rq_init\tin[%lu]\n",sizeof(RQUEUE));
    
        if (q == NULL) {
            printf("Memory alloc failure\n");
            return(NULL);
        }
    
    	q->qu = qu;
        if(NULL==q->qu)
        {
            printf("Memory allocation failure");
            return(NULL);        //退出程序
        }
        //分配完空间后，1开始队头队尾都在一起，因为没人，都为0长度也为0，
        q->head = 0;
        q->tail = 0;
        q->qlength = 0;
        q->maxsize = maxsize;
    
    	printf("rq_init\tout\n");
        return q;
    }
    
    // 判断空队列，长度为0则为空
    bool rq_empty (RQUEUE *q)
    {
        return  q->qlength == 0 ? true : false;
    }
    
    // 判断满队列，长度=最大容量为满
    bool rq_full (RQUEUE *q)
    {
        return q->qlength == q->maxsize ? true : false;
    }
    
    //入队
    bool rq_push (RQUEUE *q, char *data)
    {
    	printf("rq_push in %s\n", data);
        // 队列不满才插入
        if (rq_full(q)) {
            printf("队列满了，插入失败\n");
            return false;
    
        }else{
            //给队伍最尾添加赋值。
            //q->qu[q->tail] = num;
    		printf("%d \n",  q->tail);
    		char (*p)[DMAXSIZE] = (char(*)[DMAXSIZE])q->qu;
    		memcpy(p[q->tail], data, DMAXSIZE);
            //队尾向后移动一位，如果超过最大值，则从0开始，变成队尾
            q->tail = (q->tail +1)%q->maxsize;
            //队伍长度+1
            q->qlength++;
    		printf("rq_push\tout\n");
            return true;
        }
    
    }
    
    // 出队
    bool rq_pop (RQUEUE *q, char **data)
    {
    	printf("rq_pop\tin\n");
        // 队列有元素才能够删除
        if (rq_empty(q)) {
            printf("队列为空，删除失败\n");
            return false;
        }else{
    		char (*p)[DMAXSIZE] = (char(*)[DMAXSIZE])q->qu;
    		*data = p[(q->head)];
            //队头向后移动一位 超过最大值又重新 从0 开始计算
            q->head = (q->head +1)%q->maxsize;
    		
            // 队伍长度-1
            q->qlength--;
    		printf("rq_pop\tout\n");
            return true;
        }
    }
    
    //队列已有数据
    int rq_size(RQUEUE *q)
    {
    	return q->qlength;
    }
    
    //队列中头元素
    bool rq_front(RQUEUE *q, char **data)
    {
    	printf("rq_front\tin\n");
        // 队列有元素才能够删除
        if (rq_empty(q)) {
            printf("队列为空，查询失败\n");
            return false;
        }else{
    		char (*p)[DMAXSIZE] = (char(*)[DMAXSIZE])q->qu;
    		*data = p[(q->head)];
    		printf("rq_front\tout\n");
            return true;
        }
    }
    
    //队列中尾元素
    bool rq_back (RQUEUE *q, char **data)
    {
    	printf("rq_back\tin\n");
        // 队列有元素才能够删除
        if (rq_empty(q)) {
            printf("队列为空，查询失败\n");
            return false;
        }else{
    		char (*p)[DMAXSIZE] = (char(*)[DMAXSIZE])q->qu;
    		*data = p[(q->tail+q->maxsize-1)%q->maxsize];
    		printf("rq_back\tout\n");
            return true;
        }
    }
    
    // 遍历队列元素
    void rq_traverse(RQUEUE *q)
    {
    	printf("rq_traverse\tin\n");
    	char (*p)[DMAXSIZE] = (char(*)[DMAXSIZE])q->qu;
        // 在队列长度范围内 打印队列从队列头 到队列尾的元素
        for (int i=0 ; i<q->qlength; i++) {
          printf("%s ",  p[(q->head+i)%q->maxsize]);
        }
        printf("\n");
    	printf("rq_traverse\tout\n");
    }
    
    int main(int argc, const char * argv[]) {
        // insert code here...
    	printf("main\tin\n");
    
    	RQUEUE Q;
    	char a[RQMAXSIZE][DMAXSIZE];
    	printf("%ld\n", ARRAY_SIZE(a));
        rq_init(&Q, (char **)a, ARRAY_SIZE(a));
        if ( rq_empty(&Q)) {
            printf("空队列\n");
        };
    
    	char *c = NULL;
    	rq_front(&Q, &c);
    	printf("%s \n",  c);
    	rq_back (&Q, &c);
    	printf("%s \n",  c);
    	
    	char *aa = "1111111";
    
        rq_push(&Q, aa);
    	aa = "2222222";
        rq_push(&Q, aa);
    	aa = "3333333";
        rq_push(&Q, aa);
        if ( rq_empty(&Q)) {
            printf("空队列\n");
        };
    
    	rq_front(&Q, &c);
    	printf("%s \n",  c);
    	rq_back (&Q, &c);
    	printf("%s \n",  c);
    	aa = "444444";
        rq_push(&Q, aa);
    	aa = "555555";
        rq_push(&Q, aa);
    
    
        rq_pop(&Q, &c);
    	printf("rq_pop = %s \n",  c);
    	aa = "666666";
        rq_push(&Q, aa);
    	aa = "77777";
    	rq_push(&Q, aa);
    
        if (rq_full(&Q)) {
            printf("满队列\n");
        }
    
        rq_traverse(&Q);
    	
    	rq_front(&Q, &c);
    	printf("%s \n",  c);
    	rq_back (&Q, &c);
    	printf("%s \n",  c);
    
        return 0;
    }

编译查看运行结果gcc ring\_queue.c -o ring\_q

rt@ubuntu:~/ring_queue$ ./ring_q
    main	in
    5
    rq_init	in[20]
    rq_init	out
    空队列
    rq_front	in
    队列为空，查询失败
    (null) 
    rq_back	in
    队列为空，查询失败
    (null) 
    rq_push in 1111111
    0 
    rq_push	out
    rq_push in 2222222
    1 
    rq_push	out
    rq_push in 3333333
    2 
    rq_push	out
    rq_front	in
    rq_front	out
    1111111 
    rq_back	in
    rq_back	out
    3333333 
    rq_push in 444444
    3 
    rq_push	out
    rq_push in 555555
    4 
    rq_push	out
    rq_pop	in
    rq_pop	out
    rq_pop = 1111111 
    rq_push in 666666
    0 
    rq_push	out
    rq_push in 77777
    队列满了，插入失败
    满队列
    rq_traverse	in
    2222222 3333333 444444 555555 666666 
    rq_traverse	out
    rq_front	in
    rq_front	out
    2222222 
    rq_back	in
    rq_back	out
    666666