欢迎来到 黑吧安全网 聚焦网络安全前沿资讯,精华内容,交流技术心得!

数据结构之循环队列c语言实现

来源:本站整理 作者:佚名 时间:2016-11-06 TAG: 我要投稿

队列是一种先入先出的结构,数据从队列头出,队尾进。在linux内核中进程调度,打印缓冲区都有用到队列。
    队列有多种实现方式,可以用链表,也可以用数组。这里用数组来实现一个简单的循环队列。首先创建一个大小为8的队列如下,队列头尾指针指向同一块内存,
   

    当从队列尾部插入一个数据后变成下面的情形,为了便于处理,这里始终会浪费一个空间

    继续插入数据,直到出现以下情形,表示队列满了,

    接下来看一下出队的情形,从队列头出队3个元素,

    再添加三个元素后队列又变成满的了,
   

    在上面这种情况下面,如果再添加元素就会把队列头的元素覆盖掉,如下:

循环队列实现代码:
#include
#include
 
/* 循环队列大小*/
#define MAX 8    
 
typedef struct queue {
    int *que_array;
    int front;     //指向队首
    int rear;      //指向队尾
    int valid_cnt; //队列中有效的数据个数
    int total;      //队列总大小
} queue_t;
 
typedef enum {
    E_NONE     = 0,
    E_NOMEMORY = 1,
    E_FAIL     = 2,
} error_t;
 
void init_queue(queue_t *que)
{
    que->que_array = (int *)malloc(sizeof(int) * MAX);
    if (que->que_array == NULL) {
        printf("no mem\n");
        exit(-E_NOMEMORY);
    }
    que->front     = 0;
    que->rear      = 0;
    que->valid_cnt = 0;
    que->total     = MAX;
}
 
/* 判断队列是否已满 */
int is_full(queue_t *que)
{
    return (((que->rear + 1) % que->total) == (que->front));
}
 
/* 判断队列是否为空 */
int is_empty(queue_t *que)
{
    return (que->front == que->rear);
}
 
/* 元素入队 */
void entry_queue(queue_t *que, int data)
{
    if (is_full(que)) {
        printf("队列已满,添加后有可能会覆盖掉前面的元素 \n");
        que->front = ((que->front+1) % que->total);
    }
    que->que_array[que->rear % que->total] = data;
    que->rear = (que->rear+1) % que->total;
    que->valid_cnt++;
}
 
/* 元素出队 */
int del_queue(queue_t *que)
{
    int tmp;
    
    if (is_empty(que)) {
        printf("队列为空 \n");
        return -E_FAIL;
    }
    
    tmp = que->que_array[que->front % que->total];
    que->front = ((que->front+1) % que->total);
    que->valid_cnt--;
    
    return tmp;
}
 
int main(int argc, char *argv[])
{
    int tem_data,i;
    queue_t que;
    
    init_queue(&que);
 
#if 0
    for (i = 0; i
        entry_queue(&que, i + 1);

[1] [2]  下一页

【声明】:黑吧安全网(http://www.myhack58.com)登载此文出于传递更多信息之目的,并不代表本站赞同其观点和对其真实性负责,仅适于网络安全技术爱好者学习研究使用,学习中请遵循国家相关法律法规。如有问题请联系我们,联系邮箱admin@myhack58.com,我们会在最短的时间内进行处理。
  • 最新更新
    • 相关阅读
      • 本类热门
        • 最近下载