对于循环队列有几个操作:
1, 初始化
2, 入队
3, 出队
4, 遍历队列
5, 判队列空, 判队列满
具体如何实现, 我会在下面通过代码实现
在对循环队列操作之前, 先要建立队列结构体元素,
- typedef struct Queue
- {
- int * BUF;
- int front;
- int rear;
- }QUEUE;
1, 初始化
初始化, 需要完成的工作是, 为新建的队列分配内存空间, 然后在将头尾指针置零
- void initQueue(QUEUE *queue_q)
- {
- queue_q->BUF = (int *)malloc(sizeof(int)*BUF_SIZE);
- if(queue_q->BUF != NULL) // 队列内存分配成功
- {
- queue_q->front = queue_q->rear = 0; // 初始化头尾指针
- }
- }
2, 入队
入队主要是将数据放到内存中, 但是应该放到那一段内存, 这就是一个问题了,
在此, 在入队的时候, 循环队列的头指针不做动作, 尾指针向后偏移
实现代码如下:
其中的 BUF_SIZE 为循环队列的空间大小吗, 但是实际能存储的数据字节数是 (BUF_SIZE - 1)
- #define BUF_SIZE 8
- void In_Queue(QUEUE *queue_q , int value)
- {
- if(is_fullQueue(queue_q) != true) // 队列未满
- {
- queue_q->BUF[queue_q->rear] = value;
- queue_q->rear = (queue_q->rear + 1)%BUF_SIZE ; // 尾指针偏移
- }
- }
细心的人会注意到函数 is_fullQueue(queue_q) , 这是对循环队列进行判断, 看是不是满了, 应该队列的空间是有限的, 对于满的队列, 无法进行数据入队操作
具体函数如下:
- unsigned char is_fullQueue(QUEUE *queue_q)
- {
- if((queue_q->rear +1)%BUF_SIZE == queue_q->front)
- {
- return true;
- }else
- return false;
- }
同样, 存在一个判空函数, 函数的原理是: 头指针 = 尾指针
实现代码如下:
- unsigned char isemptyQueue(QUEUE *queue_q)
- {
- if(queue_q->front == queue_q->rear)
- {
- return true;
- }
- else
- return false;
- }
3, 出队
出队是将头指针位置下的数据取出来, 然后头指针偏移到被取数据的位置
代码实现如下:
- void out_Queue(QUEUE *queue_q , int *value)
- {
- if(isemptyQueue(queue_q) != true) // 队列未空
- {
- *value = queue_q->BUF[queue_q->front];
- queue_q->front = (queue_q->front + 1)%BUF_SIZE ;
- }
- }
入队要判满, 出队则要判空.
因为空的队列, 没办法取数据
4, 遍历队列
这就是一个简单的打印函数, 没什么好说的
唯一需要注意的就是, 遍历是出队操作, 操作的是头指针, 若头指针 = 尾指针, 遍历完毕, 循环队列为空
- void bianli_a(QUEUE *queue_q)
- {
- if(isemptyQueue(queue_q) != true)
- {
- int ret=queue_q->front;
- while(ret != queue_q->rear)
- {
- printf("%d",queue_q->BUF[ret]);
- ret=(ret+1)%BUF_SIZE;
- }
- }
- }
下面是我学习循环队列的时候, 写的代码, 若有指教, 请评论:
- #include <stdio.h>
- #include <malloc.h>
- #include <stdlib.h>
- #define true 1
- #define false 0
- #define BUF_SIZE 8
- typedef struct Queue
- {
- int * BUF;
- int front;
- int rear;
- }QUEUE;
- void initQueue(QUEUE *queue_q)
- {
- queue_q->BUF = (int *)malloc(sizeof(int)*BUF_SIZE);
- if(queue_q->BUF != NULL) // 队列内存分配成功
- {
- queue_q->front = queue_q->rear = 0; // 初始化头尾指针
- }
- }
- // 判空
- unsigned char isemptyQueue(QUEUE *queue_q)
- {
- if(queue_q->front == queue_q->rear)
- {
- return true;
- }
- else
- return false;
- }
- // 判满
- unsigned char is_fullQueue(QUEUE *queue_q)
- {
- if((queue_q->rear +1)%BUF_SIZE == queue_q->front)
- {
- return true;
- }else
- return false;
- }
- // 入队
- void In_Queue(QUEUE *queue_q , int value)
- {
- if(is_fullQueue(queue_q) != true) // 队列未满
- {
- queue_q->BUF[queue_q->rear] = value;
- queue_q->rear = (queue_q->rear + 1)%BUF_SIZE ; // 尾指针偏移
- }
- }
- // 出队
- void out_Queue(QUEUE *queue_q , int *value)
- {
- if(isemptyQueue(queue_q) != true) // 队列未空
- {
- *value = queue_q->BUF[queue_q->front];
- queue_q->front = (queue_q->front + 1)%BUF_SIZE ;
- }
- }
- void bianli_a(QUEUE *queue_q)
- {
- if(isemptyQueue(queue_q) != true)
- {
- int ret=queue_q->front;
- while(ret != queue_q->rear)
- {
- printf("%d",queue_q->BUF[ret]);
- ret=(ret+1)%BUF_SIZE;
- }
- }
- }
- int main()
- {
- int val;
- QUEUE m;
- initQueue(&m);
- In_Queue(&m,1);
- In_Queue(&m,2);
- In_Queue(&m,3);
- bianli_a(&m);
- printf("\n");
- out_Queue(&m,&val);
- bianli_a(&m);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2969818.html