Data Structure in C++: 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.


template<class T, class Container = deque<T> > class queue;  

Member Types

member types in a Queue Data Structure:

Member TypesDescription
value_typeElement type is specified.
container_typeUnderlying container type is specified.
size_typeIt specifies the size range of the elements.
referenceIt is a reference type of a container.
const_referenceIt is a reference type of a constant container.
(constructor)Used for the construction of a queue container.
emptyThe function is utilized to test for the emptiness of a queue. If the queue is blank/empty then the function returns true else false.
sizeThe function gives the size of the queue container.
frontThe function is used to locate and access the front element of the queue.
backThe function is used to locate and access the rear element of the queue.
pushThe function is used to insert a new element at the rear end of the queue.
popThe function is used for deleting an element.
emplaceThe function is used for the insertion of new elements in the queue above the current rear element.
swapThe function is used for interchanging the contents of two containers in reference.
relational operatorsThe 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.
We will be happy to hear your thoughts

Leave a reply

Open chat
Scan the code
Can we help you?