注意了,这里说的队列并不是STL容器库里面的queue。
像链表、队列、栈、二叉树其实是一种数据结构,而vector、queue、set等是容器,是不同的概念。
队列的实现可以有很多方式,可以用结构体内储存数组来实现,也可以用结构体内储存结构体来实现,我们这里选择后者。
如何实现一个队列
1.声明一个队列节点结构体
//和链表相同,一个队列包含多个节点,包含这些节点的结构体就是一个队列了
struct QueueNode{
DataType val; //创建一个整型的数据,当然也可以创建其他类型的数据
QueueNode* next;
};
2.声明一个队列结构体
struct Queue{
QueueNode* head;
QueueNode* tail;
int size;
};
这个时候我们已经具备了一个队列的雏形,接下来继续操作,让他成为一个真正的队列。
3.初始化队列
void QueueInit(Queue*q) //因为初始化的对象是列表,所以传入指向列表的指针
{
assert(q); //输入的q不能是空指针
q->head = NULL;
q->tail = NULL;
q->size = 0;
};
4.实现队列的尾插(入队)
void Push(Queue*q, Datatype x)
{
assert(q);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if(newode == NULL)
{
perror("malloc failed!");
exit(0);
}
newnode->next = null;
newnode->val = x;
if(q->tail == null) //尾部为空,说明该队列是空队列
{
q->tail = newnode; //创建一个新节点,该节点成为队列的尾部
q->head = q->tail;
}
else
{
q->tail->next = newnode; //创建一个新的节点,原尾部指向新节点
q->tail = q->tail->next; //新节点成为新的尾部
}
q->size++;
}
这样下来,我们的队列就有了尾插功能,接下来加入头删功能。
5.实现队列的头删(出队)
void Pop(Queue* q)
{
assert(q);
assert(q->size != 0);
QueueNode* next = q->head->next; //创建一个指向头节点的下一位的指针1
free(q->head);
q->head = next; //指针1成为队列新的头
q->size--;
}
到此,我们的队列又有了头删功能。
6.获取头元素和尾元素
//首元素
DataType Front(Queue*q) //DataType是前面队列节点声明的数据类型
{
assert(q);
assert(q->head && q->tail); //不能为空
return q->head->val;
}
//尾元素
DataType Back(Queue*q)
{
assert(q);
assert(q->head && q->tail); //不能为空
return q->tail->val;
}
自此,我们就得到了一个队列。
大家如果觉得麻烦,直接学习STL库中的Queue容器的使用就可以了。
标签:head,队列,笔记,assert,tail,C++,QueueNode,节点 From: https://blog.csdn.net/weixin_52133252/article/details/141592692