Intrusive queue container. More...
#include <queue.h>
Classes | |
| struct | Node |
| Queue node. More... | |
Public Types | |
| typedef T | value_type |
| typedef value_type & | reference |
| typedef const value_type & | const_reference |
| typedef value_type * | pointer |
| typedef const value_type * | const_pointer |
| typedef ptrdiff_t | difference_type |
| typedef size_t | size_type |
| typedef QueueIterator< T > | iterator |
| typedef QueueConstIterator< T > | const_iterator |
Public Member Functions | |
| Queue () noexcept | |
| template<class InputIterator > | |
| Queue (InputIterator first, InputIterator last) noexcept | |
| Queue (const Queue &) noexcept=default | |
| Queue (Queue &&) noexcept=default | |
| ~Queue () noexcept=default | |
| Queue & | operator= (const Queue &) noexcept=default |
| Queue & | operator= (Queue &&) noexcept=default |
| operator bool () const noexcept | |
| Check if the queue is not empty. More... | |
| bool | empty () const noexcept |
| Is the queue empty? More... | |
| size_t | size () const noexcept |
| Get the queue size. More... | |
| T * | front () noexcept |
| Get the front queue item. More... | |
| const T * | front () const noexcept |
| T * | back () noexcept |
| Get the back queue item. More... | |
| const T * | back () const noexcept |
| iterator | begin () noexcept |
| Get the begin queue iterator. More... | |
| const_iterator | begin () const noexcept |
| const_iterator | cbegin () const noexcept |
| iterator | end () noexcept |
| Get the end queue iterator. More... | |
| const_iterator | end () const noexcept |
| const_iterator | cend () const noexcept |
| void | push (T &item) noexcept |
| Push a new item into the back of the queue. More... | |
| T * | pop () noexcept |
| Pop the item from the front of the queue. More... | |
| void | reverse () noexcept |
| Reverse the queue. More... | |
| void | clear () noexcept |
| Clear the queue. More... | |
| void | swap (Queue &queue) noexcept |
| Swap two instances. More... | |
Friends | |
| template<typename U > | |
| void | swap (Queue< U > &queue1, Queue< U > &queue2) noexcept |
Detailed Description
template<typename T>
class CppCommon::Queue< T >
Intrusive queue container.
Queue represents container with FIFO (first in - first out) stock algorithm. For example, you insert item A into queue. Then you insert item B into queue. There is an item A at the begin of the queue and there is an item B at the end of the queue. After removing item A, there will be an item B at the begin of the queue.
Not thread-safe.
Overview
In providing services in computer science, transport, and operations research a queue is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. The most well known operation of the queue is the First-In-First-Out (FIFO) queue process - In a FIFO queue, the first element in the queue will be the first one out; this is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked.
There are two basic operations associated with a queue: enqueue and dequeue. Enqueue means adding a new item to the rear of the queue while dequeue refers to removing the front item from queue and returns it in item.
Theoretically, one characteristic of a queue is that it does not have a specific capacity. Regardless of how many elements are already contained, a new element can always be added. It can also be empty, at which point removing an element will be impossible until a new element has been added again.
A practical implementation of a queue of course does have some capacity limit, that depends on the concrete situation it is used in. For a data structure the executing computer will eventually run out of memory, thus limiting the queue size. Queue overflow results from trying to add an element onto a full queue and queue underflow happens when trying to remove an element from an empty queue.
Scheduling and buffering queues A queue is natural data structure for a system to serve the incoming requests. Most of the process scheduling or disk scheduling algorithms in operating systems use queues. Computer hardware like a processor or a network card also maintain buffers in the form of queues for incoming resource requests. A stack like data structure causes starvation of the first requests, and is not applicable in such cases. A mailbox or port to save messages to communicate between two users or processes in a system is essentially a queue like structure.
Search space exploration Like stacks, queues can be used to remember the search space that needs to be explored at one point of time in traversing algorithms. Breadth first search of a graph uses a queue to remember the nodes yet to be visited.
References
- Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238-243.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp.200-204.
Taken from:
Stack from Wikipedia, the free encyclopedia http://en.wikipedia.org/wiki/Queue
- Examples
- containers_queue.cpp.
Member Typedef Documentation
◆ const_iterator
| typedef QueueConstIterator<T> CppCommon::Queue< T >::const_iterator |
◆ const_pointer
| typedef const value_type* CppCommon::Queue< T >::const_pointer |
◆ const_reference
| typedef const value_type& CppCommon::Queue< T >::const_reference |
◆ difference_type
| typedef ptrdiff_t CppCommon::Queue< T >::difference_type |
◆ iterator
| typedef QueueIterator<T> CppCommon::Queue< T >::iterator |
◆ pointer
| typedef value_type* CppCommon::Queue< T >::pointer |
◆ reference
| typedef value_type& CppCommon::Queue< T >::reference |
◆ size_type
| typedef size_t CppCommon::Queue< T >::size_type |
◆ value_type
| typedef T CppCommon::Queue< T >::value_type |
Constructor & Destructor Documentation
◆ Queue() [1/4]
|
inlinenoexcept |
◆ Queue() [2/4]
|
inlinenoexcept |
◆ Queue() [3/4]
|
defaultnoexcept |
◆ Queue() [4/4]
|
defaultnoexcept |
◆ ~Queue()
|
defaultnoexcept |
Member Function Documentation
◆ back() [1/2]
|
inlinenoexcept |
◆ back() [2/2]
|
inlinenoexcept |
◆ begin() [1/2]
|
inlinenoexcept |
◆ begin() [2/2]
|
inlinenoexcept |
◆ cbegin()
|
inlinenoexcept |
◆ cend()
|
inlinenoexcept |
◆ clear()
|
inlinenoexcept |
◆ empty()
|
inlinenoexcept |
◆ end() [1/2]
|
inlinenoexcept |
◆ end() [2/2]
|
inlinenoexcept |
◆ front() [1/2]
|
inlinenoexcept |
◆ front() [2/2]
|
inlinenoexcept |
◆ operator bool()
|
inlineexplicitnoexcept |
◆ operator=() [1/2]
|
defaultnoexcept |
◆ operator=() [2/2]
|
defaultnoexcept |
◆ pop()
|
inlinenoexcept |
Pop the item from the front of the queue.
- Returns
- The front item popped from the queue
- Examples
- containers_queue.cpp.
◆ push()
|
inlinenoexcept |
Push a new item into the back of the queue.
- Parameters
-
item - Pushed item
- Examples
- containers_queue.cpp.
◆ reverse()
|
inlinenoexcept |
◆ size()
|
inlinenoexcept |
◆ swap()
|
inlinenoexcept |
Friends And Related Function Documentation
◆ swap
|
friend |
The documentation for this class was generated from the following files:
