嵌入式学习第三十二天！（队列）

本文主要是介绍嵌入式学习第三十二天！（队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 队列的定义：

    队列：是只允许一端进行数据插入，而另一端进行数据删除的线性表。（先进先出FIFO），如下图所示。

    队列的应用：缓冲区，即解决高速设备和低速设备数据交互的时候，速度不匹配问题

2. 存储结构：

    1. 顺序队列：循环队列

        空队列：初始两个指针都指向a1元素，如下图的左图所示；

        队列满的条件：(rear+1) % QueueSize == front，即牺牲空间来判断是否为满队列，如下图的右图所示。

        入队时：rear指针向尾部移动，front指针则依旧指向首元素，如下图的左图所示；

        出队时：front指针向下一个元素移动，释放出队元素，尾指针不变，如下图的右图所示。

        我们把头尾相接的顺序存储结构称为循环队列。

        1. 循环队列的定义：

typedef int DATA_TYPE;typedef struct que
{DATA_TYPE *pbase;int front;int rear;int maxSize;
}SQE_QUE;

        2. 循环队列的创建：

SQE_QUE *Create_Sqe_Queue(int maxSize)
{SQE_QUE *psqe = malloc(sizeof(SQE_QUE));if(psqe == NULL){perror("fail to malloc");return NULL;}psqe->pbase = malloc(maxSize * sizeof(DATA_TYPE));psqe->front = 0;psqe->rear = 0;psqe->maxSize = maxSize;return psqe;
}

        3. 判断循环队列是否为空或满：

int Is_Empty_Sqe_Queue(SQE_QUE *psqe)
{if(psqe->front == psqe->rear){return 1;}return 0;
}int Is_Full_Sqe_Queue(SQE_QUE *psqe)
{if(((psqe->rear + 1) % psqe->maxSize) == psqe->front){return 1;}return 0;
}

        4. 入循环队列：

int Push_Sqe_Queue(SQE_QUE *psqe, DATA_TYPE data)
{if(Is_Full_Sqe_Queue(psqe)){fprintf(stderr, "Queue full!\n");return -1;}else{psqe->pbase[psqe->rear] = data;psqe->rear = (psqe->rear+1) % psqe->maxSize;}return 0;
}

        5. 出循环队列：

int Pop_Sqe_Queue(SQE_QUE *psqe, DATA_TYPE *data)
{if(Is_Empty_Sqe_Queue(psqe)){fprintf(stderr, "Queue Empty!\n");return -1;}else{if(data != NULL){*data = psqe->pbase[psqe->front];}psqe->front = (psqe->front+1) % psqe->maxSize;}return 0;
}

        6. 读取循环队列队头的数据：

int Find_Front_Sqe_Queue(SQE_QUE *psqe, DATA_TYPE *data)
{*data = psqe->pbase[psqe->front];return 0;
}

        7. 清空循环队列：

void Clear_Sqe_Queue(SQE_QUE *psqe)
{psqe->front = psqe->rear = 0;return;
}

        8. 销毁循环队列：

void Destory_Sqe_Queue(SQE_QUE *psqe)
{free(psqe->pbase);free(psqe);return;
}

        9. 循环队列的遍历（为了方便验证队列是否正确）：

void Show_Queue(SQE_QUE *psqe)
{int i = psqe->front;while(i != psqe->rear){printf("%d ", psqe->pbase[i]);i = (i + 1) % psqe->maxSize;	}printf("\n");return;
}

    2. 链式队列：

        队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链式队列。

        1. 链式队列的定义：

typedef int DATA_TYPE;typedef struct node
{DATA_TYPE data;struct node *pnext;
}QUEUE_NODE;typedef struct list
{QUEUE_NODE *pfront;QUEUE_NODE *preal;int curlen;}QUEUE_LIST;

        2. 链式队列句柄的创建：

QUEUE_LIST *Create_Queue_List(void)
{QUEUE_LIST *plist = malloc(sizeof(QUEUE_LIST));if(plist == NULL){perror("fail to malloc");return NULL;}plist->pfront = NULL;plist->preal = NULL;plist->curlen = 0;return plist;
}

        3. 链式队列结点的创建：

QUEUE_NODE *Create_Queue_Node(DATA_TYPE data)
{QUEUE_NODE *pnode = malloc(sizeof(QUEUE_NODE));if(pnode == NULL){perror("fail to malloc");return NULL;}pnode->data = data;pnode->pnext = NULL;return pnode;
}

        4. 入队列（尾插法）：

int Is_Empty_Queue(QUEUE_LIST *plist)
{return plist->pfront == NULL;
}int Push_Queue_Link(QUEUE_LIST *plist, QUEUE_NODE *pnode)
{if(plist == NULL || pnode == NULL){return -1;}if(plist->pfront == NULL){plist->pfront = pnode;plist->preal = pnode;}else{plist->preal->pnext = pnode;plist->preal = pnode;}plist->curlen++;return 0;
}

        5. 出队列（头删法）：

int Pop_Queue_Link(QUEUE_LIST *plist, DATA_TYPE *data)
{if(Is_Empty_Queue(plist)){return 0;}QUEUE_NODE *ptmp = plist->pfront;if(ptmp->pnext == NULL){plist->pfront = NULL;plist->preal = NULL;if(data != NULL){*data = ptmp->data;}free(ptmp);}else{plist->pfront = ptmp->pnext;if(data !=  NULL){*data = ptmp->data;}free(ptmp);}plist->curlen--;return 0;
}

        6. 获取链式队列队头的数据：

int Get_Front_Quene(QUEUE_LIST *plist, DATA_TYPE *data)
{if(Is_Empty_Queue(plist)){return 0;}QUEUE_NODE *ptmp = plist->pfront;*data = ptmp->data;return 0;
}

        7. 清空链式队列：

void Clear_Queue(QUEUE_LIST *plist)
{QUEUE_NODE *ptmp = plist->pfront;while(plist->pfront != NULL){Pop_Queue_Link(plist, NULL);}return;
}

        8. 销毁链式队列：

void Destory_Queue(QUEUE_LIST *plist)
{Clear_Queue(plist);free(plist);return;
}

        9. 链式队列的遍历（为了方便验证队列是否正确）：

void Show_Queue(QUEUE_LIST *plist)
{QUEUE_NODE *ptmp = plist->pfront;while(ptmp != NULL){printf("%d ", ptmp->data);ptmp = ptmp->pnext;}printf("\n");return;
}

这篇关于嵌入式学习第三十二天！（队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---