{"id":4119,"date":"2022-12-20T17:39:27","date_gmt":"2022-12-20T20:39:27","guid":{"rendered":"http:\/\/lode.uno\/linux-man\/index.php\/2022\/12\/20\/queue-man7\/"},"modified":"2022-12-20T17:39:27","modified_gmt":"2022-12-20T20:39:27","slug":"queue-man7","status":"publish","type":"post","link":"https:\/\/lode.uno\/linux-man\/2022\/12\/20\/queue-man7\/","title":{"rendered":"QUEUE (man7)"},"content":{"rendered":"

QUEUE<\/h1>\n

NAME<\/a>
DESCRIPTION<\/a>
CONFORMING TO<\/a>
SEE ALSO<\/a>
COLOPHON<\/a> <\/p>\n

\n

NAME <\/a> <\/h2>\n

queue \u2212 implementations of linked lists and queues<\/p>\n

DESCRIPTION <\/a> <\/h2>\n

The <\/i> header file provides a set of macros that define and operate on the following data structures:<\/p>\n\n\n\n\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

singly linked lists (SLIST)<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

doubly linked lists (LIST)<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

singly linked tail queues (STAILQ)<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

doubly linked tail queues (TAILQ)<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

doubly linked circular queues (CIRCLEQ)<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

All structures support the following functionality:<\/p>\n\n\n\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Insertion of a new entry at the head of the list.<\/p>\n<\/td>\n<\/tr>\n

<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Insertion of a new entry after any element in the list.<\/p>\n<\/td>\n<\/tr>\n

<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

O(1) removal of an entry from the head of the list.<\/p>\n<\/td>\n<\/tr>\n

<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Forward traversal through the list.<\/p>\n<\/td>\n<\/tr>\n<\/table>\n

Code size and execution time depend on the complexity of the data structure being used, so programmers should take care to choose the appropriate one.<\/p>\n

Singly linked lists (SLIST)<\/b>
Singly linked lists are the simplest and support only the above functionality. Singly linked lists are ideal for applications with large datasets and few or no removals, or for implementing a LIFO queue. Singly linked lists add the following functionality:<\/p>\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

O(n) removal of any entry in the list.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

Singly linked tail queues (STAILQ)<\/b>
Singly linked tail queues add the following functionality:<\/p>\n\n\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Entries can be added at the end of a list.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

O(n) removal of any entry in the list.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

They may be concatenated.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

However:<\/p>\n\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

All list insertions must specify the head of the list.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Each head entry requires two pointers rather than one.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

Singly linked tail queues are ideal for applications with large datasets and few or no removals, or for implementing a FIFO queue.<\/p>\n

Doubly linked data structures<\/b>
All doubly linked types of data structures (lists and tail queues) additionally allow:<\/p>\n\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Insertion of a new entry before any element in the list.<\/p>\n<\/td>\n<\/tr>\n

<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

O(1) removal of any entry in the list.<\/p>\n<\/td>\n<\/tr>\n<\/table>\n

However:<\/p>\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Each element requires two pointers rather than one.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

Doubly linked lists (LIST)<\/b>
Linked lists are the simplest of the doubly linked data structures. They add the following functionality over the above:<\/p>\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

They may be traversed backwards.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

However:<\/p>\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

To traverse backwards, an entry to begin the traversal and the list in which it is contained must be specified.<\/p>\n<\/td>\n<\/tr>\n<\/table>\n

Doubly linked tail queues (TAILQ)<\/b>
Tail queues add the following functionality:<\/p>\n\n\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Entries can be added at the end of a list.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

They may be traversed backwards, from tail to head.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

They may be concatenated.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

However:<\/p>\n\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

All list insertions and removals must specify the head of the list.<\/p>\n<\/td>\n<\/tr>\n

<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

Each head entry requires two pointers rather than one.<\/p>\n<\/td>\n<\/tr>\n<\/table>\n

Doubly linked circular queues (CIRCLEQ)<\/b>
Circular queues add the following functionality over the above:<\/p>\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

The first and last entries are connected.<\/p>\n<\/td>\n

 <\/td>\n<\/tr>\n<\/table>\n

However:<\/p>\n\n\n
<\/td>\n\n

*<\/p>\n<\/td>\n

<\/td>\n\n

The termination condition for traversal is more complex.<\/p>\n<\/td>\n<\/tr>\n<\/table>\n

CONFORMING TO <\/a> <\/h2>\n

Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs. <\/i> macros first appeared in 4.4BSD.<\/p>\n

SEE ALSO <\/a> <\/h2>\n

circleq<\/b>(3), insque<\/b>(3), list<\/b>(3), slist<\/b>(3), stailq<\/b>(3), tailq<\/b>(3)<\/p>\n

COLOPHON <\/a> <\/h2>\n

This page is part of release 5.10 of the Linux man-pages<\/i> project. A description of the project, information about reporting bugs, and the latest version of this page, can be found at https:\/\/www.kernel.org\/doc\/man\u2212pages\/.<\/p>\n

\n","protected":false},"excerpt":{"rendered":"

queue \u2212 implementations of linked lists and queues <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[971],"tags":[973,972,1198],"class_list":["post-4119","post","type-post","status-publish","format-standard","hentry","category-7-miscelanea","tag-973","tag-man7","tag-queue"],"gutentor_comment":0,"_links":{"self":[{"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/posts\/4119","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/comments?post=4119"}],"version-history":[{"count":0,"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/posts\/4119\/revisions"}],"wp:attachment":[{"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/media?parent=4119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/categories?post=4119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lode.uno\/linux-man\/wp-json\/wp\/v2\/tags?post=4119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}