Queue is an abstract data structure which can be visualized as a line of people waiting in a queue, where the first person to arrive is the first one to be served. New persons joining the queue will be served only after all persons already in the queue are served. Similarly. in a queue data structure, the element that has been added to the queue first will be the first one to be removed/processed. Because of this behavior, queue data structure is referred as a First in First out (FIFO) type of data structure.
Similar to the real world queues observed in check-in counters, ticket counters etc, Queue data structure has two endpoints: front and rear. New elements are added to the rear end of queue, and existing elements are removed from the front end of queue. This makes sure that the first element pushed into the queue will always be the first element to come out.
For example, if number 1 is pushed into the queue followed by number 2, 3 and 4, the queue looks like this:
rear-> 4 3 2 1 <-front
Now if number 5 is pushed into queue, it looks like this:
rear-> 5 4 3 2 1 <- front
When we try to remove an element, it is removed from the front end of queue. So this is how the queue looks after removing an element:
rear-> 5 4 3 2 <- front.
Basic Operations Supported by a Queue
Before we go through all the operations formally supported by a queue abstract data type, let’s go through a practical example and relate each operation to a corresponding one in real life.
Assume that there is a checkout queue at a grocery counter. Let us now think through all the operations that are necessary for proper funtioning of the queue:
- We need a way for people to join the queue. Also the persons reaching first in the queue should be at the front of queue.
- This action corresponds to
enqueue(person)/push(person)operation to the queue
- This action corresponds to
- We need a way to get details from person at the front of queue without removing him from queue and process the items he wishes to check out
- This action corresponds to
front()/first()operation to the queue which returns the element present at the end
- This action corresponds to
- We need a way for the persons whose items are processed to leave the queue and after this the next person who came the earliest among all remaining persons, should be at the front of queue
- This action corresponds to
dequeue()/pop()operation to the queue
- This action corresponds to
- We also need a way to check if the queue is empty or not and take decisions like halt the counter etc.
- This action corresponds to
is_empty()operation to the queue which tells us if the queue is empty
- This action corresponds to
All the operations discussed are summarized in the table below:
| Operation | Description |
|---|---|
| enqueue / push | Adds an element to the rear of the queue |
| dequeue / pop | Removes an element from the front of the queue |
| front / first | Examines the element at the front of the queue |
| is_empty | Determines whether the queue is empty |
Let us now go through each operation in detail.
Push an element into the rear end of Queue
This operation allows us to push or “enqueue” element into the queue. The enqueued element will be placed at end or tail of the queue. The animation below depicts enqueuing of 4 elements into a queue.
This operation is denoted by enqueue(element) or push(element) which takes an element as input and adds it to the rear end of queue.
Pop an element from the front end of Queue
This operation allows us to remove or “dequeue” the front element in the queue. It is similar to allowing person at the beginning of a queue to leave the queue. The animation below depicts dequeuing of 4 elements from a queue.
This operation is denoted by dequeue(element) or pop(element) which removes and returns the element present at the front of queue.
Access the element present at the front of Queue
This operation allows us to access the “front” element in the queue. It is similar to taking the credentials of a person standing at the front of a queue and doing some processing while the person is still in queue.
This operation is denoted by front() or first() which returns the information about the element present at the front of queue.
Check if the Queue is Empty
This operation is useful for finding out if a queue is empty. This is helpful especially to prevent popping / dequeuing an element from an empty queue. Or to prevent accessing the front element in an empty queue etc.
This operation is denoted by is_empty() which returns true if the queue is empty and false otherwise.
Applications of Queue Data Structure
For any use case which requires a data structure which removes elements in the same order of their addition can use a queue data structure. Below are some of the use cases:
- Queues are used for maintaining active playlists in media players (The song added to the queue first needs to be played before the next).
- Printers often have queues to manage incoming print jobs. The first print request is the first one to be processed, ensuring that all print jobs are executed in the order they were received.
- In task handlers where we need to process tasks on a first come first serve basis.
- In messaging queue’s where there is a need to decouple senders and listeners while maintaining the order of messages.
- In data buffers where processed data needs to be removed from the start of buffer and new data needs to be added to the end of buffer.