Queue
A queue is an abstract data structure in the C++ programming language that operates in a first in first out (FIFO) type of system. It is similar to the ticket queue outside an atm or cinema hall, where the first person entering the queue is the first person who gets the ticket.
That is;
Queue follows the First In First Out (FIFO) operation rule- the item that goes in first will be the item that comes out first.
Basic Operations of Queue
A queue is an abstract data structure that permits the following operations:
- Enqueue: Append an element to the end of the queue
- Dequeue: Kill an element from the front of the queue
- IsEmpty: Verify if the queue is empty
- IsFull: Review if the queue is full
- Peek: Accept the value of the front of the queue without eliminating it
Working of Queue
Queue operations:
- two pointers FRONT and REAR
- FRONT track the first element of the queue
- REAR track the last element of the queue
- initially, set value of FRONT and REAR to -1
Enqueue Operation:
- check if the queue is full
- for the first element, set the value of FRONT to 0
- increase the REAR index by 1
- add the new element in the position pointed to by REAR
Dequeue Operation
- check if the queue is empty
- return the value pointed by FRONT
- increase the FRONT index by 1
- for the last element, reset the values of FRONT and REAR to -1
Complexity Analysis
O(1) is the complexity of enqueue and dequeue operations in a queue using an Array form.
Syntax:
template<class T, class Container = deque<T> > class queue; Member Types
member types in a Queue Data Structure:
| Member Types | Description |
|---|---|
| value_type | Element type is specified. |
| container_type | Underlying container type is specified. |
| size_type | It specifies the size range of the elements. |
| reference | It is a reference type of a container. |
| const_reference | It is a reference type of a constant container. |
| Function | Description |
|---|---|
| (constructor) | Used for the construction of a queue container. |
| empty | The function is utilized to test for the emptiness of a queue. If the queue is blank/empty then the function returns true else false. |
| size | The function gives the size of the queue container. |
| front | The function is used to locate and access the front element of the queue. |
| back | The function is used to locate and access the rear element of the queue. |
| push | The function is used to insert a new element at the rear end of the queue. |
| pop | The function is used for deleting an element. |
| emplace | The function is used for the insertion of new elements in the queue above the current rear element. |
| swap | The function is used for interchanging the contents of two containers in reference. |
| relational operators | The non member function specifies the relational operators that are needed for the queues. |
| uses allocator<queue> | As the name suggests the nonmember function uses the allocator for the queues. |
Applications of Queue
- The queue is used for synchronization when data is transferred asynchronously between two processes.
- Interrupts handing in real-time systems.
- Call Center phone systems.
- Disk Scheduling, CPU scheduling.
