一个能够自动扩容的顺序结构的队列 ArrQueue (GCC编译)。

 

1 /**  2 * @brief C语言顺序结构队列的实现  3 * @author wid  4 * @date 2013-10-30  5 *  6 * @note 若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢!  7 */  8   9 #include 
     
       10 #include 
      
        11  12 #define TRUE 1 13 #define FALSE 0 14  15 typedef struct Point2D 16 { 17     int x; 18     int y; 19 }ElemType;      //元素结构 20  21 typedef struct 22 { 23     ElemType **rear;    //队尾 24     ElemType *front;    //队头 25     int len;            //队列长度 26     int size;           //队列总容量 27 }ArrQueue;      //队列结构 28  29 //声明队列方法 30  31 ArrQueue *CreateQueue( int nLen );          //创建初始长度为 nLen 队列 32 void DestroyQueue( ArrQueue *pQueue );      //销毁队列pQueue 33 void ClearQueue( ArrQueue *pQueue );        //清空队列内元素 34 int GetLength( ArrQueue *pQueue );          //获取队列长度 35 int GetSize( ArrQueue *pQueue );            //获取队列总容量 36 int IsEmpty( ArrQueue *pQueue );            //检测队列是否为空 37 int GetHead( ArrQueue *pQueue, ElemType **pe );      //获取队头元素 38 int EnQueue( ArrQueue *pQueue, ElemType *pe );       //将元素插入到队尾 39 int DeQueue( ArrQueue *pQueue, ElemType **pe );      //将队头元素出队 40 void ForEachQueue( ArrQueue *pQueue, void (*func)(ElemType *pe) );      //从对尾到队头依次执行 func 41  42 //队列方法实现 43  44 /** 45 * @brief 创建初始长度为 nLen 的队列 46 * 47 * @param nLen 队列的初始长度 48 * 49 * @return 返回指向新创建的队列的指针 50 */ 51 ArrQueue *CreateQueue( int nLen ) 52 { 53     ArrQueue *pQueue = (ArrQueue *)malloc( sizeof(ArrQueue) ); 54     pQueue->rear = (ElemType **)calloc( nLen, sizeof(ElemType **) ); 55     pQueue->front = pQueue->rear[0]; 56     pQueue->len = 0; 57     pQueue->size = nLen; 58  59     return pQueue; 60 } 61  62 /** 63 * @brief 销毁队列 64 * 65 * @param pQueue 指向待销毁的队列的指针 66 */ 67 void DestroyQueue( ArrQueue *pQueue ) 68 { 69     free( pQueue->rear ); 70     free( pQueue ); 71  72     pQueue = NULL; 73 } 74  75 /** 76 * @brief 清空队列内元素 77 */ 78 void ClearQueue( ArrQueue *pQueue ) 79 { 80     pQueue->front = pQueue->rear[0]; 81  82     pQueue->len = 0; 83 } 84  85 /** 86 * @brief 获取队列长度 87 * 88 * @param 指向待获取长度的队列的指针 89 * 90 * @return 返回队列当前长度 91 */ 92 int GetLength( ArrQueue *pQueue ) 93 { 94     return pQueue->len; 95 } 96  97 /** 98 * @brief 获取队列总容量 99 *100 * @param pQueue 指向待获取容量的队列101 *102 * @return 返回队列当前总容量103 */104 int GetSize( ArrQueue *pQueue )105 {106     return pQueue->size;107 }108 109 /**110 * @brief 检测队列是否为空111 *112 * @param pQueue 指向待检测的队列113 *114 * @return 若为空, 则返回 TRUE, 否则返回 FALSE115 */116 int IsEmpty( ArrQueue *pQueue )117 {118     return pQueue->len == 0 ? TRUE : FALSE;119 }120 121 /**122 * @brief 获取队头元素123 *124 * @param pQueue 指向待获取队头元素的队列125 *126 * @param pe 指向接收元素的指针的指针127 *128 * @return 返回队头在队列中的位置(位置由 0 计起)129 */130 int GetHead( ArrQueue *pQueue, ElemType **pe )131 {132     if( pQueue->len == 0 )133     {134         *pe = NULL;135         return -1;136     }137 138     *pe = pQueue->rear[pQueue->len-1];139 140     return pQueue->len-1;141 }142 143 /**144 * @brief 将元素 pe 插入到队尾145 *146 * @param pQueue 指向待插入元素的队列147 * @param pe 指向待插入的元素148 *149 * @return 返回成功插入后队列的长度150 */151 int EnQueue( ArrQueue *pQueue, ElemType *pe )152 {153     ///检测是否需要扩容154     if( pQueue->len == pQueue->size )155     {   //需要扩容156         pQueue->rear = realloc( pQueue->rear, 2 * pQueue->size * sizeof(ElemType *) );157         pQueue->size = 2 * pQueue->size;158     }159 160     int i = 0;161     for( i = pQueue->len; i > 0; --i )162     {163         pQueue->rear[i] = pQueue->rear[i-1];164     }165     pQueue->rear[0] = pe;166     pQueue->front = pQueue->rear[pQueue->len];167 168     return ++pQueue->len;169 }170 171 /**172 * @brief 将队头元素出队173 *174 * @param pQueue 指向待出队的队列175 * @param pe 指向接收元素的指针的指针176 *177 * @return 成功出队则返回出队后队列的长度, 否则返回 -1178 */179 int DeQueue( ArrQueue *pQueue, ElemType **pe )180 {181     if( pQueue->len == 0 )182     {183         *pe = NULL;184         return -1;185     }186     *pe = pQueue->front;187     --pQueue->len;188     pQueue->front = pQueue->rear[pQueue->len-1];189 190     return pQueue->len;191 }192 193 /**194 * @brief 从队尾到队头每个元素一次执行 func195 *196 * @param pQueue 指向待处理的队列197 * @param  func 回调函数指针198 */199 void ForEachQueue( ArrQueue *pQueue, void (*func)(ElemType *pe) )200 {201     int i = 0;202     for( i = 0; i < pQueue->len; ++i )203     {204         func( pQueue->rear[i] );205     }206 }207 208 //测试209 void display( ElemType *pe )210 {211     printf( "(%d,%d) ", pe->x, pe->y );212 }213 214 int main()215 {216     ElemType t1 = {
   10, 20};217     ElemType t2 = {
   30, 40};218     ElemType t3 = {
   50, 60};219     ElemType t4 = {
   70, 80};220     ElemType t5 = {
   99, 99};221 222     ///测试 CreateQueue223     ArrQueue *pque = CreateQueue( 3 );224 225     ///测试入队226     EnQueue( pque, &t1 );227     EnQueue( pque, &t2 );228     EnQueue( pque, &t3 );229     EnQueue( pque, &t4 );230     EnQueue( pque, &t5 );231 232     ///测试 ForEachQueue233     ForEachQueue( pque, display );234 235     ///测试 IsEmpty、GetSize、GetLength236     if( IsEmpty( pque ) != TRUE )237         printf( "\n队列总容量:%d, 当前长度:%d\n", GetSize(pque), GetLength(pque) );238 239     ///测试全部出队240     printf( "\n测试全部出队:\n" );241     ElemType *p;242     while( DeQueue( pque, &p ) != -1 )243     {244         printf( "当前出队:(%d,%d), 剩余队列长为:%d\n", p->x, p->y, GetLength(pque) );245     }246 247     ///测试 ClearQueue248     printf( "\n再次入队2元素..\n" );249     EnQueue( pque, &t1 );250     EnQueue( pque, &t2 );251     ForEachQueue( pque, display );252     printf( "\n清空队列..\n" );253     ClearQueue( pque );254     printf( "队列总容量:%d, 当前长度:%d\n", GetSize(pque), GetLength(pque) );255 256     ///测试 GetHead257     printf( "\n再次入队2元素..\n" );258     EnQueue( pque, &t1 );259     EnQueue( pque, &t2 );260     ForEachQueue( pque, display );261     GetHead( pque, &p );262     printf( "\n获取队头元素:(%d,%d)\n", p->x, p->y );263     printf( "队列总容量:%d, 当前长度:%d\n", GetSize(pque), GetLength(pque) );264 265     ///销毁队列266     DestroyQueue( pque );267 268     return 0;269 }
      
     

 

测试运行:

 

若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢。