手机版
你好,游客 登录 注册
背景:
阅读新闻

C语言队列的实现

[日期:2015-03-19] 来源:Linux社区  作者:warren-liuquan [字体: ]

在C++ 里,队列可以直接使用 std::queue

队列的C语言实现如下:

queue.c

/**
* @brief 队列,顺序存储,循环队列.
*/
#include <stdlib.h>   /* for malloc(), free() */
#include <string.h>   /* for memcpy() */

#ifndef __cplusplus
typedef char bool;
#define false 0
#define true 1
#endif

typedef int queue_elem_t; // 元素的类型

/*
*@struct
*@brief 队列的结构体定义.
*@note
*/
typedef struct queue_t {
  int front;/* 队头 */
  int rear;/* 队尾 */
  int capacity; /* 容量大小,以元素为单位 */
  queue_elem_t *elems; /* 存放数据的内存块 */
}queue_t;

/**
* @brief 初始化队列.
* @param[out] q 队列结构体的指针
* @param[in] capacity 初始容量
* @return 无
*/
void queue_init(queue_t *q, const int capacity) {
  q->front = 0;
  q->rear = 0;
  q->capacity = capacity;
  q->elems = (queue_elem_t*)malloc(capacity * sizeof(queue_elem_t));
}

/**
* @brief 释放队列.
* @param[inout] q 队列对象的指针
* @return 无
*/
void queue_uninit(queue_t *q) {
  q->front = 0;
  q->rear = 0;
  q->capacity = 0;
  free(q->elems);
  q->elems = NULL;
}

/**
* @brief 判断队列是否为空.
* @param[in] q 队列结构体的指针
* @return 是空,返回 TRUE,否则返回 FALSE
*/
bool queue_empty(const queue_t *q) {
  return q->front == q->rear;
}

/**
* @brief 获取元素个数.
* @param[in] s 栈对象的指针
* @return 元素个数
*/
int queue_size(const queue_t *q) {
  return (q->rear - q->front + q->capacity) % q->capacity;
}

/**
* @brief 在队尾添加元素.
* @param[in] q 指向队列结构体的指针
* @param[in] x 要添加的元素
* @return 无
*/
void queue_push(queue_t *q, const queue_elem_t x) {
  if( (q->rear+1) % q->capacity == q->front)
   {
     // 已满,重新分配内存
    queue_elem_t* tmp = (queue_elem_t*)malloc(q->capacity * 2 * sizeof(queue_elem_t));
    if(q->front < q->rear)
     {
      memcpy(tmp, q->elems + q->front, (q->rear - q->front) * sizeof(queue_elem_t));
      q->rear -= q->front;
      q->front = 0;
    }
    else if(q->front > q->rear)
     {
      /* 拷贝 q->front 到 q->capacity 之间的数据 */
      memcpy(tmp, q->elems + q->front, (q->capacity - q->front) * sizeof(queue_elem_t));
      /* 拷贝 q->data[0] 到 q->data[rear] 之间的数据 */
      memcpy(tmp + (q->capacity - q->front), q->elems, q->rear * sizeof(queue_elem_t));
      q->rear += q->capacity - q->front;
      q->front = 0;
    }
    free(q->elems);
    q->elems = tmp;
    q->capacity *= 2;
  }
  q->elems[q->rear] = x;
  q->rear = (q->rear + 1) % q->capacity;
}


/**
* @brief 在队头删除元素.
* @param[in] q 队列结构体的指针
* @param[out] x 存放退出队列的元素
* @return 无
*/
void queue_pop(queue_t *q) {
  q->front = (q->front + 1) % q->capacity;
}

/**
* @brief 获取队首元素.
* @param[in] q 队列对象的指针
* @return 队首元素
*/
queue_elem_t queue_front(const queue_t *q) {
  return q->elems[q->front];
}

/**
* @brief 获取队首元素.
* @param[in] q 队列对象的指针
* @return 队首元素
*/
queue_elem_t queue_back(const queue_t *q) {
  return q->elems[q->rear - 1];
}

C++ 隐式类类型转化 Implicit Class-Type Conversions http://www.linuxidc.com/Linux/2013-01/78071.htm

C语言变长数组之剖析 http://www.linuxidc.com/Linux/2013-07/86997.htm

C语言需要注意的问题 http://www.linuxidc.com/Linux/2013-05/84301.htm

C语言位域的使用及其注意点 http://www.linuxidc.com/Linux/2013-07/87027.htm

C语言中简单的for循环和浮点型变量 http://www.linuxidc.com/Linux/2013-08/88514.htm

本文永久更新链接地址http://www.linuxidc.com/Linux/2015-03/115193.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款