C语言中怎么实现双端队列这个数据结构

Python021

C语言中怎么实现双端队列这个数据结构,第1张

双端队列数据类型

typedef

struct

qnode

{

DataType

data

struct

qnode

*next

}LQNode

typedef

struct

{

LQNode

*front

LQNode

*rear

}LQueue

尾出队:首先判断队列是否为空,如为空则提示队列为空,如不为空则将队尾结点

赋给临时结点。将队尾结点的前驱指针赋给队列的队尾指针,再将队尾结

点的后继指针置空。最后返回临时结点或所需要的数据。

您好,您可以用双端堆。

只有十万个数据而已,数据量并不大。

不管是双端堆、红黑树、还是采用两个堆(一个最大堆一个最小堆),效率相差没多少。

建树或建堆的复杂度都是O(nlogn),等于排序的复杂度,并且删除都是O(logn)。

如果不用插入数据的话,可以用下面简单的方法

先对数组排序。

然后设置两个位置,int min = 0, max = n - 1其中n为元素个数,分别表示最小值和最大值的位置。

获取最大值是ary[max],获取最小值是a[min]。

删除最大值是max--,删除最小值是min++。

初始化复杂度O(nlogn),查找和删除都是O(1)