C語言隊列的實現

在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