Queue
A Queue is a non-primitive linear data structure.
A Queue is a linear list in which elements can be inserted only at one end
called the rear of the queue and deleted only at the other end called the
front of the queue.
Car lined in Toll Gate. Luggage kept on conveyor belts in the Airport.
People standing in a long line to get cinema tickets.
In a queue, the insertion operation is known as enqueue and deletion is
known as dequeue.
Front Rear Front Rear Front Rear
A B C D E A B C D E F B C D E F
Insert an element Delete an element
Initial Queue
(ENQUEUE) (DEQUEUE)
Queue is also called First-IN-FIRST-OUT (FIFO) type of data structure.
Queue can be represented either by using an array or by using a linked list.
Queue implementation using an array:
#define MAX 10;
int queue_arr[MAX];
int rear = -1;
int front = -1;
(a) Empty queue (b) enqueue 5 (c) enqueue 10
front =-1 rear=-1 front =0 rear=0 front =0 rear=1
5 5 10
[0] [1] [2] [3] [4] [0] [1] [2] [3] [4] [0] [1] [2] [3] [4]
(d) enqueue 15 5 (e) dequeue 10 (f) dequeue
front =0 rear=2 front =1 rear=2 front =2 rear=2
5 10 15 10 15 15
[0] [1] [2] [3] [4] [0] [1] [2] [3] [4] [0] [1] [2] [3] [4]
(g) dequeue 15 (h) enqueue 20 (i) enqueue 25
front =3 rear=2 front =3 rear=3 front =3 rear=4
20 20 25
[0] [1] [2] [3] [4] [0] [1] [2] [3] [4] [0] [1] [2] [3] [4]
Initially when the queue is empty, the values of both front and rear will be
-1.
For Insertion, the value of rear is incremented by 1 and the element is
inserted at the new rear position.
For Deletion, the element at front position is deleted and the value of front
is incremented by 1.
When insertion is done in an initially empty queue, i.e. if the value of front
is -1, then value of front is made 0.
Queue is empty:
front = = -1 || front = = rear+1
Queue is full:
rear = = MAX-1
Basic Operations on Queue
In order to make manipulations in a stack, there are certain operations
provided to us.
➢ Enqueue( ) to insert an element into the queue
➢ Dequeue( ) to remove an element from the queue
➢ peek( ) To display the element at the front
➢ isEmpty( ) returns true if queue is empty else false.
➢ isFull( ) returns true if queue is full else false.
➢ display( ) to print all elements of the queue.
Enqueue operation: Enqueue( ) adds an item to the queue from the rear side. If
the queue is full, then it is said to be an Overflow condition i.e. rear = = MAX-1.
void Enqueue(int item)
{
if(rear == MAX-1){
print("Overflow"); //queue is full.
return;
}
if(front == -1){ //If the queue is empty
front = 0;
rear = 0;
queue_arr[rear] = item;
}
else{
rear = rear + 1; //rear point to the next index
queue_arr[rear] = item;
}
}
Dequeue operation: Dequeue( ) delete an item to the queue from the front side.
If the queue is already empty, in that case, we return an underflow error. If the
queue is not empty, we delete the front node and move the front pointer to the
next node.
int dequeue()
{
int temp;
if(front = = -1) //If the queue is empty
{
printf("Underflow");
return 0;
}
if(front = = rear) //If queue has only one element
{
temp = queue_arr[front];
front = -1;
rear = -1;
return temp;
}
else
{
temp = queue_arr[front];
front = front + 1;
return temp;
}
}
Peek Operation: This operation returns the value of the data element at the
front of the queue without deleting it.
int peek( )
{
if(isEmpty())
{
printf(“stack underflow”);
return;
}
return queue_arr(front);
}
isEmpty( ) Operation isFull( ) Operation
int isEmpty( ) int isFull( )
{ {
if(front == -1 || front == rear+1) if(rear == MAX-1)
return 1; return 1;
else else
return 0; return 0;
} }
display( ): print all elements of the queue.
void display( )
{
int i;
if(isEmpty())
{
printf(“queue is empty\n”);
return;
}
printf(“Queue elements are: ”);
for(i=front; i<=rear; i++)
printf(“%d\n”, queue_arr(i));
printf(“\n”);
}
Applications of Linear Queue
The major applications of the queue data structure are:
1. Asynchronous data transfer
We can make use of queues to transfer data asynchronously. Asynchronous transfer means when
the rate of transmission of data is not the same between two processes. For example, queues are
used in pipes, file input/output, sockets for asynchronous data transfer.
2. Multiple users for a single resource
Whenever we need to make the process wait for a single shared resource, we maintain them
inside a queue. For example, printer, CPU, etc are the shared resources.
3. Used as buffers
Queues are useful as a buffer to store the data primarily whenever required. For example, the
queue is used as a buffer in the case of MP3 players. CD players, etc.
4. Interrupt handling
Whenever a process gets interrupted, it is sent back and made to wait in the queue. Thus, queue
helps in interrupt handling.
5. Maintain playlists
Queues help maintain any kinds of lists. We can maintain a playlist of songs or other media with
the help of queues.
Disadvantages of array implementation
• It is not dynamic i.e., it doesn’t grow and shrink depending on needs at
runtime.
• The total size of the queue must be defined beforehand.
