C语言实现循环队列
程序员文章站
2022-08-30 23:30:55
今日在处理数据存储的问题中,数据占用的空间较大,在询问之下,提及循环队列。 没有学习过的我,想想就是头大,只能慢慢从网上找资料,一个字母一个字母的敲,最后,还是慢慢的对队列有了一些理解 对于循环队列有几个操作: 1、初始化 2、入队 3、出队 4、遍历队列 5、判队列空,判队列满 具体如何实现,我会 ......
今日在处理数据存储的问题中,数据占用的空间较大,在询问之下,提及循环队列。
没有学习过的我,想想就是头大,只能慢慢从网上找资料,一个字母一个字母的敲,最后,还是慢慢的对队列有了一些理解
对于循环队列有几个操作:
1、初始化
2、入队
3、出队
4、遍历队列
5、判队列空,判队列满
具体如何实现,我会在下面通过代码实现
在对循环队列操作之前,先要建立队列结构体元素,
1 typedef struct queue 2 { 3 int * buf; 4 int front; 5 int rear; 6 }queue;
1、初始化
初始化,需要完成的工作是,为新建的队列分配内存空间,然后在将头尾指针置零
1 void initqueue(queue *queue_q) 2 { 3 queue_q->buf = (int *)malloc(sizeof(int)*buf_size); 4 if(queue_q->buf != null) //队列内存分配成功 5 { 6 queue_q->front = queue_q->rear = 0; //初始化头尾指针 7 } 8 9 }
2、入队
入队主要是将数据放到内存中,但是应该放到那一段内存,这就是一个问题了,
在此,在入队的时候,循环队列的头指针不做动作,尾指针向后偏移
实现代码如下:
其中的 buf_size 为循环队列的空间大小吗,但是实际能存储的数据字节数是(buf_size - 1)
#define buf_size 8
1 void in_queue(queue *queue_q , int value) 2 { 3 if(is_fullqueue(queue_q) != true) //队列未满 4 { 5 queue_q->buf[queue_q->rear] = value; 6 queue_q->rear = (queue_q->rear + 1)%buf_size ; //尾指针偏移 7 } 8 }
细心的人会注意到函数 is_fullqueue(queue_q) ,这是对循环队列进行判断,看是不是满了,应该队列的空间是有限的,对于满的队列,无法进行数据入队操作
具体函数如下:
1 unsigned char is_fullqueue(queue *queue_q) 2 { 3 if((queue_q->rear +1)%buf_size == queue_q->front) 4 { 5 return true; 6 }else 7 return false; 8 }
同样,存在一个判空函数,函数的原理是:头指针 = 尾指针
实现代码如下:
1 unsigned char isemptyqueue(queue *queue_q) 2 { 3 if(queue_q->front == queue_q->rear) 4 { 5 return true; 6 } 7 else 8 return false; 9 }
3、出队
出队是将头指针位置下的数据取出来,然后头指针偏移到被取数据的位置
代码实现如下:
1 void out_queue(queue *queue_q , int *value) 2 { 3 if(isemptyqueue(queue_q) != true) //队列未空 4 { 5 *value = queue_q->buf[queue_q->front]; 6 queue_q->front = (queue_q->front + 1)%buf_size ; 7 } 8 }
入队要判满,出队则要判空。
因为空的队列,没办法取数据
4、遍历队列
这就是一个简单的打印函数,没什么好说的
唯一需要注意的就是,遍历是出队操作,操作的是头指针,若头指针 = 尾指针,遍历完毕,循环队列为空
1 void bianli_a(queue *queue_q) 2 { 3 if(isemptyqueue(queue_q) != true) 4 { 5 int ret=queue_q->front; 6 while(ret != queue_q->rear) 7 { 8 printf("%d ",queue_q->buf[ret]); 9 ret=(ret+1)%buf_size; 10 } 11 } 12 }
下面是我学习循环队列的时候,写的代码,若有指教,请评论:
1 #include <stdio.h> 2 #include <malloc.h> 3 #include <stdlib.h> 4 5 #define true 1 6 #define false 0 7 #define buf_size 8 8 typedef struct queue 9 { 10 int * buf; 11 int front; 12 int rear; 13 }queue; 14 15 void initqueue(queue *queue_q) 16 { 17 queue_q->buf = (int *)malloc(sizeof(int)*buf_size); 18 if(queue_q->buf != null) //队列内存分配成功 19 { 20 queue_q->front = queue_q->rear = 0; //初始化头尾指针 21 } 22 23 } 24 25 //判空 26 unsigned char isemptyqueue(queue *queue_q) 27 { 28 if(queue_q->front == queue_q->rear) 29 { 30 return true; 31 } 32 else 33 return false; 34 } 35 36 //判满 37 unsigned char is_fullqueue(queue *queue_q) 38 { 39 if((queue_q->rear +1)%buf_size == queue_q->front) 40 { 41 return true; 42 }else 43 return false; 44 } 45 46 //入队 47 48 void in_queue(queue *queue_q , int value) 49 { 50 if(is_fullqueue(queue_q) != true) //队列未满 51 { 52 queue_q->buf[queue_q->rear] = value; 53 queue_q->rear = (queue_q->rear + 1)%buf_size ; //尾指针偏移 54 } 55 } 56 57 58 //出队 59 void out_queue(queue *queue_q , int *value) 60 { 61 if(isemptyqueue(queue_q) != true) //队列未空 62 { 63 *value = queue_q->buf[queue_q->front]; 64 queue_q->front = (queue_q->front + 1)%buf_size ; 65 } 66 } 67 68 void bianli_a(queue *queue_q) 69 { 70 if(isemptyqueue(queue_q) != true) 71 { 72 int ret=queue_q->front; 73 while(ret != queue_q->rear) 74 { 75 printf("%d ",queue_q->buf[ret]); 76 ret=(ret+1)%buf_size; 77 } 78 } 79 } 80 81 int main() 82 { 83 int val; 84 queue m; 85 initqueue(&m); 86 in_queue(&m,1); 87 in_queue(&m,2); 88 in_queue(&m,3); 89 bianli_a(&m); 90 printf("\n"); 91 out_queue(&m,&val); 92 bianli_a(&m); 93 return 0; 94 }
上一篇: MySQL 笔记整理(4) --深入浅出索引(上)
下一篇: 开启一段专属于你的Airbnb温情旅程