A queue is basically a linear data structure that works on the principle of FIFO (First in First out) which means an element that is enqueued first will be dequeued first. Element is enqueued from the rear end of the queue and dequeued from the front end. The insertion operation in the queue is known as enqueue and the deletion operation in the queue is known as dequeue.
The queue is used when the operations are to be performed in the manner of First in First out order just like Breadth-First Search.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.
Basic Operations of Queue:
Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).
Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).
Front: This function returns the front element of the queue. The time complexity of this function is O(1).
Rear: This function returns the last element of the queue. The time complexity of this function is O(1).
Peek(): This operation is used to get the value of the element from the front of the queue.
Working of queue:
- We can implement queue by using two pointers i.e. FRONT and REAR.
- FRONT is used to track the first element of the queue.
- REAR is used to track the last element of the queue.
- Initially, we’ll set the values of FRONT and REAR to -1.
Drawback of simple queue:
- Operations like insertion and deletion of elements from the middle take too much time.
- Simple queue has limited space.
- For searching an element in a simple queue takes O(N) time.
- Maximum size of a queue must be defined prior.