1. 首页
  2. 文章中心
  3. Linux内核相关

Linux的队列 std/queue.h

80 阅读 0 评论
我是靠谱客的博主 奋斗发卡，最近开发中收集的这篇文章主要介绍Linux的队列 std/queue.h，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Linux的队列 queue.h

    • 环境
    • 介绍
    • List
    • Singly-linked list
    • Singly-linked tail queue(Simple queue)
    • Tail queue
    • Circular queue

环境

Ubuntu16.04 x86_64 GNU/Linux , 4.15.0-43-generic

介绍

<sys/queue.h> 实现了5种数据结构 :

	singly-linked list  
	list 
	simple queue 
	tail queue 
	circular queue

下面对他们分别进行介绍

List

List是双向链表 : head节点不包含指向最后一个节点的指针，其结构如下图 :
LIST结构
Description :

	A list is headed by a single forward pointer (or an array of forward 
	pointers for a hash table header). The elements are doubly linked 
	so that an arbitrary element can be removed without a need to 
	traverse the list. New elements can be added to the list before
	or after an existing element or at the head of the list. A list
	may only be traversed in the forward direction.

Interface :

	LIST_INIT(head) :对head进行初始化
	LIST_INSERT_HEAD(head, elm, field) : 从list头部插入elm
	LIST_REMOVE(elm, field) : 将elm从list中删除
	LIST_INSERT_AFTER(listelm, elm, field) : 将elm插入到listelm后面
	LIST_INSERT_BEFORE(listelm, elm, field) : 将elm插入到liistelm之前
	LIST_FOREACH(var, head, field) : 循环遍历所有节点, var为中间变量 
	LIST_EMPTY(head) : 判断list是否为空
	LIST_FIRST(head) : 获取第一个节点
	LIST_NEXT(elm, field) : 获取elm的下一个节点

Example：

#include <sys/queue.h>
#include <stdlib.h>
#include <stdio.h>

struct node {
	LIST_ENTRY(node) next;
	int num;
};

LIST_HEAD(head, node);

struct head* lhead = NULL;


int main(int argc, char* argv[]){
	lhead = (struct head*)malloc(sizeof(struct head));
	LIST_INIT(lhead);
	
	struct node *var;
	struct node *num_1 = (struct node *)malloc(sizeof(struct node));
	num_1->num = 1;
	LIST_INSERT_HEAD(lhead, num_1, next);
	LIST_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");

	struct node *num_2 = (struct node *)malloc(sizeof(struct node));
	num_2->num = 2;
	struct node *num_3 = (struct node *)malloc(sizeof(struct node));
	num_3->num = 3;
	LIST_INSERT_HEAD(lhead, num_2, next);
	LIST_INSERT_HEAD(lhead, num_3, next);
	LIST_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	struct node *num_4 = (struct node *)malloc(sizeof(struct node));
	num_4->num = 4;
	struct node *num_5 = (struct node *)malloc(sizeof(struct node));
	num_5->num = 5;
	LIST_INSERT_BEFORE(num_3, num_4, next);
	LIST_INSERT_AFTER(num_3, num_5, next);
	LIST_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	LIST_REMOVE(num_3, next);
	LIST_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	var = LIST_NEXT(num_4, next);
	printf("4's next is %dn", var->num);
	return 0;
}

Singly-linked list

singly-linked list 是单向链表，head不包含指向最后一个元素的指针，其结构如下图:
Slist
Description :

	* A singly-linked list is headed by a single forward pointer. The
	* elements are singly linked for minimum space and pointer manipulation
	* overhead at the expense of O(n) removal for arbitrary elements. New
	* elements can be added to the list after an existing element or at the
	* head of the list.  Elements being removed from the head of the list
	* should use the explicit macro for this purpose for optimum
	* efficiency. A singly-linked list may only be traversed in the forward
	* direction.  Singly-linked lists are ideal for applications with large
	* datasets and few or no removals or for implementing a LIFO queue.

Interface :

	SLIST_INIT(head) : 对head进行初始化
	SLIST_INSERT_HEAD(head, elm, field) : 从list头部插入elm
	SLIST_INSERT_AFTER(slistelm, elm, field) : 将elm 插入到slistelm后面
	SLIST_REMOVE_HEAD(head, field) : 从list的头部删除一个节点
	SLIST_REMOVE(head, elm, type, field) : 从list中删除elm
	SLIST_FOREACH(var, head, field) : 循环遍历所有节点, var为中间变量 
	SLIST_EMPTY(head) : 判断list是否为空
	SLIST_FIRST(head) : 获取第一个节点
	SLIST_NEXT(elm, field) : 获取elm的下一个节点

Example：

#include <sys/queue.h>
#include <stdlib.h>
#include <stdio.h>

struct node{
	SLIST_ENTRY(node) next;
	int num;
};
SLIST_HEAD(head, node);
struct head *lhead = 0;
int main(int argc, char* argv[]){
	lhead = (struct head*)malloc(sizeof(struct head));
	SLIST_INIT(lhead);
	
	struct node *var;

	struct node* num_1 = (struct node*)malloc(sizeof(struct node));
	num_1->num = 1;
	SLIST_INSERT_HEAD(lhead, num_1, next);
	SLIST_FOREACH(var, lhead, next){
		printf("%d->",var->num);
	}
	printf("nulln");

	struct node* num_2 = (struct node*)malloc(sizeof(struct node));
	num_2->num = 2;
	struct node* num_3 = (struct node*)malloc(sizeof(struct node));
	num_3->num = 3;	
	struct node* num_4 = (struct node*)malloc(sizeof(struct node));
	num_4->num = 4;
	SLIST_INSERT_AFTER(num_1, num_2, next);
	SLIST_INSERT_AFTER(num_1, num_3, next);
	SLIST_INSERT_AFTER(num_1, num_4, next);
	SLIST_FOREACH(var, lhead, next){
		printf("%d->",var->num);
	}
	printf("nulln");

	SLIST_REMOVE_HEAD(lhead, next);
	SLIST_FOREACH(var, lhead, next){
		printf("%d->",var->num);
	}
	printf("nulln");

	SLIST_REMOVE(lhead, num_3, node, next);
	SLIST_FOREACH(var, lhead, next){
		printf("%d->",var->num);
	}
	printf("nulln");
	return 0;
}

Singly-linked tail queue(Simple queue)

Simple queue同Singly-linked tail queue, 将接口前缀改为SIMPLEQ_ , 并且没有CONCAT方法，下面的description使用的为simple queue的description，两者的实现几乎完全一致。
Singly-linked tail queue是单向链表，head节点包含指向最后一个节点的指针，其结构图如下:
STAILQ
Description :

	* A simple queue is headed by a pair of pointers, one the head of the
	* list and the other to the tail of the list. The elements are singly
	* linked to save space, so elements can only be removed from the
	* head of the list. New elements can be added to the list after
	* an existing element, at the head of the list, or at the end of the
	* list. A simple queue may only be traversed in the forward direction.

Interface :

	STAILQ_INIT(head) : 对head进行初始化
	STAILQ_INSERT_HEAD(head, elm, field) : 从queue头部插入elm
	STAILQ_INSERT_TAIL(head, elm, field) : 从queue尾部插入elm
	STAILQ_INSERT_AFTER(head, listelm, elm, field) : 将elm 插入到listelm后面
	STAILQ_REMOVE_HEAD(head, field) : 从queue头部删去一个节点
	STAILQ_REMOVE(head, elm, type, field) : 将queue中的elm删除
	STAILQ_FOREACH(var, head, field) : 循环遍历所有节点, var为中间变量 
	STAILQ_CONCAT(head1, head2) : 将两个queue拼接，head1为拼接后的queue的头部，head2被重新初始化
	STAILQ_EMPTY(head): 判断queue是否为空
	STAILQ_FIRST(head): 获取第一个节点
	STAILQ_NEXT(elm, next): 获取elm的下一个节点

Example：

#include <sys/queue.h>
#include <stdlib.h>
#include <stdio.h>

struct node{
	STAILQ_ENTRY(node) next;
	int num;
};
STAILQ_HEAD(head, node);
struct head *lhead = 0;
struct head *llhead = 0;

int main(int argc, char* argv[]){
	lhead = (struct head*)malloc(sizeof(struct head));
	STAILQ_INIT(lhead);
	
	struct node* var = 0;
	struct node* num[9];
	for(int i=0; i<9; i++){
		num[i] = (struct node*)malloc(sizeof(struct node));
		num[i]->num = i;
	}
	STAILQ_INSERT_HEAD(lhead, num[0], next);
	STAILQ_INSERT_HEAD(lhead, num[1], next);
	STAILQ_INSERT_TAIL(lhead, num[2], next);
	STAILQ_INSERT_AFTER(lhead, num[1], num[3], next);
	STAILQ_INSERT_TAIL(lhead, num[4], next);
	STAILQ_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	llhead = (struct head*)malloc(sizeof(struct head));
	STAILQ_INIT(llhead);
	
	STAILQ_INSERT_TAIL(llhead, num[5], next);
	STAILQ_INSERT_TAIL(llhead, num[6], next);
	STAILQ_INSERT_TAIL(llhead, num[7], next);
	STAILQ_INSERT_TAIL(llhead, num[8], next);
	STAILQ_FOREACH(var, llhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	STAILQ_REMOVE(llhead, num[6], node, next);
	STAILQ_FOREACH(var, llhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	STAILQ_REMOVE_HEAD(llhead, next);
	STAILQ_FOREACH(var, llhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");

	STAILQ_CONCAT(lhead, llhead);
	STAILQ_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	return 0;
}

Tail queue

Tail queue是 双向链，head节点包含指向最后一个节点的指针，其结构图如下:
TAILQ
Description :

	* A tail queue is headed by a pair of pointers, one to the head of the
	* list and the other to the tail of the list. The elements are doubly
	* linked so that an arbitrary element can be removed without a need to
	* traverse the list. New elements can be added to the list before or
	* after an existing element, at the head of the list, or at the end of
	* the list. A tail queue may be traversed in either direction

Interface :

	TAILQ_INIT(head) : 对head进行初始化
	TAILQ_INSERT_HEAD(head, elm, field) : 从queue头部插入elm
	TAILQ_INSERT_TAIL(head, elm, field) : 从queue尾部插入elm
	TAILQ_INSERT_AFTER(head, listelm, elm, field) ：将elm 插入到listelm后面
	TAILQ_INSERT_BEFORE(listelm, elm, field) ：将elm 插入到listelm前面
	TAILQ_REMOVE(head, elm, field) : 将queue中的elm删除
	TAILQ_FOREACH(var, head, field) : 正向遍历所有节点, var为中间变量
	TAILQ_FOREACH_REVERSE(var, head, headname, field): 反向遍历所有节点, var为中间变量
	TAILQ_CONCAT(head1, head2, field)：将两个queue拼接，head1为拼接后的queue的头部，head2被重新初始化
	TAILQ_EMPTY(head) ：判断queue是否为空
	TAILQ_FIRST(head) ：获取第一个节点
	TAILQ_NEXT(elm, field) ： 获取elm的下一个节点
	TAILQ_LAST(elm, headname) ：获取最后一个节点
	TAILQ_PREV(elm, headname, field) : 获取elm的前一个节点

Example：

#include <sys/queue.h>
#include <stdlib.h>
#include <stdio.h>


struct node{
	TAILQ_ENTRY(node) next;
	int num;
};
TAILQ_HEAD(head, node);
struct head *lhead = 0;
struct head *llhead = 0;

int main(int argc, char* argv[]){
	lhead = (struct head*)malloc(sizeof(struct head));
	TAILQ_INIT(lhead);
	
	struct node* var = 0;
	struct node* num[9];
	for(int i=0; i<9; i++){
		num[i] = (struct node*)malloc(sizeof(struct node));
		num[i]->num = i;
	}
	TAILQ_INSERT_HEAD(lhead, num[0], next);
	TAILQ_INSERT_HEAD(lhead, num[1], next);
	TAILQ_INSERT_TAIL(lhead, num[2], next);
	TAILQ_INSERT_AFTER(lhead, num[1], num[3], next);
	TAILQ_INSERT_BEFORE(num[2], num[4], next);
	TAILQ_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	llhead = (struct head*)malloc(sizeof(struct head));
	TAILQ_INIT(llhead);

	TAILQ_INSERT_TAIL(llhead, num[5], next);
	TAILQ_INSERT_TAIL(llhead, num[6], next);
	TAILQ_INSERT_TAIL(llhead, num[7], next);
	TAILQ_INSERT_TAIL(llhead, num[8], next);
	TAILQ_FOREACH(var, llhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	TAILQ_REMOVE(llhead, num[6], next);
	TAILQ_FOREACH(var, llhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	TAILQ_FOREACH_REVERSE(var, lhead, head, next){
		printf("%d->", var->num);
	}
	printf("nulln");
		
	TAILQ_CONCAT(lhead, llhead, next);
	TAILQ_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	return 0;
}

Circular queue

Circular queue是环状双向链表, head节点包含指向最后一个节点的指针，最后一个节点的next指向head节点, 其结构图如下:
CIRCLEQ
Description :

	* A circle queue is headed by a pair of pointers, one to the head of the
	* list and the other to the tail of the list. The elements are doubly
	* linked so that an arbitrary element can be removed without a need to
	* traverse the list. New elements can be added to the list before or after
	* an existing element, at the head of the list, or at the end of the list.
	* A circle queue may be traversed in either direction, but has a more
	* complex end of list detection.

Interface :

	CIRCLEQ_INIT(head) : 对head进行初始化
	CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) : 将elm 插入到listelm后面
	CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) : 将elm 插入到listelm前面
	CIRCLEQ_INSERT_HEAD(head, elm, field)：从queue头部插入elm
	CIRCLEQ_INSERT_TAIL(head, elm, field)：从queue尾部插入elm
	CIRCLEQ_REMOVE(head, elm, field) : 将queue中的elm删除
	CIRCLEQ_FOREACH(var, head, field) : 正向遍历所有节点, var为中间变量
	CIRCLEQ_FOREACH_RESERVE(var, head, field) : 反向遍历所有节点, var为中间变量
	CIRCLEQ_EMPTY(head) : 判断queue是否为空
	CIRCLEQ_FIRST(head) : 获取第一个节点
	CIRCLEQ_LAST(head) : 获取最后一个节点
	CIRCLEQ_NEXT(elm, field) : 获取elm的下一个节点
	CIRCLEQ_PREV(elm, field) : 获取elm的上一个节点
	CIRCLEQ_LOOP_NEXT(head, elm, field) : 获取elm的下一个节点(会跳过头节点)
	CIRCLEQ_LOOP_PREV(head, elm, field) : 获取elm的上一个节点(会跳过头节点)

Example：

#include <sys/queue.h>
#include <stdlib.h>
#include <stdio.h>

struct node{
	CIRCLEQ_ENTRY(node) next;
	int num;
};
CIRCLEQ_HEAD(head, node);
struct head *lhead = 0;

int main(int argc, char* argv[]){
	lhead = (struct head*)malloc(sizeof(struct head));
	CIRCLEQ_INIT(lhead);
	
	struct node* var = 0;
	struct node* num[9];
	for(int i=0; i < 9; i++){
		num[i] = (struct node*)malloc(sizeof(struct node));
		num[i]->num = i; 
	}
	
	CIRCLEQ_INSERT_HEAD(lhead, num[0], next);
	CIRCLEQ_INSERT_HEAD(lhead, num[1], next);
	CIRCLEQ_INSERT_TAIL(lhead, num[2], next);
	CIRCLEQ_INSERT_AFTER(lhead, num[1], num[3], next);
	CIRCLEQ_INSERT_BEFORE(lhead, num[2], num[4], next);
	CIRCLEQ_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	CIRCLEQ_REMOVE(lhead, num[0], next);
	CIRCLEQ_FOREACH(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	
	CIRCLEQ_FOREACH_REVERSE(var, lhead, next){
		printf("%d->", var->num);
	}
	printf("nulln");
	return 0;
}

最后

以上就是奋斗发卡为你收集整理的Linux的队列 std/queue.h的全部内容，希望文章能够帮你解决Linux的队列 std/queue.h所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(53)

相关文章

ubuntu18.04下Value ‘SM_30‘ is not defined for option ‘gpu-name‘
ubuntu18.04下Value ‘SM_30‘ is not defined for option ‘gpu-name‘
gcc c++标准库源码位置
gcc c++标准库源码位置
Linux系统编程（22）——C++中自带的std::thread
Linux系统编程（22）——C++中自带的std::thread
base operand of '->' has non-pointer type 'const Comple
base operand of '->' has non-pointer type 'const Comple
Linux的队列 std/queue.h
Linux的队列 std/queue.h
Linux命令行下C++编程初体验
Linux命令行下C++编程初体验
安装mysql纪实（转载）
安装mysql纪实（转载）
centos6使用devtoolset快速升级GCC版本4.8/5.2/8.3
centos6使用devtoolset快速升级GCC版本4.8/5.2/8.3

评论列表共有 0 条评论

立即
投稿
返回
顶部