Queue
C++ KotlinDefinition
The queue is a data structure to contain objects in the FIFO (First In First Out) order. This means that the first element to be added will be the first element to come out. In its most classic form it implements following operations:
- Peek : this operation returns the first element of the queue, in some cases it can also be implemented as Front
- Push: the operation adds an element in the last position of the queue
- Pop : this operation removes an element from the first position in the queue. In some implementations, the operation removes and returns the element that you removed
Complexity
| Operation | Average | Worst Case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(n) | O(n) |
| Peek | O(1) | O(1) |
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
Implementation
The queue can be implemented in two ways: through a static vector with fixed size where the index of the initial position is stored and this value is rotated by the vector, or through a linked list.
When deploying with a linked list, it is necessary to keep a pointer to the last position in the list so that the insert maintains the complexity O(1).