{ "content": [ { "type": "text", "text": "# QUEUE (man)\n\n## NAME\n\nqueue - implementations of linked lists and queues\n\n## DESCRIPTION\n\nThe header file provides a set of macros that define and operate on the follow‐\ning data structures:\n\n## Sections\n\n- **NAME**\n- **DESCRIPTION** (6 subsections)\n- **CONFORMING TO**\n- **SEE ALSO**\n- **COLOPHON**\n\nUse structuredContent.sections for detailed options, examples, and full documentation.\n" } ], "structuredContent": { "command": "QUEUE", "section": "", "mode": "man", "summary": "queue - implementations of linked lists and queues", "synopsis": null, "tldr_summary": null, "tldr_examples": [], "tldr_source": null, "flags": [], "examples": [], "see_also": [ { "name": "circleq", "section": "3", "url": "https://www.chedong.com/phpMan.php/man/circleq/3/json" }, { "name": "insque", "section": "3", "url": "https://www.chedong.com/phpMan.php/man/insque/3/json" }, { "name": "list", "section": "3", "url": "https://www.chedong.com/phpMan.php/man/list/3/json" }, { "name": "slist", "section": "3", "url": "https://www.chedong.com/phpMan.php/man/slist/3/json" }, { "name": "stailq", "section": "3", "url": "https://www.chedong.com/phpMan.php/man/stailq/3/json" }, { "name": "tailq", "section": "3", "url": "https://www.chedong.com/phpMan.php/man/tailq/3/json" } ], "section_outline": [ { "name": "NAME", "lines": 2, "subsections": [] }, { "name": "DESCRIPTION", "lines": 26, "subsections": [ { "name": "Singly linked lists (SLIST)", "lines": 6 }, { "name": "Singly linked tail queues (STAILQ)", "lines": 17 }, { "name": "Doubly linked data structures", "lines": 10 }, { "name": "Doubly linked lists (LIST)", "lines": 10 }, { "name": "Doubly linked tail queues (TAILQ)", "lines": 14 }, { "name": "Doubly linked circular queues (CIRCLEQ)", "lines": 8 } ] }, { "name": "CONFORMING TO", "lines": 3, "subsections": [] }, { "name": "SEE ALSO", "lines": 2, "subsections": [] }, { "name": "COLOPHON", "lines": 7, "subsections": [] } ], "sections": { "NAME": { "content": "queue - implementations of linked lists and queues\n", "subsections": [] }, "DESCRIPTION": { "content": "The header file provides a set of macros that define and operate on the follow‐\ning data structures:\n\n* singly linked lists (SLIST)\n\n* doubly linked lists (LIST)\n\n* singly linked tail queues (STAILQ)\n\n* doubly linked tail queues (TAILQ)\n\n* doubly linked circular queues (CIRCLEQ)\n\nAll structures support the following functionality:\n\n* Insertion of a new entry at the head of the list.\n\n* Insertion of a new entry after any element in the list.\n\n* O(1) removal of an entry from the head of the list.\n\n* Forward traversal through the list.\n\nCode size and execution time depend on the complexity of the data structure being used, so\nprogrammers should take care to choose the appropriate one.\n", "subsections": [ { "name": "Singly linked lists (SLIST)", "content": "Singly linked lists are the simplest and support only the above functionality. Singly linked\nlists are ideal for applications with large datasets and few or no removals, or for imple‐\nmenting a LIFO queue. Singly linked lists add the following functionality:\n\n* O(n) removal of any entry in the list.\n" }, { "name": "Singly linked tail queues (STAILQ)", "content": "Singly linked tail queues add the following functionality:\n\n* Entries can be added at the end of a list.\n\n* O(n) removal of any entry in the list.\n\n* They may be concatenated.\n\nHowever:\n\n* All list insertions must specify the head of the list.\n\n* Each head entry requires two pointers rather than one.\n\nSingly linked tail queues are ideal for applications with large datasets and few or no re‐\nmovals, or for implementing a FIFO queue.\n" }, { "name": "Doubly linked data structures", "content": "All doubly linked types of data structures (lists and tail queues) additionally allow:\n\n* Insertion of a new entry before any element in the list.\n\n* O(1) removal of any entry in the list.\n\nHowever:\n\n* Each element requires two pointers rather than one.\n" }, { "name": "Doubly linked lists (LIST)", "content": "Linked lists are the simplest of the doubly linked data structures. They add the following\nfunctionality over the above:\n\n* They may be traversed backwards.\n\nHowever:\n\n* To traverse backwards, an entry to begin the traversal and the list in which it is con‐\ntained must be specified.\n" }, { "name": "Doubly linked tail queues (TAILQ)", "content": "Tail queues add the following functionality:\n\n* Entries can be added at the end of a list.\n\n* They may be traversed backwards, from tail to head.\n\n* They may be concatenated.\n\nHowever:\n\n* All list insertions and removals must specify the head of the list.\n\n* Each head entry requires two pointers rather than one.\n" }, { "name": "Doubly linked circular queues (CIRCLEQ)", "content": "Circular queues add the following functionality over the above:\n\n* The first and last entries are connected.\n\nHowever:\n\n* The termination condition for traversal is more complex.\n" } ] }, "CONFORMING TO": { "content": "Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. Present on the BSDs. macros\nfirst appeared in 4.4BSD.\n", "subsections": [] }, "SEE ALSO": { "content": "circleq(3), insque(3), list(3), slist(3), stailq(3), tailq(3)\n", "subsections": [] }, "COLOPHON": { "content": "This page is part of release 5.10 of the Linux man-pages project. A description of the\nproject, information about reporting bugs, and the latest version of this page, can be found\nat https://www.kernel.org/doc/man-pages/.\n\n\n\nGNU 2020-11-16 QUEUE(7)", "subsections": [] } } } }