建设网站现在免费吗,辽宁海星建设集团有限公司网站,如何破解网站后台密码,制作网站方法#x1f493;博主csdn个人主页#xff1a;小小unicorn#x1f493; ⏩专栏分类#xff1a;C #x1f69a;代码仓库#xff1a;小小unicorn的学习足迹#x1f69a; #x1f339;#x1f339;#x1f339;关注我带你学习编程知识 栈 队列的介绍队列的概念#xff1a;队… 博主csdn个人主页小小unicorn ⏩专栏分类C 代码仓库小小unicorn的学习足迹 关注我带你学习编程知识 栈 队列的介绍队列的概念队列的结构 队列的实现创建队列初始化队列销毁队列队尾入队列对头出队列获取队列头部元素获取队列尾部元素检测队列是否为空获取队列中有效元素个数 总结 队列的介绍
队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表。队列遵守先进先出FIFOFirst In First Out的原则。
入队列队列的插入操作叫做入队列进行插入操作的一端称为队尾。
出队列队列的删除操作叫做出队列进行删除操作的一端称为队头。
队列的结构 队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
创建队列
首先我们需要创建一个结点类型类型包含了该结点的数据和指向下一结点的指针。
typedef int QDataType;typedef struct QListNode
{struct QListNode* next; //指针域QDataType data; //数据域
}QListNode;
其次队列与普通链表又有所不同普通链表只需要知道链表的头指针而队列的信息包括了队头和队尾所以我们需要再创建一个结构体用于存放队列的队头和队尾。
typedef struct Queue
{QListNode* head;//队头QListNode* tail;//队尾
}Queue;
初始化队列
我们需要一个初始化函数对刚创建的队列进行初始化。
//初始化队列
void QueueInit(Queue* pq)
{assert(pq);//起始时队列为空pq-head NULL;pq-tail NULL;
}销毁队列
因为队列中的每一个结点所占用的内存空间都是动态开辟的当我们使用完队列后需要及时释放队列中的每一个结点。
//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QListNode* cur pq-head;//接收队头//遍历链表逐个释放结点while (cur){QListNode* next cur-next;free(cur);cur next;}pq-head NULL;//队头置空pq-tail NULL;//队尾置空
}
队尾入队列
入队列也就是说申请一个新结点并将其链接到队尾然后改变队尾的指针指向。
需要注意的是若队列中原本无数据那么我们只需让队头和队尾均指向这个新申请的结点即可。
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QListNode* newnode (QListNode*)malloc(sizeof(QListNode));//申请新结点if (newnode NULL){printf(malloc fail\n);exit(-1);}newnode-data x; //新结点赋值newnode-next NULL; //新结点指针域置空if (pq-head NULL) //队列中原本无结点{pq-head pq-tail newnode; //队头、队尾直接指向新结点}else //队列中原本有结点{pq-tail-next newnode; //最后一个结点指向新结点pq-tail newnode; //改变队尾指针指向}
}
对头出队列
出队列也就是释放队头指针指向的结点并改变队头指针的指向。
若队列中只有一个结点那么直接将该结点释放然后将队头和队尾置空即可。
//队头出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq)); //检测队列是否为空if (pq-head-next NULL) //队列中只有一个结点{free(pq-head);pq-head NULL;pq-tail NULL;}else//队列中有多个结点{QListNode* next pq-head-next;free(pq-head);pq-head next; //改变队头指针指向}
}
获取队列头部元素
获取队列头部元素就是返回队头指针指向的数据。
//获取队列头部元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq)); //检测队列是否为空return pq-head-data; //返回队头指针指向的数据
}
获取队列尾部元素
获取队列尾部元素也就是返回队尾指针指向的数据。
//获取队列尾部元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq)); //检测队列是否为空return pq-tail-data; //返回队尾指针指向的数据
}
检测队列是否为空
检测队列是否为空也就是判断队头指针指向的内容是否为空。
//检测队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}获取队列中有效元素个数
队列中有效元素个数也就是队列中的结点个数。
我们只需遍历一下队列统计队列中的结点数并返回即可。
//获取队列中有效元素个数
int QueueSize(Queue* pq)
{assert(pq);QListNode* cur pq-head; //接收队头int count 0; //记录结点个数while (cur) //遍历队列{count;cur cur-next;}return count; //返回队列中的结点数
}
总结
初阶数据结构五六讲的是栈和队列它们都是特殊的线性表只不过对插入和删除操作做了限制。
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
对列(queue)是只允许在一端进行插入操作而在另一端进行删除操作的线 性表。
它们均可以用线性表的顺序存储结构来实现但都存在着顺序存储的一些弊端。因此它们各自有各自的技巧来解决这个问题。
对于栈来说如果是两个相同数据类型的栈则可以用数组的两端作栈底的方法来让两个栈共享数据这就可以最大化地利用数组的空间。
对于队列来说为了避免数组插入和删除时需要移动数据于是就引入了循环队列使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗使得本来插入和删除是O(n)的时间复杂度变成了O(1)。
它们也都可以通过链式存储结构来实现实现原则上与线性表基本相同如下图所示。 文章到这里就要告一段落了有更好的思路或问题的欢迎留言评论区。
