唤起“队列”的回忆

又来博客记录自己的学习心得了，嘿嘿嘿(^～^)

目录

队列的概念和结构：

队列的创建和初始化：

队列入栈：

队列出栈：

队列的销毁：

取队头和队尾数据：

结语：

---

队列的概念和结构：

只允许一端进行插入数据，在另一端删除数据，区别于栈的结构，它属于先进先出，类似于生活中的超市排队，同样的，我们会接触到两个名词入队和出队

入队：插入数据（插入数据的位置叫队尾）

出队：删除数据（删除数据的位置叫队头）

队列的创建和初始化：

创建：

首先插入数据的数据我们先创建它的结点数据和指向下一个结点的指针，把它放置在结构体中

typedef int QDataType;
typedef struct QNode
{struct QNode* next;//指针域QDataType data;//数据域
}QNode;

数据会放置在对列中，而队列有队头和队尾，用来删除和插入数据，在定义一个结构体进行包装

typedef struct Queue
{QNode* tail;//队尾QNode* head;//队头
}Queue;

队列的初始化：

我们将队头和队尾是空队列，置空即可

void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}

队列入栈：

首先创建一个结点，其次因为一开始我们将队列置为空，没有元素，所以将队列的队头和队尾指向新结点，如果有元素，我们只需进行尾插，再将尾指针移动位置，就完成了！

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新结点if (newnode == NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->data = x;//赋值数据if (pq->head == NULL)//队列为空{pq->tail = pq->head = newnode;}else{//尾插pq->tail->next = newnode;pq->tail = newnode;//改变尾指针指向}
}

队列出栈：

首先判断队列是否为空，然后可能存在只有一个结点的情况，则将头指针和尾指针全置为空，其余情况，先保存下一个结点的地址，将要删除的空间释放，然后改变头指针的指向方向

bool QueueEmpty(Queue* pq)
{return pq->head == NULL;
}
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//判断队列是否为空if (pq->head->next == NULL)//队列只有一个结点{free(pq->head);pq->head = pq->tail = NULL;//全部置空}else{Queue* Next = pq->head->next;//保存下一个结点的地址free(pq->head);pq->head = Next;}
}

队列的销毁：

循环遍历结点，然后释放每个结点额外开辟的空间，最后将头指针和尾指针置空

void QueueDestroy(Queue* pq)
{assert(pq);Queue* cur = pq->head;while (cur)//为空结束{Queue* Next = pq->head->next;//保存下一个结点地址free(cur);//释放结点cur = Next;//向后移动}pq->head = NULL;pq->tail = NULL;
}

取队头和队尾数据：

先判断队列是否为空，如果不为空，再返回队头和队尾数据，就OK了

QDataType GetFrontdata(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//检查队列是否为空return pq->head->data;//返回队头数据
}
QDataType GetBackdata(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//检查队列是否为空return pq->tail->data;//返回队尾数据
}

结语：

bye~，本节内容完毕