数据结构——队列(浅谈队列)

在此介绍一下队列:

队列同栈一样是一种线性储存结构,具有以下性质:

  • 队列中的元素遵循“先进先出”原则(first in first out),简称FIFO结构
  • 在队尾添加元素,在队头删除元素

那么我们做几个定义:

  • 队头:允许删除元素的的一段为队头
  • 队尾:允许添加元素的一段为队尾
  • 入队:队列的插入操作
  • 出队:队列的删除操作

如果要使用数组作为底层数据结构构建队列的话,那么一般是要使用循环数组的。只有这样才能够防止空间的流失。

而ROS在此主要讲一讲用链表作为底层数据结构来构建队列:

几个函数操作:

  • queue <int> q;                    创建一个用于存放int类型数据的队列q(数据类型可任意更改)
  • q.push(i);                            向队列尾压入i
  • q.empty()                            检验队列q是否为空,如果为空则返回true,否则返回false
  • q.size()                               返回队列中元素的数量
  • q.front()                              返回队列头的元素,如果队列中预警没有元素则会RE

拓展讲一下优先队列(priority_queue):

优先队列的函数操作与队列的唯一不同就是定义一个优先队列时的queue变成了priority_queue

优先队列能够按照特定的规则动态地对队列中的元素进行排序,是堆的实现形式。

优先队列默认为小根堆(从大到小进行排序,队头为最大的元素),而我们可以有两种方式使小根堆变成大根堆:

  1. priority_queue < int,vector<int>,greater<int> >则定义了一个大根堆(greater可以变成less则变成小根堆)
  2. 重载运算符
原文地址:https://www.cnblogs.com/robertspot/p/12380548.html