这样的消息队列如何出列？

//以链表形式存储数据，容量有限
struct _linkTable
{
	int					ntype;		//类型
	char				data[255];	//数据
	struct _linkTable	*pNext;
}TLinkTable;

//插入队列
int Push(TLinkTable stLinkTable )
{
	//插入到队列尾
}

//返回队首第一个元素
int Pull()
{

}

//返回指定类型的第一个元素，失败返回0
int Pull(int ntype)
{
//如何快速找到并出列??
}

队列的顺序不能打乱。
或者有其它实现的方法？

9 个解决方案

#1

楼主似乎没有理解不同数据结构的适用范围，链表这种数据结构，决定了查找一定是线性的，不可能更快。如果需要更快的查找，建议更换为哈希表

#2

引用 1 楼 jiqiang01234 的回复:

楼主似乎没有理解不同数据结构的适用范围，链表这种数据结构，决定了查找一定是线性的，不可能更快。如果需要更快的查找，建议更换为哈希表

我这个功能是Linux的消息队列是一样的，只是考虑到跨平台不想用系统api
因为队列里面有很多消息，ntype是一样的。用哈希的话查找快一点点，入队比较麻烦。

#3

可以用glib库，包含了常用的数据结构，而且跨平台。如果是c++就无所谓了，STL本身就跨平台

#4

链表只能顺序查找，不用哈希的话可以采用数组来存，这样可以使用折半查找（前提是入队时要排序，如果不排序，也只能顺序查找）
另外，如果ntype不大的话，楼主可以考虑为每种类型建立一个映射表，映射表存放的是最近的一个元素对应的指针，要查找时，找这个映射表就好了，在入队的时候，更改这张表的相应元素，出队时麻烦些，要顺序查到最近的元素
如果出队比较多，可考虑出队时将对应元素置空，查到空元素时，再到整个链表进行顺序查找

#5

引用 3 楼 jiqiang01234 的回复:

可以用glib库，包含了常用的数据结构，而且跨平台。如果是c++就无所谓了，STL本身就跨平台

这是另外一回事了，
我现在想的是怎么实现这个消息队列

#6

引用 4 楼 r_Jimy 的回复:

链表只能顺序查找，不用哈希的话可以采用数组来存，这样可以使用折半查找（前提是入队时要排序，如果不排序，也只能顺序查找）
另外，如果ntype不大的话，楼主可以考虑为每种类型建立一个映射表，映射表存放的是最近的一个元素对应的指针，要查找时，找这个映射表就好了，在入队的时候，更改这张表的相应元素，出队时麻烦些，要顺序查到最近的元素
如果出队比较多，可考虑出队时将对应元素置空，查到空元素时，再到整个链表进行顺序查找

意思就是用ntype作为数组下标定位元素，如果有多个ntype重复的话，再用链表连接起来呗。
ntype大不大这个固定不了，也不可能是连续的。有可能是:1,2,3,5000。

总体上是用HASH然后解决冲突用链表了？

#7

引用 6 楼 zhxingway 的回复:

Quote: 引用 4 楼 r_Jimy 的回复:

链表只能顺序查找，不用哈希的话可以采用数组来存，这样可以使用折半查找（前提是入队时要排序，如果不排序，也只能顺序查找）
另外，如果ntype不大的话，楼主可以考虑为每种类型建立一个映射表，映射表存放的是最近的一个元素对应的指针，要查找时，找这个映射表就好了，在入队的时候，更改这张表的相应元素，出队时麻烦些，要顺序查到最近的元素
如果出队比较多，可考虑出队时将对应元素置空，查到空元素时，再到整个链表进行顺序查找

意思就是用ntype作为数组下标定位元素，如果有多个ntype重复的话，再用链表连接起来呗。
ntype大不大这个固定不了，也不可能是连续的。有可能是:1,2,3,5000。

总体上是用HASH然后解决冲突用链表了？

可以这么理解，ntype连上限也不确定吗，这比较难办，在HASH的时候要考虑下上限

#8

用c++ stl deque。

#9

引用 8 楼 guyuguang8628391 的回复:

用c++ stl deque。

公司不让用stl