带m开头的网站怎么做,建筑公司网站页面图片,网站前台模板怎么替换,龙岗区建设局网站一、简而言之在百度百科里面摘取了一段关于队列(queue)的介绍#xff1a;队列是一种特殊的线性表#xff0c;特殊之处在于它只允许在表的前端(front)进行删除操作#xff0c;而在表的后端(rear)进行插入操作#xff0c;和栈一样#xff0c;队列是一种操作受限制的线性表。…一、简而言之在百度百科里面摘取了一段关于队列(queue)的介绍队列是一种特殊的线性表特殊之处在于它只允许在表的前端(front)进行删除操作而在表的后端(rear)进行插入操作和栈一样队列是一种操作受限制的线性表。二、一般而言这里是对就一般而言 队列的结构操作方法等的表述。2.1 结构以下为队列的结构示意图2.2 实现分类一般来说队列有两类实现方式数组实现暂时将其称为有限队列根据创建队列是传入的size创建相应size的数组来作为队列的载体一般都会以循环的方式利用数组也可看作循环队列。优点预先分配好内存在入队和出队过程中不会重新分配内存有一定时间上的优势。缺点因必须预先分配好内存所以存在内存空间浪费的问题(比如分配了10个元素但很多时候却只有5个有效元素)元素数目固定不够灵活。链表实现可称其为链式队列使用链表来实现队列理论上这样的队列可以无限延伸当然根据实际需要可以人为的限制队列长度让其表现的和数组实现方式差不多。优点 无需预先分配内存所以不存在空间浪费的问题(虽然会多一个指针域但也基本可以接受)队列长度可限制也可不限制较为灵活。缺点 入队出队分别需要分配和释放元素节点在时间上会略微慢于数组实现。总的来说在可以确定队列长度最大值的情况下建议用循环队列如果你无法预估队列的长度时则用链队列。2.3 基本操作这里主要指的是队列的入队(enqueue)与出队(dequeue)对于链式队列来说其入队和出队也就是链表的尾部插入与移除头部节点这里就不多说主要说一下以数组实现的循环链表的具体实现(其中head和tail都是表示数组的下标)。入队 如上面的循环队列示意图入队操作需要先判断tail节点的下一个位置是否是head如果是就表示队列已满无法入队如果不是那就可以入队也即是将元素放入tail的下一个位置最后将tail加一(也就是指向最终的尾元素)其伪代码如下/** 取余保证当tail size - 1 时转回到0 */int tail (queue-tail 1) % queue-size;if (tail queue-head){ /** 此处这样写是因为正常情况下非满的情况多于满了的情况这样写可以稍微的加快点执行速度 */queue-elems[queue-tail] elem;queue-tail tail;}else /** 此时队列已满 */{printf(the queue is full!);}出队 先判断 tail 和head是否相等如果相等就比较队列已空无元素可出不等则表示非空。此时需要取出head对于位置的元素然后将head加1(当然为了能够在head 增加到数组尾部时能够转回到首部那么这里其实需要 将head加1与队列的size取余再赋值给head)其伪代码如下elem_type elem elem_null; /** 初始化元素 */if(queue-tail queue-head) /** 判断队列不为空 */{/**这样写的作用与上一段伪代码的作用是一样的 */elem queue-elems[queue-head];/** 取余保证当head size - 1 时转回到0 */queue-head (queue-head1) % queue-size;}else /** 此时队列已空 */{printf(the queue is empty \n);}return elem;三、和盘托出这里就是我的具体实现。目前我实现的是无限队列(链式队列 )链表就是前一章实现的list。其头文件如下#ifndef __TINY_QUEUE_H__#define __TINY_QUEUE_H__#include general_type.h#ifdef __cplusplusextern C {#endif/***************************************************************************** macro declaration****************************************************************************//***************************************************************************** data structure declaration****************************************************************************//** the callback function for free item */typedef void (*tfQueueItemFreeFunc_t)(void* item);/***************************************************************************** API declaration****************************************************************************//***brief create a queue instance**param none**return success: queue instance handle, fail: NULL.*see**/G_API GPHD tfQueueCreate(void);/***brief destroy a queue instance**param queue [in] pointer to queue instance**return none.*see**/G_API void tfQueueDestroy(GPHD queue);/***brief clear(remove and free) all item in queue**param queue [in] pointer to queue instance*param item_free [in] callbck function for free item.**return none.*see**/G_API void tfQueueClear(GPHD queue, tfQueueItemFreeFunc_t item_free);/***brief append a item to current queue.**param queue [in] pointer to queue instance*param item [in] pointer new item.**return success: GTRUE, fail: GFALSE*see**/G_API GBOL tfQueueEnQueue(GPHD queue, void* item);/***brief pop a item from current queue**param queue [in] pointer to queue instance**return success: item handle, fail: NULL.*see**/G_API void *tfQueueDeQueue(GPHD queue);/***brief get the count of item in current queue.**param queue [in] pointer to queue instance**return how many item in current queue.*see**/G_API GU32 tfQueueLength(GPHD queue);#ifdef __cplusplus}#endif#endif //end of __TINY_QUEUE_H__其源文件如下#include#include general_macro.h#include tiny_queue.h#include tiny_list.h#include vos_mem.h/***************************************************************************** macro declaration****************************************************************************/#define LOGE printf#define LOGD printf#define LOGW printf/***************************************************************************** data structure declaration****************************************************************************//** data structure for item */typedef struct my_queue_item_s{tiny_list_node_t node;void* data;}my_queue_item_t;/** data structure for queue */typedef struct my_queue_s{tiny_list_t items;}my_queue_t;/***************************************************************************** inner API define****************************************************************************/static my_queue_item_t* tqItemNew(void* data){my_queue_item_t* item (my_queue_item_t*)memAlloc(sizeof(my_queue_item_t));if (item){item-data data;}return item;}/***************************************************************************** API define****************************************************************************/GPHD tfQueueCreate(void){my_queue_t* mq (my_queue_t*)memAlloc(sizeof(my_queue_t));if (mq){memset(mq, 0, sizeof(*mq));tfListInitialize((mq-items), memFree);}else{LOGE(alloc queue instance failed\n);}return mq;}void tfQueueDestroy(GPHD queue){if (queue){my_queue_t* mq (my_queue_t*)queue;tiny_list_t* tl (mq-items);GU32 left_count tfListCount(tl);if (left_count 0){LOGW(here have: %d items in queue, its maybe lead to memory leak\n, left_count);}tfListClear(tl);memFree(queue);}}void tfQueueClear(GPHD queue, tfQueueItemFreeFunc_t item_free){if (queue){my_queue_t* mq (my_queue_t*)queue;tiny_list_t* tl (mq-items);if (item_free){tiny_list_node_t* node tfListFront(tl);while (node){my_queue_item_t* mqi (my_queue_item_t*)node;item_free(mqi-data);node node-next;}}else{LOGW(item_free is NULL, so here wouldnt free item, it maybe lead to memory leak\n);}tfListClear(tl);}}GBOL tfQueueEnQueue(GPHD queue, void* item){GBOL ret GFALSE;if (queue){my_queue_t* mq (my_queue_t*)queue;tiny_list_t* tl (mq-items);my_queue_item_t* mqi tqItemNew(item);GCHECK(mqi);tfListPushBack(tl, (tiny_list_node_t*)mqi);/** todo, is need check push to list is successed ?? */ret GTRUE;}return GFALSE;}void *tfQueueDeQueue(GPHD queue){void* item NULL;if (queue){my_queue_t* mq (my_queue_t*)queue;tiny_list_t* tl (mq-items);my_queue_item_t* node (my_queue_item_t*)tfListFront(tl);if (node){item node-data;tfListPopFront(tl); /** remove head node from list */}}return item;}GU32 tfQueueLength(GPHD queue){GU32 ret 0;if (queue){my_queue_t* mq (my_queue_t*)queue;ret tfListCount((mq-items));}return ret;}其中的 vos_mem.h是我封装的虚拟系统接口中关于memory操作的部分以作跨平台使用以上源文件中使用到的memAllocmemFree可以简单的理解为标准的malloc和free。general_macro.h可以去看第九章。四、扪心自问这里只是实现了无限队列的情况如果后续在开发的过程中还需要有限队列的话再添加相关接口与实现代码。
