欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

C语言实现循环队列

程序员文章站 2022-08-30 23:30:55
今日在处理数据存储的问题中,数据占用的空间较大,在询问之下,提及循环队列。 没有学习过的我,想想就是头大,只能慢慢从网上找资料,一个字母一个字母的敲,最后,还是慢慢的对队列有了一些理解 对于循环队列有几个操作: 1、初始化 2、入队 3、出队 4、遍历队列 5、判队列空,判队列满 具体如何实现,我会 ......

今日在处理数据存储的问题中,数据占用的空间较大,在询问之下,提及循环队列。

没有学习过的我,想想就是头大,只能慢慢从网上找资料,一个字母一个字母的敲,最后,还是慢慢的对队列有了一些理解
C语言实现循环队列

对于循环队列有几个操作:

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 }